Archived

This topic is now archived and is closed to further replies.

Game trees

This topic is 5533 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Wy not just make it a bunch of if statements?

May be inefficient, but it is tic tac toe.... Who cares about effienciency....

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 ]

Share this post


Link to post
Share on other sites
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??

Share this post


Link to post
Share on other sites
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 ]

Share this post


Link to post
Share on other sites
A connect4 program in a modern computer should be able to search about depth 14 in under a minute. It could be less, depending on how sophisticated the evaluation function is. Definitely not less than 10.

Share this post


Link to post
Share on other sites
From the player''s point of view, I don''t like timers at all. If I play on the "hard" level, give me hard. If I play on easy, give me easy. I don''t want "easy" to search 4 more depth levels just because I play on an Athlon 1600+, nor hard to be too easy just because I play on a P233.

That being said, a timer friendly algorithm probably needs to store the search tree in memory and be able to add single nodes to that tree and update the rest of the tree after adding that node. Proof number search is an example of such algorithm. It assumes the game tree is and AND/OR tree (each node can be true or false - true for a win, false for a loss for the AI player). If a node represents a game state where the computer AI plays, it is an OR node, if its oponent plays its an AND node (minmax style). Each inner node in a partially calculated game tree needs a minimal number of leaf nodes proved true to prove it true and a minimal number of leaf nodes disproved to disprove it. Turns out that at all times there is at least one leaf node that is in both of these sets. Expanding that node will have the highest likelihood of solving the tree. For more, search for the paper by Victor Allis.

But I''d much rather prefer an algorithm that performs the same on all computers. Iterative deepening minmax is a good and simple enough choice. You start with a very shallow minmax run (1 ply or so). You then keep calling the minmax with larger depths (increase the depth with 1 at each iteration). You can limit your algorithm when a minmax run has expanded a certain number of nodes (this gives the advantage that you can search deeper at times) or using a timer (bleh). Given the exponential time needed by minmax, you won''t waste too much time with the unused shallow searches (probably around 25% give or take). And if you use transposition tables (storing the values of the positions you have calculated in a hash table), you can use these values calculated by a shallow iteration to improve the alpha beta optimisation by better move ordering at the next iteration.

That or you _can_ use fixed depth. Trouble is often the time needed for a fixed depth algorithm can vary a lot. My former go-moku program could search ten thousand position or five millions for the same depth without blinking. I assume a the number of moves needed for a Connect 4 game is a lot more stable though given the limited moves at each step.

Share this post


Link to post
Share on other sites