[Exercise] Tic Tac Toe

Joe · November 5 2012

This thread presents several exercises based around the game of Tic Tac Toe. We will consider that X always go first.
You are free to chose any way you like to represent the board, but for the sake of clarity we will represent by a 9 character string, like this: Each cell in the board is represents an index from 0 to 8 and its value is the corresponding index in the state string.

|---+---+---|
| 0 | 1 | 2 |
|---+---+---|
| 3 | 4 | 5 |
|---+---+---|
| 6 | 7 | 8 |
|---+---+---|

For instance, "XOX-X-OO-" represents the following board:

|---+---+---|
| X | O | X |
|---+---+---|
| - | X | - |
|---+---+---|
| O | O | - |
|---+---+---|

NB: Empty cells are marked "-".

Unlike the usual exercise threads, this time I'll suggest several different (albeit slightly dependent) exercises and you can chose whichever you want to work on.

Easy exercise

Write a program that takes a string representation of the board as an input and prints the matrix representation similar to the above quote. Example:

>>> print_matrix("XXOXOOXOX")
|---+---+---|
| X | X | O |
|---+---+---|
| X | O | O |
|---+---+---|
| X | O | X |
|---+---+---|

You can make this exercise more interesting by coming up with a way that will scale easily to a 1000x1000 matrix.

Math Exercise

Let's formalize the rules of the game. A board position is considered a "valid ending" if:

"X" wins.
"O" wins.
all the pieces of the board have been filled with no-one winning. It's a tie.

The goal of this exercise is to compare the success rate of "X" (first player to play) to the success rate of "O" and determine whether the player who starts has a statistical advantage.
"Success rate" is defined by "the number of total winning positions divided by the total number of valid endings".

Be careful when thinking about the total number of valid endings as certain conditions have to be taken into account. For instance here are examples of invalid endings:

"XXXOXXOOO": you cannot have 2 winners at once.
"XOOXOXOOX": since X starts, you cannot have more Os than Xs.
"XOOX--X-O": if X wins, there must be one X more than there are Os. (Remember X always starts)
...

The list goes on and it's up to you to develop a test to determine what constitutes a valid ending.

Note: If you work on this exercise, and since I don't have the solution (I just made it up), it'd be great if you included a short explanation text along with your code so we can discuss different approaches taken.

UI exercise

Write a simple 2 player Tic Tac Toe game. You have total freedom over the UI of the game. It could be something over the web or a JS script inside your browser or a native GUI app or a command line game or ... you come up with something!

AI exercise

Write a 1 player Tic Tac Toe game where the user plays against the AI.
You are asked to write this AI in such a way that it never loses. Remember that in this game, if both players behave optimally, the game will inevitably end in a draw. So your task is to write an AI that makes "no mistakes".
Your AI should be able to assume both "X" and "O" plays.

Use the UI developed in the above exercise so other players can play against your AI.

Note for devs interested in Functional Programming: This exercise was solved in a famous paper by John Hughes written in 1984. In this paper, titled "Why functional programming matters", the author makes a theoretical presentation of Functional Programming (using Miranda, an old language close to Haskell). The paper ends with the solving of a Tic Tac Toe puzzle. It's a great introduction to the paradigm, I strongly suggest you read it.
Re-implementing Hughes' solution in another language is considered an acceptable solution to this exercise.

geek · November 6 2012

Grid:

TTTSize[s_] := IntegerPart[Sqrt[Length[s]]];
TTTMatrix[s_] := Partition[s, TTTSize[s]];
TTTGrid[s_] := Grid[TTTMatrix[s], Frame -> All, ItemSize -> {N@GoldenRatio, N@GoldenRatio}];

TTTGrid[Characters["XXOO-OXOX"]]

TTT Grid

Winner?

TTTWinner[s_, t_] := With[
    {n = TTTSize[s], T = TTTMatrix[s]},
    MemberQ[
        Join[T, Transpose[T], {Diagonal[T]}, {Diagonal[Reverse[T]]}], 
        Array[t &, n]
    ]
];

X wins when {X, X, X} is a row, a column, or a diagonal.

Two-player game using row-major indexing:

n = 3;
t = Riffle[Array["X" &, Ceiling[n^2/2]], Array["O" &, Floor[n^2/2]]];
s = Array["-" &, n^2];
d = 1;
b = False;

