Help writing a game tree for tictactoe
-
can anyone help me design a game tree for tictactoe. i am trying to do the recursion for the AI of the tictactoe and i cant seem to get it write. i decided to write the game tree 1st but i can figure out how to write it. can anyone kindly help me do that? anyways, thank you very much.
-
can anyone help me design a game tree for tictactoe. i am trying to do the recursion for the AI of the tictactoe and i cant seem to get it write. i decided to write the game tree 1st but i can figure out how to write it. can anyone kindly help me do that? anyways, thank you very much.
First of all...whats a game tree...? Is this like a flowchart or something...? What AI are you having problems with...determining a win with the active player or the computer making it's moves..? Recursion will make your game logic IMO doubly hard...a simple double iteration loop would look much nicer on the eyes. Depending on how many times your recursion function is called, this could be very in-efficient. Unless i'm missing something...each time a function is called it pushe s it's params and locals onto a lifo stack, this could cause your stack to grow quite large i'd think. Can you do it with a loop or MUST you use recursion...? "An expert is someone who has made all the mistakes in his or her field" - Niels Bohr
-
First of all...whats a game tree...? Is this like a flowchart or something...? What AI are you having problems with...determining a win with the active player or the computer making it's moves..? Recursion will make your game logic IMO doubly hard...a simple double iteration loop would look much nicer on the eyes. Depending on how many times your recursion function is called, this could be very in-efficient. Unless i'm missing something...each time a function is called it pushe s it's params and locals onto a lifo stack, this could cause your stack to grow quite large i'd think. Can you do it with a loop or MUST you use recursion...? "An expert is someone who has made all the mistakes in his or her field" - Niels Bohr
umm... i dont really have to do it using recursions. i am just practicing it for fun. oh a game tree is like a family with all the possible moves that can happen when playing tictactoe. i got my algorithm already just that i am having a harding trying to figure out how to evaluate the players moves then return the best move the computer can move. i was going to implement that by looking at a game tree but i can figure out how to write one. oh, i am trying to determine how the computer will move on the board after the player has moved. i made the computer as the 1st one to move as default. here is my algorithm: Const int MAXDEPTH = 9; CheckForMoves() If Board is all Occupied or Player Won or Depthcount > MAXDEPTH - return. Else - DepthCount++; - GetPlayerMove(row & column); - Evaluate Player Move and return the best move the computer can take. If the Move the computer has made is a good move and The Board Cell is empty. - Computer makes the move Else - CheckForMoves() <-- Check for moves I am getting a hard time trying to figure out how to evaluate the player move and how to make it return the best possible move and also how to check if the move done is a good move. well, if you guys think my algorithm logic is wrong let me know. and if so can you tell me a better algorithm to implement it :) thank you very much...
-
umm... i dont really have to do it using recursions. i am just practicing it for fun. oh a game tree is like a family with all the possible moves that can happen when playing tictactoe. i got my algorithm already just that i am having a harding trying to figure out how to evaluate the players moves then return the best move the computer can move. i was going to implement that by looking at a game tree but i can figure out how to write one. oh, i am trying to determine how the computer will move on the board after the player has moved. i made the computer as the 1st one to move as default. here is my algorithm: Const int MAXDEPTH = 9; CheckForMoves() If Board is all Occupied or Player Won or Depthcount > MAXDEPTH - return. Else - DepthCount++; - GetPlayerMove(row & column); - Evaluate Player Move and return the best move the computer can take. If the Move the computer has made is a good move and The Board Cell is empty. - Computer makes the move Else - CheckForMoves() <-- Check for moves I am getting a hard time trying to figure out how to evaluate the player move and how to make it return the best possible move and also how to check if the move done is a good move. well, if you guys think my algorithm logic is wrong let me know. and if so can you tell me a better algorithm to implement it :) thank you very much...
AI for tic tac toe can be anything from simple as hell and fairly complex. 1) This simplest method of AI is to just iterate the array gameboard and check for NULL's, the first NULL = empty space which means...the computer should pick this spot. Of course this doesn't leave for very interesting game play (not that tic tac toe would or could) 1) To spice things up a little you could add some more advanced AI and do something like...instead of take the first available spot...search the game board for a potential opponent win and fill that gap before they do, I think this would work best if the computer started second. 2) Then you could use a game tree (i'd never heard of that before). Something I was attempting to do in my comp sci class was actually dynamically store players moves in a db while executing and use this growing db as a method of choosing the next mostly likely win-win scenerio. The second approach would best be suited for the computer if it starts second...but would provide night and day difference in AI... If you sit down and think about it for a sec or two you'd probably think of a better way of doing this, but heres just a quick idea on how to implement this. char move[9]; Then create an array of move's (tree) initialized with X and O's in different places. Use this tree to choose your next move. The one downside to this method (which I just realised while writting this... ;P is that you'd need one 'move' for each possible scenerio...to be able to use this method effectively...thats a whole lot of move[n]={X,O,O,X,O,X,X,O...} This is only one possible solution to a problem which has many. "An expert is someone who has made all the mistakes in his or her field" - Niels Bohr
-
AI for tic tac toe can be anything from simple as hell and fairly complex. 1) This simplest method of AI is to just iterate the array gameboard and check for NULL's, the first NULL = empty space which means...the computer should pick this spot. Of course this doesn't leave for very interesting game play (not that tic tac toe would or could) 1) To spice things up a little you could add some more advanced AI and do something like...instead of take the first available spot...search the game board for a potential opponent win and fill that gap before they do, I think this would work best if the computer started second. 2) Then you could use a game tree (i'd never heard of that before). Something I was attempting to do in my comp sci class was actually dynamically store players moves in a db while executing and use this growing db as a method of choosing the next mostly likely win-win scenerio. The second approach would best be suited for the computer if it starts second...but would provide night and day difference in AI... If you sit down and think about it for a sec or two you'd probably think of a better way of doing this, but heres just a quick idea on how to implement this. char move[9]; Then create an array of move's (tree) initialized with X and O's in different places. Use this tree to choose your next move. The one downside to this method (which I just realised while writting this... ;P is that you'd need one 'move' for each possible scenerio...to be able to use this method effectively...thats a whole lot of move[n]={X,O,O,X,O,X,X,O...} This is only one possible solution to a problem which has many. "An expert is someone who has made all the mistakes in his or her field" - Niels Bohr