First, Tic Tac Toe algorithm where computer goes first:
Definitions:
board:
1 | 2 | 3
-----------
4 | 5 | 6
-----------
7 | 8 | 9
TAS They are screwed - you have two lines that they need to block.
For example: (it's their turn and we are 'X')
O | | X
-----------
| |
-----------
X | O | X
If they go to 5, you go to 6, if they go to 6, you go to 5.
You win no matter what. The TAS possibilities will be labeled with
the two positions you could go to, for this example: TAS(5,6)
TWBS They will be screwed - it is their turn, but you have forced them
into a position that will create a TAS. For example:
O | |
-----------
| |
-----------
X | | X
They will be screwed because they need to go to 8 to block, then you
can move to 3 and you have the same situation as the TAS above -- TAS(5,6)
TWBS will be labeled like such: TWBS(block:next move:choice1,choice2)
Where: block=the position they have to go to block (be prepared to take
this spot if they don't go there, otherwise you will look
stupid declaring a win you didn't get)
next move=the next move you take after they take the block position
(if they don't take the block position, of course, you do)
choice1,2=the two choices of the TAS
So the above example would be: TWBS(8:3:5,6)
Which means that they need to go to 8 to block (or you take 8 and win) and then
you go to 3, and that gives you a TAS(5,6). Be careful when calling a board
a TWBS! They *need* to be forced into the block. The one case where they
might not be is if they have a possible immediate win.
Make sense? Good - because that makes the algorithm much easier to type up
and understand. I did it this way because after you make your second move,
it is always a TWBS situation, *unless* they take the center as their first
move, then it gets stupid (this is the only way they can tie)
(this table *should* be correct -- try it out and see, it will help
you understand it anyways :)
Current state Their move (x) Move to Next State
------------- -------------- ------- ----------
start 9 A
A 1 3 TWBS(6:7:5,8)
A 3 1 TWBS(5:7:4,8)
A 7 1 TWBS(5:3:2,6)
A 2, 4 or 8 1 TWBS(6:5:1,7)
A 6 7 TWBS(8:5:1,3)
A 5 1 B
B 2,4,6 or 8 **(see below)
B 3 7 TAS(2,6)
B 7 3 TAS(2,6)
** NOTE:
In this situation, you cannot win. You will need to block, then they
need to block, etc...
There are *many* alternatives to the above table that still has the
same effect. For example:
A 7 3 TWBS(6:1:2,5)
Each time I had an alternative, I chose the one that most looked like
one of the other lines, which makes it easier to simplify. You can
simplify further than the lines above, for example, lines A 3 and A 7 could
be combined something like this: (Their move=x)
A x=3 or 7 1 TWBS(5:7:...)
where ...=4,8 if x=3 or 2,6 if x=7
So - if you are going to use some method other than this table, you might
want to use some of the alternatives so that the pattern isn't as obvious
(the above table often goes in the same places and does the same things).
The quick way to program it (that would require memory) is to just do
a bunch of case statements like the table above. So you have the case
statement for state A which is switched on their move. For every possible
move they have, the case statement would give you your move and the next
state to go to (another case statement)
That's one way to do it.
Since you are going to need to set up some functions for the possibility
of the other player going first, you might want to use this more interesting
method (I'm pretty sure this will give just as good results as the table,
but it lets you randomize it a little - for example, when it says ANY
corner, you can randomly pick one, so the game can be different every time):
First, go to 9 (or ANY of the corners, for that matter)
Then, when they move, if they don't take the center, take ANY of the other
corners that fulfills the following conditions: (If they pick the center,
see CENTER below)
A They aren't already blocking it (for example, you go to 9, they
go to 8, this rules out 7)
B If they do block it, it doesn't give them 2 in a row with a blank
space that you will need to block. (In other words, if they block
it, it won't put you in a position where you need to block) (for
example, if you go to 9, then they go to 8, you can't go to 1, because
they will block at 5, and then you will be forced to block at 2 - you
will have lost your dominance. Try drawing this out to see)
Then, you will have two corners - which obviously have a line potential.
This is now a TWBS situation:
They will have to block it (because of condition A), and this doesn't
force you to block. Now you can go just about anywhere, and you will
find that you have at least one position you can go to that gives you
a TAS situation. You will have to write a function that looks at the
board for your turn and finds a place that you can go that will give you
the TAS situation, but you will probably want to write something like this
anyways for the possibility that they can go first. (see below for
one approach)
CENTER: Now, what if they went to the center on their turn?
Then you go to the opposite corner. I know it doesn't make sense, since
they already have that line blocked, but if you go anywhere else, it could
set up a win for *them*. Trust me, I've worked it out. :)
Then, if they go to one of the side squares (the even ones) then you just
block, and they block, and you block, and they block, and finally you block,
and its a damn tie. Oh well.
If they go to one of the two corners, they have lost. The TWBS is automatic;
since they hold the center and one of the corners, you pick the other corner
to block, and suddenly TAS.
---
Here is an example of how you can look for TAS situations. They will have
taken the block (again, if they don't, be ready to take the spot and win).
When they do, you need to find where you can go to make the TAS.
You find this by picking the empty square that gives you two possibilities
to win, because once you put an X in the square, then there will be
two lines that have two X's and an empty space (where the empty spaces
are different). They can only block one empty space, so you take the other.
For example, if you have 3 and 9, and 1, 2 and 5 are blank, then by
taking 1 you have a TAS situation. 2 and 5 will both give you three in a row,
so they can only block one.
There is an easy way to figure out if you have that situation on any given
line(s). This algorithm I am about to describe is useful for figuring out
the state on any given line in general. For example, if you want to know
if a line has one X on it and two blank spaces, or two X's and one blank
space, or an X and an O or whatever.. here is how you can do it without
trying to match the line up to each possible pattern. For example, if we
are looking at the line 1,2,3 to see if it has one X and one O and one
space in it, we could do a comparison of 1,2,3 to each possibility:
XO_
OX_
X_O
O_X
_XO
_OX
But this would be stupid. A better way is through my addition algorithm.
Just add up the values of each position on the line, where the values are:
space 0
X 1
O 4
(trust me, there is method to this madness)
This sum is going to be unique for each possible line, regardless of
position, which means that all lines with one X and one O and a space
are going to have the same value, which will be a different value
then a line that has two X's and one O which will be different from
a line with two X's and a space, etc.. etc..
So, to look for a line with one X and one O and one space, we just
add up the values of the three positions in the line. If they
equal=X+O+space=4+1+0=5, then we have found it.
This can help you find block situations. If you are X, and there are
any lines with the sum=O+O+space=4+4+0=8, then you need to block there,
unless you have somewhere you can go to win: sum=X+X+space=1+1+0=2.
Fucking cool, eh?
So, here is how I would go about looking for TAS situations. Pick an
empty space. Each empty space except 5 has two lines going through it
(for example, 2 has 1,2,3 and 2,5,8). So, see if the sum of the two
lines going through the empty space=X+space+space=1+0+0=1 then you
have a TAS situation. You can just go to that empty space, making those
two lines now have a value=X+space+X=1+0+1=2, which gives you two possible
wins (since the space in each line is different from the other space -this
isn't hard to proove). If the two lines going through the space do not
have the sum of 1, then go on to the next empty space.
If the empty space is 5, it gets a little tricky, since you have 4 possible
lines through space 5. In this case, just see if you have any two with
the sum of 1, and once again, a TAS situation.