Game Programming and Development Tools

ai for tic tac toe – bennythebear



Posts: 1225
From: kentucky,usa
Registered: 12-13-2003
i'm back working on the ai for my tic tac toe game. right now i'm just working on the theory/pseudo code side of things, and i'm having a hard time working it all out. here's what i have so far:

1 check to see what boxes are not used
2 temporarily save finding to memory(variables)
3 select first open box
4 check to see players possible moves
5 tally a score somehow(need help with the details)
6 repeat steps 3-5 with the rest of the boxes
7 compare scores and select highest scoring box

ok...i need help with some of the details. also, should i take this further and go 2 or 3 rounds take the 2-3 top scoring boxes then check the next set of possible moves? any advice would be appreciated.

proverbs 17:28
Even a fool, when he holdeth his peace, is counted wise: and he that shutteth his lips is esteemed a man of understanding.

proverbs 25:7
open rebuke is better than secret love. - Gospel for Asia - Voice of the Martyrs



Posts: 518
From: Janesville WI
Registered: 08-31-2006
Did this program once as a way to think through creating an artificial intellegence

You have some points down, It has been a few years, but here is what I used

1. Determine open sqaures or possible moves.
2. Check to see if you can win, if you can win win
3. Check to see if the opponent can win. If the opponent can win, then you must block that move
4. If neither of the above cases are true then
a. determine if the middle square is open, if it is open take it
b. determine if a corner is available, if it is take it (what I did hear is determine if there is more than one corner open randomly pick a corner, I also added code that if you owned one corner and the opposite corner is open, and ad adjacent corner is open, take the opposite corner.)
c. Then if no corners are open, make a random placement (at this point there are only four squares left anyway)

So in summary, the AI I used for my game was comprised of three different levels,

A grabber, win if you can win, get the best position
A blocker, don't under any circumstances let anyone get a win or position
And random, play a square

There may be a better AI for tic tac toe, but I have played the above AI and cannot beat it.

Hope this has been of interest




Posts: 654
From: Pacific Northwest
Registered: 03-22-2005
I studied this exact AI while working on my 'Game In 2 Weeks' after the contest ended. I needed to make my computer AI better.

You need to look into the MiniMax algorithm.

Here are a few sites I used. Just to let you know, I read, re-read, and re-read many times and still don't have a confident grasp on the entire thing.

Tic-Tac-Toe in C# using MiniMax

GameDev AI Page
AI Wisdom
MiniMax Explained
Chess Programming

Chess Programming uses MiniMax too. As to how many levels to go, that is up to you. In Tic-Tac-Toe, which contains a small, simple board, it's easy to dig all the way down to the final move. But something like chess can become quite time consuming as you can get really deep in a tree of possibilities.

Try these sites and let us know if you have any more questions.

[This message has been edited by SSquared (edited November 17, 2006).]



Posts: 3450
From: SV, CA, USA
Registered: 01-29-2002
I sent you the code I made when I did my TicTacToe AI.

basically, I created a tree generated with all possible outcomes of the battle, and the 2 players(1 human and 1 computer) go down the tree, starting from root, alternating choosing which branch to go down. the human's choice inputed via the GUI of the tic tac toe board, and the possibly outcomes are narrowed down further, obviously. when it's the computer's turn, it uses a recursive algorithim to go down the trees and assess which branches will lead to it's vicotory (by also temporarily assuming the human makes the best choice he can possibly). each leaf of the tree holds a value, either a 1 (for comp victory, -1 for human, and 0 for tie.) the comp then chooses a path that leads to it's victory and then the human takes it turn and so it goes until one wins and one doesn't.

This is otherwise known as the Game Theory. (similar, but more complex algorithim used on stuff like Deep Blue, me thinks)

now, using this on a tic-tac-toe gives you a computer than can never be beaten. maybe having something goes through tree and randomizes some of the values on the leafs will screw the comps mind up and give it the ability to lose. (the amount randomized can determine the difficulty level)

Yes, I'm still better than you
Soterion Studios



Posts: 1225
From: kentucky,usa
Registered: 12-13-2003
thanks for the links and all the info guys. i don't have time to read it all right now, but i should have plenty of time tomorrow...if i don't do school work all day, and work in my website for my frontpage final. anywho, it's amazing how many lines of code can go into something so simple as a tic tac toe game.

proverbs 17:28
Even a fool, when he holdeth his peace, is counted wise: and he that shutteth his lips is esteemed a man of understanding.

proverbs 25:7
open rebuke is better than secret love. - Gospel for Asia - Voice of the Martyrs