While[d <= n^2 && !b,
    a = ToExpression[Input[]];
    s[[a]] = t[[d]];
    Print[t[[d]], "@", a];
    Print@TTTGrid[s];

    If[TTTWinner[s, t[[d]]],
        Print[t[[d]] <> " is a winner."];
        b = True;
    ];

    d++;
];

TTT Game

Given that X starts and the players alternate turns, a game ending is represented as a sequence of integers corresponding to grid positions chosen by the players at each turn. With this representation, the possible tic-tac-toe game endings are the permutations of {1, 2, 3, 4, 5, 6, 7, 8, 9}; they are all valid by construction.

n = 3;

t = Riffle[Array["X" &, Ceiling[n^2/2]], Array["O" &, Floor[n^2/2]]];
won = 0;
draw = 0;
lost = 0;
total = 0;

Do[
    s = Array["-" &, 9];
    d = 1;
    b = False;

    While[d <= n^2 && !b,
        s[[i[[d]]]] = t[[d]];

        If[TTTWinner[s, t[[d]]],
            If[OddQ[d], won++, lost++];
            b = True;
        ];

        d++;
    ];

    If[!b, draw++];

, {i, Permutations[Range[9]]}
];

won
draw
lost
won + draw + lost

However, this is an overestimate of the number of "actual" games, because two game endings can map to the same game, e.g., {1, 2, 3, 4, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 5, 6, 7, 9, 8} (X has already won by the 7th turn). To get the right numbers, the rest of a permutation is dropped whenever one of the players wins, e.g., {1, 2, 3, 4, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 5, 6, 7, 9, 8} would both map to {1, 2, 3, 4, 5, 6, 7} and X wins a single game instead of two.

n = 3;

t = Riffle[Array["X" &, Ceiling[n^2/2]], Array["O" &, Floor[n^2/2]]];
won = 0;
draw = 0;
lost = 0;
total = 0;

Clear[h];
h[_] := False;

Do[
    s = Array["-" &, 9];
    d = 1;
    b = False;

    While[d <= n^2 && !b,
        s[[i[[d]]]] = t[[d]];

        If[TTTWinner[s, t[[d]]],
            If[!h[Take[i, d]],
                h[Take[i, d]] = True;
                If[OddQ[d], won++, lost++];
            ];
        
            b = True;
        ];

        d++;
    ];

    If[!b, draw++];

, {i, Permutations[Range[9]]}
];

won
draw
lost
won + draw + lost

The numbers can be verified at the Wikipedia article.

Johnaudi · March 31 2014

Here's what the OP requested me to do:

static void Main(string[] args)
        {
            string board = "";

            refreshGrid();

            while (true)
            {
                try {
                    Console.WriteLine();

                    string[] r = Console.ReadLine().Split(' ');

                    board = addXOPos(r[0][0], Convert.ToInt32(r[1]), board);
                    refreshGrid(board);

                    Console.WriteLine();
                } catch {}
            }

        }

        public static string addXOPos(char _char, int _pos, string _mstr)
        {
            if (_char != 'X' && _char != 'O')
            {
                return _mstr;
            }

            if (_mstr.Length != 9) _mstr = "---------";

            char[] _mchar = _mstr.ToCharArray();

            if (_mstr[_pos - 1] != '-')
            {
                Console.WriteLine("Could not place in this area");

                return _mstr;
            }
            else
            {
                _mchar[_pos - 1] = _char;
            }

            foreach (char _c in _mchar) {
                if (_c != 'X' && _c != 'O' && _c != '-')
                {
                    Console.WriteLine("An error occured, let's just reset all!");
                    return "---------";
                }
            } return new string(_mchar);
        }

        public static void refreshGrid(string grid_data = "---------") {
            grid_data = grid_data.Substring(0, 9);

            int i = 0;

            Console.WriteLine("Loading grid...");

            foreach (char _o in grid_data)
            {
                if (i % 3 == 0) Console.Write("\n|---+---+---|\n|");

                switch (_o)
                {
                    case 'X':
                        Console.Write(" X |");
                        break;

                    case 'O':
                        Console.Write(" O |");
                        break;

                    default:
                        Console.Write(" - |");
                        break;        
                }

                i++;
            } Console.Write("\n|---+---+---|");

        }

I didn't quite focus on the system (player turns, AI, winners) but I guess you get the concept. (as it's easy to put an array of possible patterns etc)

LebGeeks

#1 November 5 2012