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.