Sign in to follow this  

TicTacToe AI

This topic is 4745 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

I finished my first C++ game today, tictactoe. Its unbeatable. I would like to compare my AI with other people. This is how my AI works (it goes second) 1) Check for win 2) Check for win for the other player 3) If nobody has moved to the center, move to the center 4) look for the move that on the next turn, will yield the most wins 5) look for the move that on the next turn, will yield the most wins for the other player, if it will yield more wins than in number 4, move there I plan to post my code later.

Share this post


Link to post
Share on other sites
Thats a good ai, but its hard-coded logic. (thats good sometimes, but bad in others).

Perhaps make some version of reinforcement learning for it? (its quite simple, but its nice to know how to do).

From,
Nice coder

Share this post


Link to post
Share on other sites
if you would like to compare you tic tac toe to others, enter it in our ttt competition

www.newgameprojects.net

http://www.gamedev.net/community/forums/topic.asp?whichpage=1&pagesize=25&topic_id=288141

Share this post


Link to post
Share on other sites
basically step three should be eliminated.
also, step five I think you typed in wrong. at any rate, step four is almost enough. You should add that the AI should take the move that is also the most detrimental to the player, minimizing the player's wins.

It's called the minimax algorithm, and I don't think it's perfect. For example, I'm pretty sure it fails in this situation:

user plays a corner (not the "strongest" center play)

x| |
-----
| |
-----
| |

minimax will play center

x| |
-----
|o|
-----
| |

user plays opposing corner, which would be baffling, because the o is already blocking

x| |
-----
|o|
-----
| |x

minimax plays another corner

x| |o
-----
|o|
-----
| |x

user blocks

x| |o
-----
|o|
-----
x| |x

and minimax has dug its own grave.

Share this post


Link to post
Share on other sites
This is something that i encountered. heres the problem:
...there are 2 identical moves that will both cause the player to win
...but this will only happen if the computer has the middle
if you put these 2 expressions in an if statment, the problem will be solved, or at lest thats how mine works, there might be a better way.

Share this post


Link to post
Share on other sites
One way would be to hard code each possible situation and the best solution for that situation. This is ideal for tic-tac-toe because the game itself is bloody simple.. and it doesn't require any large amount of fudging with algorithms. Of course, if you're out to learn more about more advanced AI...

Share this post


Link to post
Share on other sites
The easiest way to make an unbeatable (At least iirc) tic-tac-toe game would be to eliminate step 4 and 5 and instead just make a move 'next' to the other players move (for ex if they move on the upper left corner, then move on either the upper side or left side.

In my boot sector ttt (in the showcase), I think I used negamax. I'm not certain though because my c++ implementation is slightly different and I couldn't find any good explanations on google to see which one was correct and of course I don't feel like debugging my assembly code now anyways =-) Even if it is incorrect, I think it always wins still.

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
The easiest way to make an unbeatable (At least iirc) tic-tac-toe game would be to eliminate step 4 and 5 and instead just make a move 'next' to the other players move (for ex if they move on the upper left corner, then move on either the upper side or left side.


I think that Extrarius might be wrong...

| |
-----
|x|
-----
| |

| |
-----
|x|o
-----
| |

| |
-----
|x|o
-----
| |x

o| |
-----
|x|o
-----
| |x

o| |
-----
|x|o
-----
x| |x

...and X can win two ways.

Share this post


Link to post
Share on other sites
Oh, I left out the rule that if they go in the center (on first move only?) you must take a corner.
A long time ago I worked out some simple rules for never losing and I can't remeber exactly what they were but they went something like that. Anyways, like I said that isn't the algorihm I used in my TTT in the showcase.

Share this post


Link to post
Share on other sites

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this