21 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
Tic-Tac-Toe
September 29, 2003 04:49 PM
What would be a good way to go about making an AI for a Tic-Tac-Toe game? Any pseudo code or explanation of an algorithm or links would be appriciated
Thx in advnace
"Everything that can be invented has been invented."
-Charles H. Duell, Commissioner, U.S. Office of Patents, 1899.
211
September 29, 2003 05:06 PM
Try searching for minimax search. It is also referred to as minmax, mini-max and min-max. One url: http://ai-depot.com/LogicGames/MiniMax.html
There are many more sights with info available. Many introductory AI books focus on the use of this algorithm with tic-tac-toe.
There are many more sights with info available. Many introductory AI books focus on the use of this algorithm with tic-tac-toe.
Syntax without semantics is meaningless.
September 29, 2003 05:49 PM
Also, the much overlooked "Articles & Resources" link at the top of this page.
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
Dave Mark - President and Lead Designer
Intrinsic Algorithm - "Reducing the world to mathematical equations!"
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC
Professional consultant on game AI, mathematical modeling, simulation modeling
Co-founder and 10 year advisor of the GDC AI Summit
Author of the book, Behavioral Mathematics for Game AI
Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play
"Reducing the world to mathematical equations!"
September 30, 2003 08:15 AM
Thanks,
InnocuousFox, I already checked, but nothing specific to what I''m doing and way more advanced than what I need.
InnocuousFox, I already checked, but nothing specific to what I''m doing and way more advanced than what I need.
122
October 01, 2003 09:53 PM
you will probably have to use the A* algorithm, it is a path finding algorithm which can simulate intelligence among the monsters. from what i have read, it is realy efficient.
cheers
cheers
141
October 04, 2003 10:17 PM
im not an advanced programmer, but i think that you could try to make it like an state diagram. Also im not an advanced TicTacToe player, but i know how to play it =P
ie
If PC has Tic_Tac (so its missing the Toe =P, two X's and the third spot open) -> play that spot to win (obvious)
else
If User has Tic_Tac -> play that spot to prevent him from winning. (obvious)
else
* check Future_Loss
** Future_Loss, Defend.
** no Future_Loss, Attack.
endif
endif
Thus you could make the function Tic_Tac to check if theres a Tic_Tac going on, then return, whos having the Tic_Tac and play (PC's offense should have priority since if it goes for it, it wins)
This is the easy part...
If theres no Tic_Tac, then the PC must check for Future_Lose (so, try not to fall on tricks like giving the User two possible lines to make, wich is to lose), if theres a Future_Lose then it must go stop it, else it will try to go offensively...
To know where to go, you should just make different games of tic-tac-toes on paper and check what are the best positions and "strategies" (they cant be many...), so you can include them on your looking for info functions...
Now, will the user be always first?, if the PC can go first then you could start it with a random position (though im not sure if there are positions where the first move shouldnt go... im no expert playing tictactoe =P)
the number of possibilities are 9! if im not wrong, but it is actually less than that, since ppl must try not to be defeated and thus they will apply the Tic_Tac part...
i will think about the Defend and Attack parts =P ill edit/post later (picks pen and paper =P)
ok i figured the following, you could do it this way (using pen and paper and trying to get the rules for your state diagram), or you could try some more "intelligent" AI that would be useful for example... for a 4x4 tetris board...
you could scan all possible lines in the map, there are 8. Then think on all the possible moves and then choose among the best (if there are many that have the same result)
States for the first round:
when checking for Future_Loss, we will cancel some possible moves, because they will/would end making the PC lose if the User plays well.
If PC_first_turn, and user already has middle (2,2), PUT in corner, DO NOT put in cardinal (if you take any cardinal point, you will enter into Future_Loss and you do not want that...), random corner of course...
if PC_first_turn and user has corner, DO NOT put in middle, DO NOT put in opposite corner, DO NOT put nonadyacent cardinal, DO NOT put in nonopposite corner, DO NOT put in adyacent cardinal =P, so -> PC loses, thus put anywhere... (you could use a random number to decide, because there are positions that are harder to figure out a way of winning, though the user can always win easily, he just have to figure it out)
if PC_first_turn, and user has cardinal point, PUT in middle, PUT in adyacent corner, DO NOT PUT in nonopposite cardinal, PUT in opposite cardinal, DO NOT PUT in nonadyacent corner.
(These can be applied to the User if he goes second...)
Using these, we can see, that, if PC is first, and now it is its second turn, and user took one of the DO NOT put sections on his turn, then the PC will win if it plays regularly.
If PC is second, and it is its first turn, it will not choose any of the DO NOT put, because the User has a chance of always win, if he plays perfectly. Unless the PC is set to have different difficulties, or not a "godlike" difficulty, then this should be used, otherwise, you could choose to use a random number to know if the PC will make a smart move or not.
If PC is second, it will not win unless the User makes a mistake, so when deciding its first move, it can choose from any of the PUT sections available.
If PC is first..., well, it just have to choose a corner..., to let the User be able to win, you could use the random numbers i said before.., at least to give the PC very low chances of selecting a corner as its first move...
then you should check the states for round 2, and so on... the game is decided after round 3, at least from what i have been playing =P
[edited by - giaym on October 4, 2003 12:24:41 AM]
[edited by - giaym on October 4, 2003 12:33:30 AM]
ie
If PC has Tic_Tac (so its missing the Toe =P, two X's and the third spot open) -> play that spot to win (obvious)
else
If User has Tic_Tac -> play that spot to prevent him from winning. (obvious)
else
* check Future_Loss
** Future_Loss, Defend.
** no Future_Loss, Attack.
endif
endif
Thus you could make the function Tic_Tac to check if theres a Tic_Tac going on, then return, whos having the Tic_Tac and play (PC's offense should have priority since if it goes for it, it wins)
This is the easy part...
If theres no Tic_Tac, then the PC must check for Future_Lose (so, try not to fall on tricks like giving the User two possible lines to make, wich is to lose), if theres a Future_Lose then it must go stop it, else it will try to go offensively...
To know where to go, you should just make different games of tic-tac-toes on paper and check what are the best positions and "strategies" (they cant be many...), so you can include them on your looking for info functions...
Now, will the user be always first?, if the PC can go first then you could start it with a random position (though im not sure if there are positions where the first move shouldnt go... im no expert playing tictactoe =P)
the number of possibilities are 9! if im not wrong, but it is actually less than that, since ppl must try not to be defeated and thus they will apply the Tic_Tac part...
i will think about the Defend and Attack parts =P ill edit/post later (picks pen and paper =P)
ok i figured the following, you could do it this way (using pen and paper and trying to get the rules for your state diagram), or you could try some more "intelligent" AI that would be useful for example... for a 4x4 tetris board...
you could scan all possible lines in the map, there are 8. Then think on all the possible moves and then choose among the best (if there are many that have the same result)
States for the first round:
when checking for Future_Loss, we will cancel some possible moves, because they will/would end making the PC lose if the User plays well.
If PC_first_turn, and user already has middle (2,2), PUT in corner, DO NOT put in cardinal (if you take any cardinal point, you will enter into Future_Loss and you do not want that...), random corner of course...
if PC_first_turn and user has corner, DO NOT put in middle, DO NOT put in opposite corner, DO NOT put nonadyacent cardinal, DO NOT put in nonopposite corner, DO NOT put in adyacent cardinal =P, so -> PC loses, thus put anywhere... (you could use a random number to decide, because there are positions that are harder to figure out a way of winning, though the user can always win easily, he just have to figure it out)
if PC_first_turn, and user has cardinal point, PUT in middle, PUT in adyacent corner, DO NOT PUT in nonopposite cardinal, PUT in opposite cardinal, DO NOT PUT in nonadyacent corner.
(These can be applied to the User if he goes second...)
Using these, we can see, that, if PC is first, and now it is its second turn, and user took one of the DO NOT put sections on his turn, then the PC will win if it plays regularly.
If PC is second, and it is its first turn, it will not choose any of the DO NOT put, because the User has a chance of always win, if he plays perfectly. Unless the PC is set to have different difficulties, or not a "godlike" difficulty, then this should be used, otherwise, you could choose to use a random number to know if the PC will make a smart move or not.
If PC is second, it will not win unless the User makes a mistake, so when deciding its first move, it can choose from any of the PUT sections available.
If PC is first..., well, it just have to choose a corner..., to let the User be able to win, you could use the random numbers i said before.., at least to give the PC very low chances of selecting a corner as its first move...
then you should check the states for round 2, and so on... the game is decided after round 3, at least from what i have been playing =P
[edited by - giaym on October 4, 2003 12:24:41 AM]
[edited by - giaym on October 4, 2003 12:33:30 AM]
122
October 14, 2003 05:54 PM
The way I have done it is much simpler (I think):
The concrete numbers for the weights are not based on any calculations but they do work. Also the algortihm is not optimized but that's not needed for tic-tac-toe anyway.
1. give base weights to all cells.
center = 3
corner = 2
other = 1
already used cells = 0
2.
3. make your move to the cell with the largest weight.
-----
Because all of the rows are checked in every turn and one cell can be part of 2-4 rows, the weights to the cells are added cumulatively. That way the algorithm takes into account every effect that the move will have.
This AI would never lose though so you might want to add some dumbness.
[edited by - Erkki on October 14, 2003 6:54:56 PM]
[edited by - Erkki on October 14, 2003 6:55:51 PM]
[edited by - Erkki on October 14, 2003 6:56:28 PM]
The concrete numbers for the weights are not based on any calculations but they do work. Also the algortihm is not optimized but that's not needed for tic-tac-toe anyway.
1. give base weights to all cells.
center = 3
corner = 2
other = 1
already used cells = 0
2.
// (8 possible rows - 3 vertical, 3 horizontal, 2 diagonal)for i = firstRow to lastRow{ // check all cells in that row for j = 0 to 2 { // if cell is empty if weight(i,j) > 0 { ownCount = count own's marks in the current row oppCount = count opponent's marks in the current row // There can be a total of 0, 1 or 2 marks in the row because we know that one cell is empty if (ownCount = 0 and oppCount = 1) weight(i,j) += 1 // prefer rows that block opponent if (ownCount = 1 and oppCount = 0) weight(i,j) += 2 // prefer more rows that help you win if (ownCount = 2) weight(i,j) += 50 // to win if (oppCount = 2) weight(i,j) += 10 // to block the opponent's win } }} 3. make your move to the cell with the largest weight.
-----
Because all of the rows are checked in every turn and one cell can be part of 2-4 rows, the weights to the cells are added cumulatively. That way the algorithm takes into account every effect that the move will have.
This AI would never lose though so you might want to add some dumbness.
[edited by - Erkki on October 14, 2003 6:54:56 PM]
[edited by - Erkki on October 14, 2003 6:55:51 PM]
[edited by - Erkki on October 14, 2003 6:56:28 PM]
208
October 15, 2003 03:02 PM
I programmed a TicTacToe game a while ago. It worked reasonably well but my design plan was flawed... First what i did was that I would get the computer to calculate the probability of it winning the game assuming the opponent would choose a random square.
It wasn't easy to program, but i got it working in the end... It worked relatively well, it always selected the 3rd square if it already had 2 in a row, it always started by choosing the middle square to start off with (even know i hadn't told it to do that specifically, it just worked out that statistically that was the best chance of winning). It did some strange stuff sometimes though, like if i had 2 squares in a row he wouldn't block me from getting the 3rd.
The reason for this was that it would only calculate the probability of it WINNING the game, it didn't care about losing. Obviously if it lost the game, that gives him a 0% chance of winning, but as far as the computer was concerned drawing the game or losing was the same to him.
So then i thought, ok what if I do the opposite... I made it so that it would calculate the probability of it losing the game, and then make it choose the path the one with the lowest probability... This seemed to work better, i.e. It would never lose a game... but on some occasions it didn't take the path that would lead to victory.
So in the end i tried to combine the two by subtracting the lose probability from the win probability.. which seems to work pretty much perfectly..
Here is the source code (sorry if i'm not supposed to do this cause its quite long :/)
It wasn't easy to program, but i got it working in the end... It worked relatively well, it always selected the 3rd square if it already had 2 in a row, it always started by choosing the middle square to start off with (even know i hadn't told it to do that specifically, it just worked out that statistically that was the best chance of winning). It did some strange stuff sometimes though, like if i had 2 squares in a row he wouldn't block me from getting the 3rd.
The reason for this was that it would only calculate the probability of it WINNING the game, it didn't care about losing. Obviously if it lost the game, that gives him a 0% chance of winning, but as far as the computer was concerned drawing the game or losing was the same to him.
So then i thought, ok what if I do the opposite... I made it so that it would calculate the probability of it losing the game, and then make it choose the path the one with the lowest probability... This seemed to work better, i.e. It would never lose a game... but on some occasions it didn't take the path that would lead to victory.
So in the end i tried to combine the two by subtracting the lose probability from the win probability.. which seems to work pretty much perfectly..
Here is the source code (sorry if i'm not supposed to do this cause its quite long :/)
#include <iostream.h>#include <time.h>#include <stdlib.h>void ShowBoard(int iBoard[3][3], int iWin = 0);void Play(int iBoard[3][3], int iTurn);void CPUPlay(int iBoard[3][3], int iTurn, int iSkill);double WinProb(int iBoard[3][3], int iTurn, int iPlayer);int CheckWin(int iBoard[3][3]);int CheckDraw(int iBoard[3][3]);int main(){ int iBoard[3][3]; int iTurn = 1; int iWin; int iDraw; int iPlayer[2]; // Skill: 0 - player, 1 - random, 2 - offensive, 3 - defensive, 4 - neutral iPlayer[0]=0; iPlayer[1]=4; srand( (unsigned)time( NULL ) ); for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { iBoard[j]=0;<br> }<br> }<br> while (true)<br> {<br> if (iPlayer[iTurn-1]==0)<br> {<br> Play(iBoard, iTurn);<br> }<br> else<br> {<br> CPUPlay(iBoard, iTurn, iPlayer[iTurn-1]);<br> }<br> if (iWin = CheckWin(iBoard))<br> {<br> ShowBoard(iBoard, iWin);<br> return 0;<br> }<br> if (iDraw = CheckDraw(iBoard))<br> {<br> ShowBoard(iBoard, 3);<br> return 0;<br> }<br> if (iTurn==1)<br> iTurn=2;<br> else<br> iTurn=1;<br> }<br> return 0;<br>}<br><br>void ShowBoard(int iBoard[3][3], int iWin)<br>{<br> cout << " a b c" << endl;<br> cout << " /—–\\" << endl;<br> for (int i=0; i<3; i++)<br> {<br> cout << (char)(i + '1');<br> for (int j=0; j<3; j++)<br> {<br> cout << "|" ;<br> switch (iBoard[j])<br> {<br> case 0:<br> cout << " ";<br> break;<br> case 1:<br> cout << "X";<br> break;<br> case 2:<br> cout << "O";<br> break;<br> }<br> }<br> cout << "|" << endl;<br> }<br> cout << " \\—–/" << endl;<br> if (iWin==3)<br> {<br> cout << "The Match is a Draw";<br> }<br> else if (iWin)<br> {<br> cout << "Player " << (char)(iWin + '0') << " Wins";<br> }<br> for (int cnt = 0; cnt < 18; cnt++)<br> {<br> cout << endl;<br> }<br> return;<br>}<br><br>void Play(int iBoard[3][3], int iTurn)<br>{<br> char szInput[ 8 ] = "";<br> int i, j;<br> while (true)<br> {<br> while (szInput[0] < '1' || szInput[0] > '3' || szInput[1] < 'a' || szInput[1] > 'c')<br> {<br> ShowBoard(iBoard);<br> cin >> szInput;<br> }<br> i = szInput[0] - '1';<br> j = szInput[1] - 'a';<br> if (!iBoard[j])<br> {<br> break;<br> }<br> else<br> {<br> szInput[0] = 0;<br> szInput[1] = 0;<br> }<br> }<br> iBoard[j] = iTurn;<br> return;<br>}<br><br>void CPUPlay(int iBoard[3][3], int iTurn, int iSkill)<br>{<br> int i,j;<br> int iBest = 0;<br> int jBest = 0;<br> double dBestProb = -1;<br> double dProb;<br> double dBestLoseProb = 2;<br> double dLoseProb;<br> int iNextTurn;<br> int iChecked = 0;<br><br> ShowBoard(iBoard);<br><br> if (iTurn==1)<br> iNextTurn=2;<br> else<br> iNextTurn=1;<br><br> do<br> {<br> i = rand()*3/0x7fff;<br> j = rand()*3/0x7fff;<br> if (iChecked&(1<<(i+j*3)))<br> {<br> continue;<br> }<br> if (!iBoard[j])<br> {<br> if (iSkill==1)<br> {<br> iBest = i;<br> jBest = j;<br> break;<br> }<br> if (iSkill==2)<br> {<br> iBoard[j] = iTurn;<br> dProb = WinProb(iBoard, iNextTurn, iTurn);<br> if (dProb > dBestProb)<br> {<br> dBestProb = dProb;<br> iBest = i;<br> jBest = j;<br> }<br> iBoard[j] = 0;<br> }<br> if (iSkill==3)<br> {<br> iBoard[j] = iTurn;<br> dLoseProb = WinProb(iBoard, iNextTurn, iNextTurn);<br> if (dLoseProb < dBestLoseProb)<br> {<br> dBestLoseProb = dLoseProb;<br> iBest = i;<br> jBest = j;<br> }<br> iBoard[j] = 0;<br> }<br> if (iSkill==4)<br> {<br> iBoard[j] = iTurn;<br> dProb = WinProb(iBoard, iNextTurn, iTurn);<br> dLoseProb = WinProb(iBoard, iNextTurn, iNextTurn);<br> dProb -= dLoseProb;<br> if (dProb > dBestProb)<br> {<br> dBestProb = dProb;<br> iBest = i;<br> jBest = j;<br> }<br> iBoard[j] = 0;<br> }<br> }<br> iChecked |= (1<<(i+j*3));<br> }<br> while (iChecked != ((1<<0)|(1<<1)|(1<<2)|(1<<3)|(1<<4)|(1<<5)|(1<<6)|(1<<7)|(1<<8)));<br><br> iBoard[iBest][jBest] = iTurn;<br>}<br><br>double WinProb(int iBoard[3][3], int iTurn, int iPlayer)<br>{<br> int iWin;<br> int iFreeSpaces = 0;<br> int iWinSpaces = 0;<br> int iLoseSpaces = 0;<br> double dWinProb = 0;<br> int iNextTurn;<br><br> if (iTurn==1)<br> iNextTurn=2;<br> else<br> iNextTurn=1;<br><br> for (int i=0; i<3; i++)<br> {<br> for (int j=0; j<3; j++)<br> {<br> if (!iBoard[j])<br> {<br> iFreeSpaces++;<br> iBoard[j]=iTurn;<br> iWin = CheckWin(iBoard);<br> if (iWin == iPlayer)<br> {<br> // CPU wins<br> iWinSpaces++;<br> }<br> else if (iWin)<br> {<br> // CPU loses<br> iLoseSpaces++;<br> }<br> else<br> {<br> // Game continues<br> dWinProb += WinProb(iBoard, iNextTurn, iPlayer);<br> }<br> iBoard[j]=0;<br> }<br> }<br> }<br> if (iFreeSpaces)<br> {<br> return (double(iWinSpaces)/double(iFreeSpaces)+dWinProb/double(iFreeSpaces));<br> }<br> return 0;<br>}<br><br>int CheckWin(int iBoard[3][3])<br>{<br> int i,j;<br> int iColor;<br> // horizontal<br> for (i=0; i<3; i++)<br> {<br> for (j=0; j<3; j++)<br> {<br> if (j==0 && iBoard[j])<br> {<br> iColor=iBoard[j];<br> }<br> else if (iColor==iBoard[j])<br> {<br> if (j==2)<br> {<br> return iColor;<br> }<br> }<br> else<br> {<br> break;<br> }<br> }<br> }<br> // vertical<br> for (i=0; i<3; i++)<br> {<br> for (j=0; j<3; j++)<br> {<br> if (j==0 && iBoard[j])<br> {<br> iColor=iBoard[j];<br> }<br> else if (iColor==iBoard[j])<br> {<br> if (j==2)<br> {<br> return iColor;<br> }<br> }<br> else<br> {<br> break;<br> }<br> }<br> }<br> // diagonal<br> i=0;<br> for (j=0; j<3; j++)<br> {<br> if (j==0 && iBoard[j])<br> {<br> iColor=iBoard[j];<br> }<br> else if (iColor==iBoard[j])<br> {<br> if (j==2)<br> {<br> return iColor;<br> }<br> }<br> else<br> {<br> break;<br> }<br> i++;<br> }<br> // diagonal<br> i=2;<br> for (j=0; j<3; j++)<br> {<br> if (j==0 && iBoard[j])<br> {<br> iColor=iBoard[j];<br> }<br> else if (iColor==iBoard[j])<br> {<br> if (j==2)<br> {<br> return iColor;<br> }<br> }<br> else<br> {<br> break;<br> }<br> i–;<br> }<br> return 0;<br>}<br><br>int CheckDraw(int iBoard[3][3])<br>{<br> for (int i=0; i<3; i++)<br> {<br> for (int j=0; j<3; j++)<br> {<br> if (!iBoard[j])<br> {<br> return 0;<br> }<br> }<br> }<br> return 1;<br>}<br><br> </pre> </i> <br><br><SPAN CLASS=editedby>[edited by - SpaceDude on October 15, 2003 4:05:14 PM]</SPAN> <br><br><SPAN CLASS=editedby>[edited by - SpaceDude on October 15, 2003 4:06:13 PM]</SPAN>This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement