Tic Tac Toe AI

I finally got around to finish my min-max AI toy model, a Tic Tac Toe AI! I found out the hard way that creating an actual AI in a real situation, in a generic way, is harder than what the wikipedia page makes it look with its simple formula 🙂 Also, I spent a lot of time debugging small issues because even for Tic Tac Toe, the graph of possibilities can be quite daunting (9! = 362880 possibilities for the first move). So I had to imagine some ways to retrieve debug information about what is going on. I think I’ll have to push this further when I get to the real implementation with MTG. Otherwise, the AI just feels like a black box: “I chose to do this.” and then you go “Why the hell did it choose that move? It’s a losing move!”.

But now, it’s all fixed and my AI never loses in normal games 🙂 I also got surprised by some situations, where I would test a simpler case. Something like:

    XX_
    ___
    ___

Now, where should the AI place its O? At first, I was expecting it to block the X line, of course. But it turns out it gives any move (the first move it evaluates in fact). It took me some time to figure out why that is. Basically, the AI is telling us that it’s going to lose whatever it does, so it doesn’t even bother trying a decent move. Indeed, if you block the line, the other player can place an X in the middle and the O player is screwed because X has two possible lines next turn.

    XXO
    _X_
    _..

It’s kind of creepy to be corrected by an AI 🙂

What’s left to do before attempting the MTG implementation:

  • Alpha-beta pruning
  • Simpler implementation + simpler integration with the game
  • Support for multi-choice game (in Tic Tac Toe, every player is asked the same thing: what’s your next move? But in MTG, there’s a lot of choices to be made: “What card do you play? What player do you target? How will you pay this cost?”)
  • More debug info 🙂

Next time, I’ll try to delve into the change in paradigm I had to make with regards to the game sequencing to make this work (solving the problem established in my last post).

Advertisements

About fparadis2

Lead Game programmer
This entry was posted in Mox. Bookmark the permalink.

2 Responses to Tic Tac Toe AI

  1. Huggybaby says:

    Maybe we should change it from Artificial Intelligence to Artificial Human Like Intelligence, or WWHD (what would humans do LOL).

    Once the AI knows it’s going to lose, it shouldn’t make a random move. That is in effect conceding. It assumes that the opponent is perfect. Instead it should make the game last as long as possible, forcing as many moves as possible, because the longer the game takes the more likely it is that the opponent will make a mistake.

  2. fparadis2 says:

    Yeah, I think you’re right! I’ll have to figure out a way to introduce some “human-ness” into the AI. The vanilla minmax algorithm has a very mechanical feel.

    On the other side, I think this behavior is in part due to the heuristic I use for Tic Tac Toe. The heuristic assigns a score to a given board position. Currently my heuristic is:

    +100 if the AI has won
    -100 if the AI has lost
    0 otherwise

    Which means that all board positions are equal for the AI, except for a winning/losing position.

    In a game like MTG, I except the heuristic to be a lot more subtle. In fact, I don’t think there will be any point where the AI will be able to say with absolute certainty that “it will lose”. In that case, it will choose the best move at the time.

    I’d still expect that move to be intelligent though, even if the AI is in a desperate situation… I’ll think about that! Thanks for your input!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s