🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Game trees
Author
Hey people,
Im implementing my first ever game-tree minimax algorithm to play a perfect game of tic-tac-toe / xs and os / whatever you want to call it.
Ive put it together in java to play against a human, but it doesnt seem to play a good game at all.
For example, if the human is about to win, it doesnt block. Shouldnt the minimax algorithm see that and play its move accordingly? I havnt put in any heuristics "like always block winning opponent moves", but i thought the minimax algorithm sorted that out.
Ofcourse, it could just be my buggy code...
Hope someone can help, Id post code, but Im not known around these parts and I think it would be a bit presumptuous!
Thanks,
Tim.
not all games end that way.
Are you forgetting that sometimes the computer could win if he and the opponent both have winning moves and its his turn. he would always block and the game would go to the cat. You need to have and lexical procedure to check one then the other. Just as humans do when choosing thier move. Trick is that humans do not always see their move correctly.
Are you forgetting that sometimes the computer could win if he and the opponent both have winning moves and its his turn. he would always block and the game would go to the cat. You need to have and lexical procedure to check one then the other. Just as humans do when choosing thier move. Trick is that humans do not always see their move correctly.
Wy not just make it a bunch of if statements?
May be inefficient, but it is tic tac toe.... Who cares about effienciency....
May be inefficient, but it is tic tac toe.... Who cares about effienciency....
Glad to see someone playing game trees. 
Here are a list of possible problems.
1. If the ''opponent'' has more than one win available (even if the wins occure a few moves away), then your minmax algorithm might not care anymore, because no matter where it goes it looses. Here is an example of the opposite:
. . .
. . .
o o .
It''s ''o''s move., and it chooses:
. . .
o . .
o o .
Why? Because of the order in which we generate moves, and because it''s still going to win. No matter what X does, O wins. Wierd, but true.. The work around is to give more current wins a higher score than future wins. (score = WIN_VALUE + (maxDepth - currDepth).
2. If you have any special conditions for ply 0, or you don''t bother exploring boards that already contain a win, you might be ''forgetting'' to pass that ''winning'' board up the tree. So maybe your minmax is choosing the right board, but your not taking that board and making it so. It''s happened to me before.
3. The opposite of 2. If you don''t specifically tell your tree to stop exploring a node if it contains a win, then your tree will continue on to Max_Depth, and may find a win for the other player! So, dont examine boards to ''max depth'' if they contain a win.
ie:
o . x
. o .
. . x
O to move and it pics
o . x
o o .
. . x
It assumes black will try to win, but in the next move o will win too. So black wins, you continue down the tree and find a win for o. O would like to take the win.
4. You have a bug in your code. MinMax is perfect, and if implemented correctly will always give you the right answer.
Hope this helps,
Will
Here are a list of possible problems. 1. If the ''opponent'' has more than one win available (even if the wins occure a few moves away), then your minmax algorithm might not care anymore, because no matter where it goes it looses. Here is an example of the opposite:
. . .
. . .
o o .
It''s ''o''s move., and it chooses:
. . .
o . .
o o .
Why? Because of the order in which we generate moves, and because it''s still going to win.
No matter what X does, O wins. Wierd, but true.. The work around is to give more current wins a higher score than future wins. (score = WIN_VALUE + (maxDepth - currDepth). 2. If you have any special conditions for ply 0, or you don''t bother exploring boards that already contain a win, you might be ''forgetting'' to pass that ''winning'' board up the tree. So maybe your minmax is choosing the right board, but your not taking that board and making it so. It''s happened to me before.
3. The opposite of 2. If you don''t specifically tell your tree to stop exploring a node if it contains a win, then your tree will continue on to Max_Depth, and may find a win for the other player! So, dont examine boards to ''max depth'' if they contain a win.
ie:
o . x
. o .
. . x
O to move and it pics
o . x
o o .
. . x
It assumes black will try to win, but in the next move o will win too. So black wins, you continue down the tree and find a win for o. O would like to take the win.
4. You have a bug in your code. MinMax is perfect, and if implemented correctly will always give you the right answer.
Hope this helps,
Will
Check the eval function.
A pretty standard evaluation function is:
MAX(n)=X(1)+10*X(2)+100*X(3)
MIN(n)=O(1)+10*O(2)+100*O(3)
where X(n) means there are ''n'' X''s in a particular line, with no ''O''s to block it (i.e. a possible winning row).
the same goes for O(n).
This way, the function gives extra importance to states where the distance to a terminal state is small (with exception of draw states).
I implemented this with the minimal look-ahead (i.e. only took the next opponent move into account) and it worked perfectly. (i.e. CPU never loses. Worst case is a draw).
A pretty standard evaluation function is:
MAX(n)=X(1)+10*X(2)+100*X(3)
MIN(n)=O(1)+10*O(2)+100*O(3)
where X(n) means there are ''n'' X''s in a particular line, with no ''O''s to block it (i.e. a possible winning row).
the same goes for O(n).
This way, the function gives extra importance to states where the distance to a terminal state is small (with exception of draw states).
I implemented this with the minimal look-ahead (i.e. only took the next opponent move into account) and it worked perfectly. (i.e. CPU never loses. Worst case is a draw).
Author
To everyone that replied,
many thanks.
Ill keep you posted on how I get on with that, and I''ll know in the future where to come to for AI advice.
Thanks,
Tim.
many thanks.
Ill keep you posted on how I get on with that, and I''ll know in the future where to come to for AI advice.
Thanks,
Tim.
Hey all, I just have a real quick question about a similar game tree design. I''m making a connect 4 game (just bigger tic-tac-toe). I was wondering how many moves ahead the tree should be built. I was thinking 4 (my current, player, mine, player). any suggestions??
--Ninj4D4n
--Ninj4D4n
Making it look an extra turn ahead should just be a case of changing a single number somewhere. If you can''t do that, then maybe your design needs to be rethought And if you can, the answer to your question is "as many as you want". The further it looks ahead, the better the choices made will be.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
And if you can, the answer to your question is "as many as you want". The further it looks ahead, the better the choices made will be. [ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
Right, i realize that the farter it looks the better, what i forgot to include is that there is a time restraint on the turn of the computer (1 min). So i was wondering if i should limit the looks to say 4 or 6 turns... or should i just use a timer.. and go as far as i can in say 50 secs??
Just search until your time runs out. Of course, you may want to alter the algorithm to make optimal use of your limited time, since the last ply is unlikely to be fully completed by the time the computer needs to make its move.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement