Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 3, 2005 #1
    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. jcsd
  3. Mar 3, 2005 #2
    Yes, of course. Have you ever seen a game of Tic-Tac-Toe where the player who didn't start won?
     
  4. Mar 4, 2005 #3
    I don't think that's really an answer, toxicbug. Eot-cat-cit would be pretty different from tic-tac-toe.
     
  5. Mar 4, 2005 #4
    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 =-)
     
  6. Mar 4, 2005 #5
    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 :smile:

    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
  7. Mar 4, 2005 #6
    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
  8. Mar 4, 2005 #7
    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.
     
  9. Mar 6, 2005 #8
    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...
     
  10. Mar 6, 2005 #9
    I think you're right msmith
     
  11. Mar 6, 2005 #10
    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?
     
  12. Mar 7, 2005 #11
    Now that's strange, seems to work... what's the bug in my code?
     
  13. Mar 7, 2005 #12
    It is impossible for the person that goes first to force a win.
     
  14. Mar 7, 2005 #13
    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.
     
  15. Mar 7, 2005 #14

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    You're code is wrong because it tries every possibility, not every strategy.
     
  16. Mar 8, 2005 #15
    If it tries every possibility it includes every strategy. There must be some other bug.
     
  17. Mar 8, 2005 #16

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  18. Mar 8, 2005 #17
    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.
     
  19. Mar 8, 2005 #18
    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.
     
  20. Mar 8, 2005 #19

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    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!!
     
  21. Mar 8, 2005 #20

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    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?



Similar Discussions: The game of reverse Tic-Tac-Toe, called Eot-Cat-Cit
  1. The TOE (Replies: 15)

  2. Toe poll (Replies: 59)

  3. That game (Replies: 16)

Loading...