Jump to content
  • Advertisement
Sign in to follow this  
chaosgame

TicTacToe AI

This topic is 5088 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
Advertisement
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
So what you are saying is i should make a simpler verson of my ai and then a list of moves not to make. when it looses it adds the move to the list.

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
Sign in to follow this  

  • 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!