Topic awaiting preservation: Optimizing Tic-Tac-Toe logic

A friend of mine started a Comp.Sci program (I think) this year, and in one of his classes they have to recreate Tic-Tac-Toe in python. I'm going to assume of course everyone knows how the game is played (three in a row on a 3x3 grid.)

He showed me the code he was working on, which had a bunch of nested IF statements for the logic checking if a win case existed - I tried to think of a more optimized way of doing it.

My first attempt used a loop that checked for a vertical, horizontal or diagonal "win" pattern, but I realized there were only at most 8 cases to check for with a 3x3 grid.

That resulted in the following Javascript:

var map = [

 'X','O','X',

 'O','X','O',

 'X','X','O'

] // X wins on diagonal in this case



var result = false;



var isWin = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]];



function win(x) {

  var s = map[x[0]]+map[x[1]]+map[x[2]];

  return (s=='XXX'||s=='OOO');

}



for (var i=0; i<isWin.length; i++) {

  if (win(isWin[i])) {

    result = true;

  }

}



alert(result?'win':'no win');

After I did this of course, I figured some of the in-house code gurus might be able to show me up with some crazy two-liner that does the same thing ..So I'd be interested in hearing other peoples' thoughts.

It's little puzzles like this that I find interesting. "Try to find the pattern" and write an optimized routine for it. Of course, anyone familiar with the demo scene knows very well what I'm getting at

(Edited by Scott on 10-20-2004 02:22)

I think the best way to implement this would be to represent the board with a bitstring of length 9, with all squares taken by the player to (let's assume X) to be 1, and all other spaces 0. Then, each solution will also be a bitstring of length 9, with 1's where the proper spaces are to complete a row. And if (board & solution == solution) then that solution fufills the requirements, and the game is won. Note the bitwise AND, not a logical AND.

I think this algorithm would work, anyway. When I find the time, I'll test it.

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

Here is a tic tac toe in c++... C++ Help
maybe it helps....or not!

The only problem with the bitshifting method is there are 3 states for each square, blank, O, and X. But that was the first thing I thought about too .

Hmm. Just some brainstorming. It seems that if you add all the digits together in the win patterns you always get a multiple of three. I think that may be a key you just need to make sure all the variables are checked. Then again I can't get anything smaller than the code posted yet



.:[ Never resist a perfect moment ]:.

bitdamaged: If you look closely at the source provided by Scott, you'll see that he starts from a fulfilled map, thus each cell can be encoded on a single bit.

Scott: Actually your code is already extremely short. The only shorter thing I can think of is to replace the last for loop by :

for( var i=0; !(result=win(isWin[i])) && i<isWin.length; i++ );

And of course, if you don't fear the obfuscation, you can also remove the win() function and place its body directly the for loop, which gives:

for( var i=0; !(result=((s=map[isWin[i][0]]+map[isWin[i][1]]+map[isWin[i][2]])=='XXX'||s=='OOO')) && i<isWin.length; i++ );

And again you could go further and include the declaration of the isWin array in the for itself, which gives :

for( i=0; (isWin=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]) && !(result=((s=map[isWin[ i ][ 0 ]]+map[isWin[ i ][ 1 ]]+map[isWin[ i ][ 2 ]])=='XXX'||s=='OOO')) && i<isWin.length; i++ );



(Edited by poi on 10-20-2004 20:28)

True but in a real tic-tac-toe situation/program you wouldn't start with a fulfilled grid. You'd test after each move.

I think to really optimize the solution you need to find an algorithm as opposed to finding a better way to test the mapping.




.:[ Never resist a perfect moment ]:.

(Edited by bitdamaged on 10-20-2004 21:19)

I may be coming out of left field here, but with the whole bitwise testing...
With each move, one only needs to test whether that individual has a winning situation. In that case, each spot in the grid CAN be stored in a bit -- that is, that player has a marker there or not. The location of the other player's markers are of no consequence.

You'd need ten bitstrings: 1-Xs, 1-Os, 8-solutions.
The two player strings would then have to be checked, manipulated, and checked with each move.

I'm not trying to step on anybody's toes here. I'm trying to use this as a learning experience too. You three are infinately more knowledgable in this sort of thing than I am. If my thinking is outta whack, let me know.

quote:

---

bitdamaged said:

The only problem with the bitshifting method is there are 3
states for each square, blank, O, and X. But that was the first thing I
thought about too .

---

Mobrul hit it on the head. Basically, since a tic-tac-toe board is TINY (we're talking a short int here), there is no consequence in storing two boards: one for where X has pieces, one for where O has pieces. If you feel like it, go ahead and add a third board for where any player has pieces, it makes it easier to find when the game is over.

"Any sufficiently advanced technology is indistinguishable from magic." -- Arthur C. Clarke
"Any sufficiently arcane magic is indistinguishable from technology." -- P. David Lebling

quote:

---

bitdamaged said:

True but in a real tic-tac-toe situation/program you wouldn't start with a fulfilled grid. You'd test after each move.I think to really optimize the solution you need to find an algorithm as opposed to finding a better way to test the mapping. .:[ Never resist a perfect moment ]:.

---

Agreed on the latter point. The algorithm is what I was wondering about; ie. finding a pattern that can be exploited to efficiently determine the win cases.

The grid would be empty to start of course, but could be tested after each move without having been "fulfilled" using * instead of X or O to represent "empty" etc. Granted you'd be still checking all possible win cases even though the routine could be modified to exclude any that involve empty grid spaces, but then that'd bloat the code for what I see as little benefit - I wouldn't consider this to be too processor intensive anyways

(Edited by Scott on 10-21-2004 02:43)

you could probably not store some of the win cases by representing them as bit shifted variants of other win cases.

Actually the solution evoked by mobrul sounds really good. Using one bit-field variable per player to store the positions they hold. Mix that with the binary AND win case check method proposed by Iron Wallaby to test if the bit-field of the current player matches a the bit-field of a win case and I think we've got a good candidate here.

Eventually, to go even faster, since there is only 8 possible win case the win check method can be hard coded and the loop unrolled to fit in a single line made that would look like :

playerWins = (playerBitField&17)==17 || (playerBitField&83)==83 || (playerBitField&213)==213 ..