Fastest way to generate next move in TIC TAC TOE game

Question

In a X's and 0's game (i.e. TIC TAC TOE(3X3)) if you write a program for this give a fast way to generate the moves by the computer. I mean this should be the fastest way possible.

All I could think of at that time is to store all the board configurations in a hash so that getting best position of move is a O(1) operation.
Each board square can be either 0,1, or 2.
0 represents empty square. 1 represents a X & 2 represents 0.

So every square can be filled with either of the three. There are approx 3^9 board configurations.

In simple, we need a hash of size 3^9. For hashing,we can go for base 3 representation. Means each number in base 3 will be 9 digits long each digit corresponding to each square. To search in hash, we need to find the decimal representation of this 9 digit number. Now, each square can be associated with row number & column number. In order to identify each square uniquely, we can again make use of base 3 representation. say SQ[1][2] will be 12 in base 3 which is equivalent to 5 in decimal.

Thus, we have effectively designed an algorithm which is fast enough to calculate the next move in O(1).

But, the interviewer insisted in reducing the space complexity as DOS system doesn't have that much amount of memory.

How can we reduce the space complexity with no change in time complexity?
Please help me so that I do not miss such type of questions in the future.

Answer 1

The game of Tic Tac Toe is sufficiently simple that optimal algorithm may be implemented by a machine built from Tinker Toys (a brand of sticks and fasteners). Since the level of hardware complexity encapsulated by such a construction is below that of a typical 1970's microprocessor, the time required to find out what moves have been made would in most cases exceed the time required to figure out the next move. Probably the simplest approach would be have a table which, given the presence or absence of markers of a given player (2^9, or 512 entries), would indicate what squares would turn two-in-a-rows into three-in-a-rows. Start by doing a lookup with the pieces owned by the player on move; if any square which would complete a three-in-a-row is not taken by the opponent, take it. Otherwise look up the opponent's combination of pieces; any square it turns up that isn't already occupied must be taken. Otherwise, if the center is available, take it; if only the center is taken, take a corner. Otherwise take an edge.

It might be more interesting to open up your question to 4x4x4 Tic Tac Toe, since that represents a sufficient level of complexity that 1970's-era computer implementations would often take many seconds per move. While today's computers are thousands of times faster than e.g. the Atari 2600, the level of computation at least gets beyond trivial.

If one extends the game to 4x4x4, there will be many possibilities for trading off speed, RAM, and code space. Unlike the original game which has 8 winning lines, the 4x4x4 version has (IIRC) 76. If one keeps track of each line as being in one of 8 states [ten if one counts wins], and for each vacant square one keeps track of how many of the winning lines that pass through it are in what states, it should be possible to formulate some pretty fast heuristics based upon that information. It would probably be necessary to use an exhaustive search algorithm to ensure that heuristics would in fact win, but once the heuristics were validated they should be able to run much faster than would an exhaustive search.

Answer 2

The assumption of 3^9 is wrong. This would include for example a board that only has X which is impossible as both players place each turn an X or an O.

My initial thought was that there are (9*8*7*6*5*4*3*2) * 2 possibilities. First player has 9 choices, second player has 8 choices, first player has 7 etc. I put * 2 because you might have different best moves depending who starts.

Now 3^9 is 19863 and 9! is 362880, so clearly this is not the superior solution, a lot of 'different scenarios' actually will end up looking exactly the same. Still, the base idea that many of the 19863 board setups are invalid remain.

This piece of code which probably could be replaced by a simple formula tells me that this is the count of positions you want to have a move for.

<script>

a = permuteString( "X........" ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XO......." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOX......" ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXO....." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOX...." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOXO..." ); document.write( Object.keys(a).length + "<br>" );console.log( a );
a = permuteString( "XOXOXOX.." ); document.write( Object.keys(a).length + "<br>" );console.log( a );

//Subset of the Array.prototype.slice() functionality for a string
function spliceString( s , i )
{
    var a = s.split("");
  a.splice( i , 1 );
    return a.join("");
}

//Permute the possibilities, throw away equivalencies
function permuteString( s )
{
    //Holds result
    var result = {};

    //Sanity
    if( s.length < 2 ) return [];

    //The atomic case, if AB is given return { AB : true , BA : true }
    if( s.length == 2 )
    {
        result[s] = true;
        result[s.charAt(1)+s.charAt(0)] = true;
        return result;
    }

    //Enumerate
    for( var head = 0 ; head < s.length ; head++ )
    {
        var o = permuteString( spliceString( s , head  ) );
        for ( key in o )
            result[ s.charAt( head ) + key ] = true;
    }
    return result;
}


</script>

This gives the following numbers: 1st move : 9 2nd move : 72 3rd move : 252 4th move : 756 5th move : 1260 6th move : 1680 7th move : 1260

So in total 5289 moves, this is without even checking for already finished games or symmetry.

These numbers allow you to lookup a move through an array, you can generate this array yourself by looping over all possible games.

T.

Answer 3

For a small game like this, a different way of going about this is to pre-compute and store the potential game tree in a table.

Looking first at the situation where the human starts, she obvious has 9 different start positions. A game-play table would contain 9 entry points, then, each pointing to the correct response - you could use the guidelines outlined in this question to calculate the responses - as well as the next level table of human responses. This time there are only 7 possible responses. For the next level there'll be 5, then 3, then just 1. In total, there will be 9 * 7 * 5 * 3 * 1 = 945 entries in the table, but that can be compressed by realizing symmetries, i.e. rotations and flipped colors.

Of course, the situation where the computer starts is similar in principle but the table is actually smaller because the computer will probably want to start by playing the middle piece - or at least avoid certain spots.

Answer 4

There are not 3^9 different board configurations. Just as tomdemuyt says, there are 9! different board configurations, i.e., 9 choices at first, 8 choices next, 7 choices after that, and so on.

Also, we can further reduce the space complexity by accounting for symmetry. For example, for the first move, placing an X in [0,0] is the same as placing it in [0,2], [2,0], and [2,2]. I believe this reduces 9! to 9!/4

We can even reduce that by accounting for which board configurations were winning before the final move (the 9th move). I don't know the number, but a detailed explanation can be found on the Stack Overflow cousin http://en.wikipedia.org/wiki/Tic-tac-toe