Writing Tic-Tac-Toe from scratch.

[Kabir Shah]

       int negamax(boolean xTurn, int depth, int alpha, int beta,
            char[] board1)
      {
        int eval;
        eval = check_Win();
        System.out.println("eval " + eval);
        if ((eval == -1) || (depth == 0))
          {
            return eval;
          }

        if (board1[0] != ' ' && board1[1] != ' ' && board1[2] != ' ' && board1[3] != ' '
                && board1[4] != ' ' && board1[5] != ' ' && board1[6] != ' ' && board1[7] != ' ' && board1[8] != ' ')
          {
            return check_Win();
          }
        for (int sq = 0; sq < 9; sq++)
          {
            if (board1[sq] == ' ')
              {
                board1[sq] = (xTurn ? 'X' : 'O');
                //          System.out.println(xTurn);
                eval = -negamax(!xTurn, depth - 1, -beta, -alpha, board1);
                board1[sq] = ' ';
                if (eval >= beta)
                  {
                    return beta;
                  }
                if (eval > alpha)
                  {
                    alpha = eval;
                  }
              }
          }
        return alpha;
      } 

  public int get_Move(boolean turn)
      {

        int alpha = -2;
        int beta = 2;
        int index = 0;
        int sq;
        int eval = 0;

        char board1[] = new char[size * size];

        for (sq = 0; sq < 9; sq++)
          {
            board1[sq] = board[sq / 3][sq % 3];
          }

       
        for (sq = 0; sq < 9; sq++)
          {
            if (board1[sq] == ' ')
              {
                board1[sq] = (turn ? 'X' : 'O');
                eval = -negamax(!turn, maxdepth - 1, -beta, -alpha, board1);

                if (eval >alpha)
                  {
                    alpha = eval;
                    index = sq;
                  }

              }
          }

        return index;


      }   

The above code is for methods of negamax and get_Move.
I am fully aware of the other thread which explains writing tic-tac-toe from scratch, I tried to code my version of tictactoe taking help from that post,just to see whether I can code these algorithms in different data structures or not.I am also aware that I have not created a list of legalMoves, but I have made condition in the program, and this does not hamper any thinking done by the machine.

Kindly take a look at the post, my problem is that the above given code, when executed by computer, doesnot make the best possible move. What have I done wrong?

[Mich Robinson]

Gurudas Bhandarkar wrote:Kindly take a look at the post, my problem is that the above given code, when executed by computer, doesnot make the best possible move. What have I done wrong?

What testing have you done? does check_win() return correct values for either side winning, a draw and no result as yet? In a given position does your program favour the worst move, the first move it comes to or the last move? You should learn to debug your code ie print out what the program is doing at each stage, then just look at a simple position, then look through the output and see where it first does something different to what you expect, you have now found your bug!

MinMax algorithms work by passing back a large +ve value for one side winning and a large -ve value for the other side winning. Looking briefly at your code (line 24) you only appear to be seeing if eval is greater than beta whereas you should be prefering large positive values when playing one side and large negative values when playing the other side.

You also seem to be also using an AlphaBeta algorithm (judging by the variable names at line 28) - this only complicates matters and you should get the MinMax working correctly first.

I wouldn't be too worried - I've been playing chess for years and don't think I've ever made the best possible move.

[Kabir Shah]

@Mich
Thank you very much , I tested my game thoroughly, but then due to the recursion process I was unable to make few decision.
I then implemented only negamax(without alpha beta pruning).

and now it works, however, now I am stuck with the alpha beta pruning part.
my program moves from left to right and then evaluates the positions.

The game is fully working with only negamax.
but I want to learn, addition of alpha beta algorithms and then higher algorithms.

The error my program was making was not seeing any win for itself or for the opponent.
kindly help me with it if possible.

here is the code fully working tic tac toe with AI.
CODE

[Mich Robinson]

I tested my game thoroughly

The idea of testing is to find and correct any mistakes. If you didn't find any errors then the program should work or it suggests the testing wasn't that thorough. Recursion should actually make testing easier as you can test what the program will do in any given situation. It makes testing much easier if you have print statements (that can be turned off) throughout your code to show what's going on.

The game is fully working with only negamax
but I want to learn, addition of alpha beta algorithms

AlphaBeta pruning is explained here. Whether you need it in a simple game like OXO is another question.

here is the code fully working

I'm not familiar with negamax but assume it's similar to minmax - in which case your code looks wrong. The check_win routine should return a large +ve or a large -ve number. Instead it always returns -1 or 0. The code to check this value also looks wrong as I explained before. I'm not sure what the variable alpha holds but it suggests something to do with alphabeta pruning and, if it doesn't do this, it should be renamed.

The check_win routine could be much shorter, faster and easier to read if you pass the side that just moved and then just look to see if that side has 3 in a row anywhere.

int check_Win(char side, char board[]) {
   if ( board[0] == side && board[1] == side && board[2] == side
       || board[3] == side && board[4] == side && board[5] == side
       || board[6] == side && board[7] == side && board[8] == side
       || board[0] == side && board[3] == side && board[6] == side
       || board[1] == side && board[4] == side && board[7] == side
       || board[2] == side && board[5] == side && board[8] == side
       || board[0] == side && board[4] == side && board[8] == side
       || board[2] == side && board[4] == side && board[6] == side ) {

       if ( TESTING ) { System.out.println("check_win: found win for " + side ); }

       if ( side == 'X' ) {
           return 100;
       } else {
           return -100;
       }
   } else {
       return 0;
   }
}

Mike

[Kabir Shah]

@Mich.

Ya negamax is similar to min-max, but is more elegant implementation of min-max.
In this, we negate the return value for both players so it gives two extreme values like min-max, but we do not write two functions -min and max.

here is the reference which I used.
http://www.hamedahmadi.com/gametree/

still struggling to add alpha-beta pruning.
I want to add alpha beta to this game because, I want to redesign my connect four and use alpha beta pruning in it.

[Mich Robinson]

Just had a very quick look at that site and it seems to explain things well. I'm not sure about how useful the negamax method is though as it doesn't really offer that much of an improvement. From what I can see you should be negating the score only for one side so you end up with a MaxMax type of algorithm which just saves a bit of code when testing - problem is you're negating all scores at line 270.

Anyway the code looks wrong to me due to the points I raised in both my previous posts but if it works - great!

[Kabir Shah]

@Mich
Hey I have worked out with alpha beta pruning as well. and it works 100%now.
thanks for help and advice.

I have programed a connect four as well.
I have written a primitive evaluation for it. how ever, its been sure that in order to win, the game has to be evaluated using some concepts. I have tried to do that as well, but not working. can you help me in it, It is programmed for command prompt.

[Mich Robinson]

Just start a new thread on evaluating connect 4 and I'll reply there.