The game of reverse Tic-Tac-Toe, called Eot-Cat-Cit

1. Mar 3, 2005

msmith12

The game of reverse Tic-Tac-Toe, called Eot-Cat-Cit, has the same rules as Tic-Tac-Toe, except that the first player with 3 markers in a straight line looses. Can the player with first move avoid being beaten?

(note: a tie counts as a win for player 1)

Last edited: Mar 3, 2005
2. Mar 3, 2005

ToxicBug

Yes, of course. Have you ever seen a game of Tic-Tac-Toe where the player who didn't start won?

3. Mar 4, 2005

Bartholomew

I don't think that's really an answer, toxicbug. Eot-cat-cit would be pretty different from tic-tac-toe.

4. Mar 4, 2005

xJuggleboy

Well.... Tic Tac Toe is not much of a game... THere are only a few possible games of Tic tac toe that can be played.

The first person to go will have 5 boxes while the other has 4. The first person to go will always lose unless the other person is very nice and lets him tie. The seccond person can not lose if he has half a brain =-)

5. Mar 4, 2005

mattmns

No, the first player can not win, unless my proofs are wrong, in which case then player 1 could possibly win lol.

Here are my picture proofs: Too hard to type tic tac toe boards, imo

Note: My handwriting is terrible, and these proofs are not explained in great detail. Also the proofs have not been fully tested, but if you can prove them wrong then you have probably found the answer.

Note: X = player 1 for all. Also O = player 2 for all.

http://img150.exs.cx/img150/9642/tictac2small0so.png

http://img153.exs.cx/img153/8046/tictac1small9xk.png

http://img150.exs.cx/img150/3295/tictac3small2te.png

Last edited: Mar 4, 2005
6. Mar 4, 2005

Bartholomew

Turns out you're right, matt, but I couldn't say whether your proofs are correct. I wrote a program:
Code (Text):

class eotcatcit
{
private static int P1 = -1;
private static int P2 = 1;
static int testWin(int[][] arr)
{
int i;
for(i = 0; i < 3; i++){
if(arr[i][0] != 0 && arr[i][0] == arr[i][1] && arr[i][1] == arr[i][2])
return -arr[i][0];
if(arr[0][i] != 0 && arr[0][i] == arr[1][i] && arr[1][i] == arr[2][i])
return -arr[i][0];
}
if(arr[0][0] != 0 && arr[0][0] == arr[1][1] && arr[1][1] == arr[2][2])
return -arr[0][0];
if(arr[2][0] != 0 && arr[2][0] == arr[1][1] && arr[1][1] == arr[0][2])
return -arr[2][0];
return 0;
}

static int findOutcome(int[][] arr, int whomoves)
{
int test = testWin(arr);
boolean winflag = false;
if(test != 0)
return test;
// if any move has a winning outcome for current player,
// then current player wins.  Otherwise current player loses.
// Also, if no moves are legal for current player, current player loses.
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
if(arr[i][j] == 0){
arr[i][j] = whomoves;
winflag = (findOutcome(arr, -whomoves) == whomoves);
arr[i][j] = 0;
}
if(winflag)
return whomoves;
}
return -whomoves;
}

public static void main(String argv[])
{
int[][] arr = new int[3][3];
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
arr[i][j] = 0;
System.out.println(findOutcome(arr, P1));
}
}

It runs and returns 1, meaning player 2 wins. Hopefully my code is correct.

