﻿ Tic-Tac-Toe algorithm
25 May, 2013, 20:07:14
 OmnomIRC You must Register, be logged in and have at least 40 posts to use this shout-box! If it still doesn't show up afterward, it might be that OmnomIRC is disabled for your group or under maintenance.Note: You can also use an IRC client like mIRC, X-Chat or Mibbit to connect to an EFnet server and #omnimaga.

 Pages: [1]   Go Down
 Author Topic: Tic-Tac-Toe algorithm -  (Read 10548 times) 0 Members and 1 Guest are viewing this topic.
Xeda112358
Xombie. I am it.
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Last Login: 23 May, 2013, 22:01:23
Date Registered: 31 October, 2010, 08:46:36
Location: Land of Little Cubes and Tea, NY
Posts: 3760

Topic starter
Total Post Ratings: +610

 « on: 26 March, 2012, 17:43:57 » +3

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 :)
 TTTExample1.gif (128.07 KB, 192x128 - viewed 10786 times.) Logged

Latest update (possibly incomplete)
My pastebin
Spoiler for FileSyst:
FileSyst is an application that provides a folder and filesystem for the TI-83+/84+ calculators. It is designed to be easy to access and use in BASIC, and it can be used to access game files and save data, or to create a command prompt, among other things:

Spoiler for Graphiti:
This is a graph explorer for graph theory. It will require lots of work to finish. Currently you can:
Add edges (direction not shown, but they are directed)
Arrange vertices in a circle (in the future, you will be able to define levels of rings and the number of nodes in each)
Create complete graphs quickly

Plans:
Deleting edges
Multiple graphs support
Arrows for directed graphs
Planarity testing
Matrix operations
Weighted edges
Chromatic polynomials
Chromatic numbers

Spoiler for Stats:

Samocal             [o---------]
Virtual Processor   [o---------]
EnG                 [oo--------]
Grammer             [ooo-------]
AsmComp             [ooo-------]
Partex              [oooo------]
BatLib              [oooooooo--]
Grammer82           [----------]
Grammer68000        [----------]

Pseudonyms:  Zeda, Xeda, Thunderbolt
Languages:   English, français
Programming: z80 Assmebly
Grammer
TI-BASIC (83/84/+/SE, 89/89t/92)
Known For:   -Creator of the Grammer programming language
(Winning program of zContest2011)
-BatLib- One of the most feature packed libraries for BASIC programmers available
with over 100 functions and a simple programming language
-Learning to program z80 in hexadecimal before using an assembler (no computer was
available!)
╔═╦╗░╠═╬╣▒║ ║║▓╚═╩╝█

Deep Thought
So much to do, so much time, so little motivation

Online

Gender:
Date Registered: 19 May, 2009, 08:00:00
Location: The Universe
Posts: 7813

Total Post Ratings: +706

 « Reply #1 on: 26 March, 2012, 18:20:55 » 0

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
 Logged

Xeda112358
Xombie. I am it.
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Last Login: 23 May, 2013, 22:01:23
Date Registered: 31 October, 2010, 08:46:36
Location: Land of Little Cubes and Tea, NY
Posts: 3760

Topic starter
Total Post Ratings: +610

 « Reply #2 on: 26 March, 2012, 21:05:41 » 0

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
 « Last Edit: 26 March, 2012, 21:06:05 by Xeda112358 » Logged

Latest update (possibly incomplete)
My pastebin
Spoiler for FileSyst:
FileSyst is an application that provides a folder and filesystem for the TI-83+/84+ calculators. It is designed to be easy to access and use in BASIC, and it can be used to access game files and save data, or to create a command prompt, among other things:

Spoiler for Graphiti:
This is a graph explorer for graph theory. It will require lots of work to finish. Currently you can:
Add edges (direction not shown, but they are directed)
Arrange vertices in a circle (in the future, you will be able to define levels of rings and the number of nodes in each)
Create complete graphs quickly

Plans:
Deleting edges
Multiple graphs support
Arrows for directed graphs
Planarity testing
Matrix operations
Weighted edges
Chromatic polynomials
Chromatic numbers

Spoiler for Stats:

Samocal             [o---------]
Virtual Processor   [o---------]
EnG                 [oo--------]
Grammer             [ooo-------]
AsmComp             [ooo-------]
Partex              [oooo------]
BatLib              [oooooooo--]
Grammer82           [----------]
Grammer68000        [----------]

Pseudonyms:  Zeda, Xeda, Thunderbolt
Languages:   English, français
Programming: z80 Assmebly
Grammer
TI-BASIC (83/84/+/SE, 89/89t/92)
Known For:   -Creator of the Grammer programming language
(Winning program of zContest2011)
-BatLib- One of the most feature packed libraries for BASIC programmers available
with over 100 functions and a simple programming language
-Learning to program z80 in hexadecimal before using an assembler (no computer was
available!)
╔═╦╗░╠═╬╣▒║ ║║▓╚═╩╝█

nishtiman
LV0 Newcomer (Next: 5)

Offline

Last Login: 30 March, 2013, 16:27:28
Date Registered: 30 March, 2013, 16:23:53
Posts: 1

Total Post Ratings: 0

 « Reply #3 on: 30 March, 2013, 16:27:28 » 0

hi
but how can i find matlab code for this metod
 Logged
Xeda112358
Xombie. I am it.
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Last Login: 23 May, 2013, 22:01:23
Date Registered: 31 October, 2010, 08:46:36
Location: Land of Little Cubes and Tea, NY
Posts: 3760

Topic starter
Total Post Ratings: +610

 « Reply #4 on: 30 March, 2013, 17:47:25 » 0

I am not familiar with matlab, but does it allow for the following:
-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):
 12 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:
 12 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:
 12 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
 « Last Edit: 30 March, 2013, 17:50:18 by Xeda112358 » Logged

Latest update (possibly incomplete)
My pastebin
Spoiler for FileSyst:
FileSyst is an application that provides a folder and filesystem for the TI-83+/84+ calculators. It is designed to be easy to access and use in BASIC, and it can be used to access game files and save data, or to create a command prompt, among other things:

Spoiler for Graphiti:
This is a graph explorer for graph theory. It will require lots of work to finish. Currently you can:
Add edges (direction not shown, but they are directed)
Arrange vertices in a circle (in the future, you will be able to define levels of rings and the number of nodes in each)
Create complete graphs quickly

Plans:
Deleting edges
Multiple graphs support
Arrows for directed graphs
Planarity testing
Matrix operations
Weighted edges
Chromatic polynomials
Chromatic numbers

Spoiler for Stats:

Samocal             [o---------]
Virtual Processor   [o---------]
EnG                 [oo--------]
Grammer             [ooo-------]
AsmComp             [ooo-------]
Partex              [oooo------]
BatLib              [oooooooo--]
Grammer82           [----------]
Grammer68000        [----------]

Pseudonyms:  Zeda, Xeda, Thunderbolt
Languages:   English, français
Programming: z80 Assmebly
Grammer
TI-BASIC (83/84/+/SE, 89/89t/92)
Known For:   -Creator of the Grammer programming language
(Winning program of zContest2011)
-BatLib- One of the most feature packed libraries for BASIC programmers available
with over 100 functions and a simple programming language
-Learning to program z80 in hexadecimal before using an assembler (no computer was
available!)
╔═╦╗░╠═╬╣▒║ ║║▓╚═╩╝█

 Pages: [1]   Go Up