Tic-Tac-Toe algorithm

[Xeda112358]

A few are curious about my Tic-Tac-Toe algorithm, so here it is First, I would like to give credit as well to Michael Macie. We designed this last year for a linear algebra project and it is very beautiful indeed I have modified it a bit to make it work even better with matrix row operations.

First: In Tic-Tac-Toe, there are 9 positions and 8 wins. What we did is something that we have seen nowhere else and makes things amazingly less complex. As in, a child with rudimentary math skills might be able to get it. Each position we label as a to i like this:
a  b  c
d  e  f
g  h  i

We then assigned a matrix of win contributions to each position. I changed this to using a row of 8 elements. So, in my example, we can do:
[[D1,H1,H2,H3,V1,V2,V3,D2]] where D1 is the main diagonal, H1~H3 or horizontal wins, V1~V3 are vertical wins, and D2 is the other diagonal. If a position corresponds to a win, give it a 1, like so:

[a]=[[1,1,0,0,1,0,0,0]]
[b]=[[0,1,0,0,0,1,0,0]]
...
Et cetera. Now, reform this into a giant 9x8 matrix. This matrix remains constant. Here is where the actual algorithm come in :D Get ready...

Now, the game matrix starts clean, with 0s: [[0,0,0,0,0,0,0,0]]. These are the wins. Now, say player one selects position [a]. Add its matrix to the game matrix and you get [[1,1,0,0,1,0,0,0]]. Player two will subtract from the game matrix, so it tries to:
1) Make a -3
2) Make as many -2s as possible without leaving any 2s. If you leave 2 -2s, this will make a trap for next turn. If you leave a 2, then X will win next turn.
3) Make as many 2s into 1s if you cannot do any of that. Remember, a 2 now will turn into a 3 the next move and 3 means X got 3 in a row!

See how beautiful that is? For X, it follows the same algorithm, but use the negative of any of the numbers :) The really nice part is that:
-You can easily include random choices of moves  that fit the highest criterion.
-When the game is over, use the winning matrix and any 3s or -3s are wins, so you will know exactly where to strike through for wins!

Now, I would post my tic-tac-toe program, but I apparently never saved my final version (which was in english instead of french and had the bugs fixed). Instead, I will show you a screenie :)

[Deep Thought]

That is really clever. I think when people use lists (or matrices) for a Tic-Tac-Toe AI, each element represents a square, not a whole series of squares. (I know I didn't even start to think in that direction lol)

And on an unrelated note, those sprites are exactly the same as mine but stretched

[Xeda112358]

That is what makes this so beautiful :3 It is another way of looking at things Plus, I saw the link somebody posted to the wikipedia article, and this goes through that checklist super fast in only a few steps! All you need to do is row addition, then get the 10th column of the transpose (in TI-BASIC: Matr>List([A]^T,10,A to store it into list A). Then you check the list for the appropriate numbers

[nishtiman]

hi
i liked your view
but how can i find matlab code for this metod

[Xeda112358]

I am not familiar with matlab, but does it allow for the following:

• Vector Addition/Subtraction and indirection

-or-

• Matrix row operations

I would assume it had some way to do these. I did a quick search and you could probably do something like this:

First, review the following matrix rows of the form [[D1,H1,H2,H3,V1,V2,V3,D2]]
[a]=[[1,1,0,0,1,0,0,0]]
[b]=[[0,1,0,0,0,1,0,0]]
[c]=[[0,1,0,0,0,0,1,1]]
[d]=[[0,0,1,0,1,0,0,0]]
[e]=[[1,0,1,0,0,1,0,1]]
[f]=[[0,0,1,0,0,0,1,0]]
[g]=[[0,0,0,1,1,0,0,1]]
[h]=[[0,0,0,1,0,1,0,0]]
[i]=[[1,0,0,1,0,0,1,0]]
Then in MatLab you will want to define your matrix like this (from what I saw):

Code: Select All | Copy To Clipboard

1 2	A = [1,1,0,0,1,0,0,0; 0,1,0,0,0,1,0,0; 0,1,0,0,0,0,1,1; 0,0,1,0,1,0,0,0; 1,0,1,0,0,1,0,1; 0,0,1,0,0,0,1,0; 0,0,0,1,1,0,0,1; 0,0,0,1,0,1,0,0; 1,0,0,1,0,0,1,0; 0,0,0,0,0,0,0,0]

Notice that the last row is comprised of all zeros. This is the row holding all of the information about the moves taken in the game. From here, I cannot help much more (this is my first experience with MatLab), but from what I see, if the user selects a position a,b,c,d,e,f,g,h,i, that corresponds to rows 1,2,3,4,5,6,7,8,9 in the matrix. Where B is 1 or -1 depending on the turn (X or O) and C is the row:

Code: Select All | Copy To Clipboard

1 2	A(10,:) = A(10,:) + B*A(C,:)

And you might want to do something like this to signify that the move has already been selected:

Code: Select All | Copy To Clipboard

1 2	A(C,1) = .5

I have no clue if that works, but I was trying to set the first element in the row to .5. That way, you can just check if the first element is .5.

I have no clue what easy tricks or methods there are to test if an element in the last row is 2,-2, 3, or -3. In TI-BASIC, we can simply extract the last row as a list, then do something like '2=L1' and it returns a list of boolean values, 1 means the list element is 2, 0 means it wasn't. We could do sum(2=L1) and it will return 0 if no elements are 2, some other positive integer otherwise. I have no clue if anything like this can be done in MatLab, sorry

EDIT: Also, I would like to point out that you registered at 11:23:53. If that last digit was an 8, that would have been rather awesome o.o