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

[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)

 

[ToxicBug]

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

 

[Bartholomew]

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

 

[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 let's him tie. The seccond person can not lose if he has half a brain =-)

 

[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

 

[Bartholomew]

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

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)

 

[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.

 

[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...

 

[Pseudopod]

I think you're right msmith

 

[mattmns]

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...

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?

 

[Bartholomew]

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

 

[xJuggleboy]

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

 

[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.

 

[Alkatran]

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

 

[Bartholomew]

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

 

[Alkatran]

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

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.

 

[K.J.Healey]

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.

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.

 

[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.

 

[Alkatran]

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.

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:

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!

 

[Alkatran]

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.

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.

 

[Bartholomew]

Alkatran, you do not understand my program. findOutcome will return at both whomoves and -whomoves many times before completion.

 

[Bartholomew]

Also, this is exactly the type of problem a tree search is intended to be used on.

 

[Bartholomew]

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!

This is where your confusion arises. Already (bout an hour ago) I ran a trace on the whomoves return statement in the loop. It happens hundreds of times, as intended. I didn't have much time then to look at it more fully but now I will.

By the way, thanks for your comment about declaring P1 and P2 constants. Doesn't affect the program but is good coding style--as is explicitly initializing the array to 0 rather than relying on the language to automatically do it for me, especially since 0 is a special value (meaning empty square) in this class.

 

[Bartholomew]

Okay, I found the bug. It was in the testWin method.

	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])
				[b]return -arr[i][0];[/b] // this should be "return -arr[0][i];"
		}
		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;
	}

I fixed that statement and now it runs fine, returning -1 as it should. Cat got your tongue?

 

[Bartholomew]

If you still haven't conceded defeat, I expanded the class by a few methods so that now you can play against the computer (as player 2). The computer uses the methods I originally posted (with that one bugfix) to beat you.

No, I didn't include any System.out.println("Hooray, you won!"); statements. They'd be unreachable code.

import java.io.*;

class eotcatcit
{
	private static final int P1 = -1;
	private static final 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[0][i];
		}
		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;
	}
	
	static void makeBestMove(int[][] arr) // makes a winning move for player 1
										// given that player 1 can win for the valid board arr
	{
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
			{
				if(arr[i][j] == 0){
					arr[i][j] = P1;
					if(findOutcome(arr, P2) == P1)
						return;
					arr[i][j] = 0;
				}
			}
	}
	
	static void printBoard(int[][] arr)
	{
		System.out.println("   1  2  3");
		for(int i = 0; i < 3; i++)
		{
			System.out.print((i+1)+"  ");
			for(int j = 0; j < 3; j++)
			{
				if(arr[i][j]==P1)
					System.out.print("X  ");
				else if(arr[i][j]==P2)
					System.out.print("O  ");
				else
					System.out.print("   ");
			}
			System.out.println();
		}
	}
	
	static boolean boardIsFilled(int[][] arr)
	{
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
			{
				if(arr[i][j] == 0){
					return false;
				}
			}
		return true;
	}
	
	static void playGame(int[][] arr)
	{
		boolean gameover=false, inputok;
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		String humanmove = new String();
		int i, j;
		
		printBoard(arr);
		System.out.println();
		while(true)
		{
			i = 0;
			j = 0;
			System.out.println("Player 1 Moves:");
			makeBestMove(arr);
			System.out.println();
			printBoard(arr);
			System.out.println();
			
			if(boardIsFilled(arr)){
				System.out.println("Board filled. Game over! (computer wins)");
				return;
			}
				
			inputok=false;
			while(!inputok)
			{
				System.out.println("Your move? (enter in format row column with 1 space to separate)");
				try{
					humanmove=input.readLine();
				}
				catch(Exception e){
					e.printStackTrace();
					System.exit(0);
				}
				
				try{
					i = Integer.parseInt(""+humanmove.charAt(0));
					j = Integer.parseInt(""+humanmove.charAt(2));
				}
				catch(Exception e){
					i = 0;
					j = 0;
				}
				inputok = j >= 1 && j <=3 && i >=1 && i <=3 && arr[i-1][j-1] == 0;
				if(inputok)
					arr[i-1][j-1] = P2;
				else
					System.out.println("invalid input");
			}
			if(testWin(arr) != 0){
				printBoard(arr);
				System.out.println("Game over! (computer wins)");
				return;
			}
			System.out.print("And ");
		}
	}
	
	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;
		playGame(arr);
	}
}

 

[Bartholomew]

(I've only done a few games of testing for the updated program so it may be buggy. Let me know how it goes)

 

[Alkatran]

Just because you got the right answer doesn't mean you got it the right way.

It's similar to the undecidable problems: You have two functions, one returns true, the other returns false, one of them HAS to be right. But that doesn't mean the functions analyze the problem in any way.

Here is the main idea of your entire algorythm:

                  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;

Now, look at what it is doing.
First, you check if the current configuration is a win (for either player). If it is, you return that player's index. Otherwise you check every possible move at this point, and recurse.

To recurse, you loop through every square on the board. If the square is empty you play it, check all children through recursion, then empty the square and move to the next one. If the current square being checked results in a win, you pass along the message. Which means the parent of the current function get the win, returns, etc...

I don't see how the program wouldn't end.

 

[Bartholomew]

When in the first move the program finds a winning square, it ends the program _as it should_. There's no reason to search farther and find a potential second winning square.

When the program picks the wrong coordinates (say, the upper-left corner) for the first move, it runs a test and finds it's a loss. The way it finds it's a loss is by finding that on the next move, the other player has a winning move. Once it finds that the other player has a winning move, it returns, and you're back to the original board, where it chooses and evaluates another possible move for player 1.

To trace the order of execution:
On the first move, when i and j are 0, it finds square (0,0) is 0 and does this:

arr[j] = whomoves;
winflag = (findOutcome(arr, -whomoves) == whomoves);

Now when it finds that outcome, it will be a loss because player 2 has a win. In the recursive call, it tests square by square (again recursively) finding that player 2 loses for those moves _until_ it finds a square where player 2 wins. It returns that player 2 wins, which is the value 1--and after it returns you are now back in the first call of the method, where you have "winflag = (1 == -1);" or winflag = false;. Since winflag is false you continue, incrementing j and checking again for player 1 for the square (0,1). A similar thing happens... and so on, until it tests square (1,1) and finds a win for player 1, and returns -1.


Anyway, if there were a flaw in the program's logic, my updated program wouldn't be able to beat you at eot-cat-cit; it couldn't choose the correct moves. But it can
beat you at eot-cat-cit. Therefore it's correct.

 

[BicycleTree]

Since the program always beats you, it's correct.

 

[BicycleTree]

Returning does not end the program unless you are in the first function call.

 

[Alkatran]

Since the program always beats you, it's correct.

But this isn't about always being beaten, this about choosing one strategy that ALWAYS works for NOT being beaten!

This program will tell you the answer to "Can Someone Win at the game?"

 

[BicycleTree]

The program uses the move search algorithm already described to play eot-cat-cit against you as player 1 and win every time. Have you run the program to verify this?

It's a pretty good bet that if the program can do perfect play, its win-testing functions are correct.

 

[BicycleTree]

Perhaps I haven't been making myself clear: the updated version not only plays eot-cat-cit to itself to find a winner, it actually beats you as a human player, where it makes a move then you make a move and so on.