Jump to content
  • Advertisement

Archived

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

glJunkie

Game trees

This topic is 5818 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
Advertisement
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
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.

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!