(that's in Java, by the way)

Last edited: Mar 4, 2005
7. Mar 4, 2005

mattmns

I thought about making a program, but I do not know how to program lol. I used the logic of player A can only move to 3 spots, because you can rotate the board to turn it into any of the other positions. From there I found a spot that would always win for player B, then I made it so that there was a position that would always win for player B IF player A chose that first spot, which worked too.

8. Mar 6, 2005

msmith12

I actually think that i found a solution for player 1 to always tie...

if player one chooses the middle square first... and then mirrors all of player 2's choices (i.e. if player 2 chooses top right, then player 1 then chooses bottom left), it works out to a tie every time...

9. Mar 6, 2005

Pseudopod

I think you're right msmith

10. Mar 6, 2005

mattmns

Yep that seems to work, good job: Very interesting strategy. Is there a tic tac toe pattern that will always win if you go first?

11. Mar 7, 2005

Bartholomew

Now that's strange, seems to work... what's the bug in my code?

12. Mar 7, 2005

xJuggleboy

It is impossible for the person that goes first to force a win.

13. Mar 7, 2005

Bartholomew

Well, a tie counts as a win for player 1 as stated in the problem. My program should account for that... don't know why it's wrong.

14. Mar 7, 2005

Alkatran

You're code is wrong because it tries every possibility, not every strategy.

15. Mar 8, 2005

Bartholomew

If it tries every possibility it includes every strategy. There must be some other bug.

16. Mar 8, 2005

Alkatran

Uh. No. That's the problem. It tries every strategy at once. It needs to try every strategy individually.

Testing out the 'play opposite square' strategy is obviously not going to work if you included a game that doesn't involve that! You're program is just mindlessly iterating through the boards.

I don't understand how you don't see the flaw. This type of problem is notoriously hard to program because it is strategy, not permutations, that matters. It's incredibly hard to try every permutation allowed by a single strategy, and repeat for >every< strategy.

17. Mar 8, 2005

K.J.Healey

Well you could use it to see which patterns lead to a win, then see if any of those patterns have the same X moves, regardless of O moves. If about 7 or more of those patterns do, then you have a pattern where X can win everytime. You can't just expect the program to find the solution without a little analysis.

18. Mar 8, 2005

Bartholomew

Yes, you can. There's a name for what my program does--it's called a tree search. There's a simple bug in the program somewhere. I'm going to try and find it now.

19. Mar 8, 2005

Alkatran

True. But the idea of said program was to return if it was possible, so it should have done the analysis itself (haha, good LUCK).

As for the program, let me lay it out for you:

Code (Text):

class eotcatcit
{
//variables which should be constants (not to mention bytes, 1 and 2)
private static int P1 = -1;
private static int P2 = 1;

public static void main(String argv[])
{
//start 3x3 array for the board
int[][] arr = new int[3][3];
//unnecessary for loops, since declaring an array like you did starts it with 0
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
arr[i][j] = 0;
//check if player 1 can win
System.out.println(findOutcome(arr, P1));
}

static int findOutcome(int[][] arr, int whomoves)
{
//check if this board configuration is a win
int test = testWin(arr);
boolean winflag = false;

//Check if any moves coming from this move is a win
if(test != 0)
return test;
// if any move has a winning outcome for current player,
// then current player wins.  Otherwise current player loses.
// Also, if no moves are legal for current player, current player loses.
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
{
if(arr[i][j] == 0){
arr[i][j] = whomoves;
winflag = (findOutcome(arr, -whomoves) == whomoves);
arr[i][j] = 0;
}
//If this board configuration is a win, return it (this will effectively end the program)
if(winflag)
return whomoves;
}
//If it's not a win, return the opposite, and the program keeps going
return -whomoves;
}

//this sub checks if a win happened
static int testWin(int[][] arr)
{
int i;
for(i = 0; i < 3; i++){
if(arr[i][0] != 0 && arr[i][0] == arr[i][1] && arr[i][1] == arr[i][2])
return -arr[i][0];
if(arr[0][i] != 0 && arr[0][i] == arr[1][i] && arr[1][i] == arr[2][i])
return -arr[i][0];
}
if(arr[0][0] != 0 && arr[0][0] == arr[1][1] && arr[1][1] == arr[2][2])
return -arr[0][0];
if(arr[2][0] != 0 && arr[2][0] == arr[1][1] && arr[1][1] == arr[0][2])
return -arr[2][0];
return 0;
}

}

Alright. Look at the comments. Here's the general idea of the program:
-Start with a blank tic tac toe board.
-Start a recursive function which:
Tries placing the current player's move in each available square in turn
Calls itself from that move
Returns wether or not a win is achieved

The program will run until it hits the FIRST WIN IT FINDS then return who had that win and STOP. Of COURSE IT DIDN'T WORK!! It doesn't make any sense in the context of the problem!! You're just checking if it's possible for a player to win a normal game of tic tac toe!!

20. Mar 8, 2005

Alkatran

By the way, I know what a tree-search is. It WON'T WORK for this problem. You're approaching it wrong. As I've already said, a tree search checks every possibility, not every strategy. All the possibilities that break from the 'play the opposite side' strategy are checked, so the program fails.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?