Help in understanding Negamax and Alpha-Beta Pruning

Started by
8 comments, last by alvaro 13 years, 3 months ago
Hello every one and I am new to this website.
I know there are many articles which explain the concept behind negamax and alpha beta pruning.
I have successfully programed connect-4 using negamax and alpha-beta using the pseudo code that is available on numerous websites.
However when it comes to understanding the concept and writing an evaluation which corresponds to the same,troubles me.

int AlphaBeta(int depth, int alpha, int beta){    if (depth == 0)        return Evaluate();    GenerateLegalMoves();    while (MovesLeft()) {        MakeNextMove();        val = -AlphaBeta(depth - 1, -beta, -alpha); // <-- ***NEGATE HERE***        UnmakeMove();        if (val >= beta)            return beta;        if (val > alpha)            alpha = val;    }    return alpha;}
.This is taken from bruce morelands website.


So Now I proceed to write the evaluation. The program works fine when I keep only the game ending conditions i.e. connect-4 and return a -value. But then this will offer least tactics for the computer player making it very easy to play against,hence I programed three in a row and more conditions like that. But now the computer focuses on connecting three or blocking three,forgeting about 4.
Has any one ever experienced such type of problem?
Advertisement
No, that's not a common problem. Can you post your evaluation function?
Is it possible that you're getting an alpha trigger every time it sees three in a row? This might prevent it from exploring any further..

Alvaro, didn't you find a simple solution to Connect-4 when you were in college? :)
Quote:Original post by willh
Alvaro, didn't you find a simple solution to Connect-4 when you were in college? :)

No, no simple solution. But I did learn how to play the game well, and I managed to put my knowledge into a program that was pretty strong. If I were writing a program these days I think I would go for optimal play, since weakly solving the game only takes a few minutes (google for "Fhourstones").

@alvaro and @willh:
Thank you for replying and trying to help me in this case.
Fhourstones was I guess programed by Mr.Tromp.(heavy stuff)
Since this is my primary version of game, I have programed it using simple 2-d arrays(Its not as fast as bit board which are developed by Mr.Tromp, but after all this is my first version in programing connect-4,later on if required I can re program the game in bit-boards if required,but for that I should get my basic concepts cleared.)

Here is my evaluation function:
 public static char[] board_one_d = new char[42];    static int r, c, rows = 6, cols = 7;    public static int fscore = -1000;    static int _3inr = 5;    static int _2inr = 1;       static int EMPTY='1';    public static int evaluate(char[][] board, boolean white) {        char color = white ? 'x' : 'o';        int eval = 0;        //Winning.        for (r = 0; r < rows; r++) {            for (c = 0; c < cols - 3; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r][c + 1]                        && board[r][c] == board[r][c + 2]                        && board[r][c] == board[r][c + 3]) {                    eval = fscore;                                  }            }        }// check for a vertical win        for (r = 0; r < rows - 3; r++) {            for (c = 0; c < cols; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r + 1][c]                        && board[r][c] == board[r + 2][c]                        && board[r][c] == board[r + 3][c]) {                    eval = fscore;                                    }            }        }// check for a diagonal win (positive slope)        for (r = 0; r < rows - 3; r++) {            for (c = 0; c < cols - 3; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r + 1][c + 1]                        && board[r][c] == board[r + 2][c + 2]                        && board[r][c] == board[r + 3][c + 3]) {                    eval = fscore;                                }            }        }// check for a diagonal win (negative slope)        for (r = 3; r < rows; r++) {            for (c = 0; c < cols - 3; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r - 1][c + 1]                        && board[r][c] == board[r - 2][c + 2]                        && board[r][c] == board[r - 3][c + 3]) {                    eval = fscore;                                   }            }        }//3in a r        for (r = 0; r < rows; r++) {            for (c = 0; c < cols - 2; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r][c + 1]                        && board[r][c] == board[r][c + 2]) {                    eval = eval + _3inr;                }            }        }// check for 3-a vertical         for (r = 0; r < rows - 2; r++) {            for (c = 0; c < cols; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r + 1][c]                        && board[r][c] == board[r + 2][c]) {                    eval = eval + _3inr;                }            }        }// check for 3-a diagonal (positive slope)        for (r = 0; r < rows - 2; r++) {            for (c = 0; c < cols - 2; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r + 1][c + 1]                        && board[r][c] == board[r + 2][c + 2]) {                    eval = eval + _3inr;                }            }        }// check for 3- a diagonal  (negative slope)        for (r = 2; r < rows; r++) {            for (c = 0; c < cols - 2; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r - 1][c + 1]                        && board[r][c] == board[r - 2][c + 2]) {                    eval = eval + _3inr;                }            }        }        //Two in r        for (r = 0; r < rows; r++) {            for (c = 0; c < cols - 1; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r][c + 1]                        ) {                    eval = eval + _2inr;                }            }        }// check for 3-a vertical        for (r = 0; r < rows - 2; r++) {            for (c = 0; c < cols; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r + 1][c]                       ) {                    eval = eval + _2inr;                }            }        }// check for 3-a diagonal (positive slope)        for (r = 0; r < rows - 2; r++) {            for (c = 0; c < cols - 2; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r + 1][c + 1]                        ) {                    eval = eval + _2inr;                }            }        }// check for 3- a diagonal  (negative slope)        for (r = 2; r < rows; r++) {            for (c = 0; c < cols - 2; c++) {                if (board[r][c] != EMPTY                        && board[r][c] == board[r - 1][c + 1]                       ) {                    eval = eval + _2inr;                }            }        }        //....  return eval;    }


Also if possible kindly give me some hints for wrinting more sophisticated evaluation.
I know the basics of connect 4(odd row threats for player1, double threats even row threats for player2) but before I start adding these stuffs, it would be better for me to get all the concepts and method of programing correctly.

I can see several problems with your code:

* Your evaluation function should return a positive score if the side to move seems to be winning, and a negative score if it seems to be losing. It's a good thing that you passed the parameter white and you defined color, but you then never use them, so you have no way of returning what you are supposed to.
* Continuing with the sign problems, you seem to add positive numbers to the score, regardless of which player has the desired features. You should add positive numbers when the player to move has the desired features, and negative numbers when it's the opponent who has the desired feature.
* Detecting four in a row shouldn't even be part of the evaluation function. You should have a function that detects the end of the game, and this should be called every time in the search (AlphaBeta) function, so you don't keep trying moves after the game is over.
* Three in a row is not a threat unless it has an empty space on one end. You should be interested in detecting places that can eventually lead to a win, but this means that you should loop over the spots where you can make four in a line and give a bonus when a player has three of the four spots and the other spot is empty.

I have returned the +evl or - eval depending on the turn to move, if the player is white, return +ve score else return -ve score.
Empty spacing coding,I would do later on your approval of this code.

//3in a row(row3).        for (row = 21; row <= 25; row++) {            if ((board1d[row] == board1d[row + 1] && board1d[row] == board1d[row + 2] && board1d[row] == 'x')                    && board1d[row + 7] == board1d[row + 8] && board1d[row + 7] == board1d[row + 9] && board1d[row + 7] != 'y') {                eval = eval + _3inrowinodd;            }        }        //row5        for (row = 7; row <= 13; row++) {            if ((board1d[row] == board1d[row + 1] && board1d[row] == board1d[row + 2] && board1d[row] == 'x')                    && board1d[row + 7] == board1d[row + 8] && board1d[row + 7] == board1d[row + 9] && board1d[row + 7] != 'y') {                eval = eval + _3inrowinodd;            }        }//Diagonal '\'        for (row = 0; row <= 3; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 8] == EMPTY) && (board1d[row] == board1d[row + 16]) && (board1d[row] == board1d[row + 24]) && (board1d[row] == 'x')) {                eval = eval + _3inrowinodd;            }        }        for (row = 7; row <= 10; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 8] == EMPTY) && (board1d[row] == board1d[row + 16]) && (board1d[row] == board1d[row + 24]) && (board1d[row] == 'x')) {                eval = eval + _3inrowinodd;            }        }        for (row = 14; row <= 17; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 8] == EMPTY) && (board1d[row] == board1d[row + 16]) && (board1d[row] == board1d[row + 24]) && (board1d[row] == 'x')) {                eval = eval + _3inrowinodd;            }        }        //Diagonal '/'        for (row = 3; row <= 6; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 6] == EMPTY) && (board1d[row] == board1d[row + 12]) && (board1d[row] == board1d[row + 18])) {                eval = eval + _3inrowinodd;            }        }        for (row = 3; row <= 6; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 6] == EMPTY) && (board1d[row] == board1d[row + 12]) && (board1d[row] == board1d[row + 18])) {                eval = eval + _3inrowinodd;            }        }        for (row = 10; row <= 13; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 6] == EMPTY) && (board1d[row] == board1d[row + 12]) && (board1d[row] == board1d[row + 18])) {                eval = eval + _3inrowinodd;            }        }        for (row = 17; row <= 20; row++) {            if (((row / 7) % 2 != 0) && (board1d[row + 6] == EMPTY) && (board1d[row] == board1d[row + 12]) && (board1d[row] == board1d[row + 18])) {                eval = eval + _3inrowinodd;            }        }        return white ? eval : -eval;//Is this the way to do it?    }


I have programed 2 AI games(tictactoe and this connect-4).My hobby is playing chess and would like to build chess game of my own one day(and then keep improving it as how Crafty was done though I am in no position to compare my future chess program with Crafty) and keep it as on going hobby, you as a better and experienced programer, think that I should start it or wait and learn other things so that I am conceptually correct in building chess or build another simple game.
Please reply.

[Edited by - ashish123 on December 26, 2010 9:41:32 AM]
You should definitely continue working on your connect 4 program before you move into chess. A lot of what you learn here will help you when writing your chess program.
@alvaro, I will follow your suggestion
I made a short survey on game playing ai(s), it seems most of them are programmed in C/C++. major game developers stay away from java because its slow(I know object creation does take time and when in recursive loop,it gets multiplied) .
So decided to go for C++. Since I am writing the connect4 program from past two months,but yet didnot get it right,and that is because I donot have computer programing background(I am a junior chemistry person).and so I did mess up the code just by following the pseudocode with out getting its insights.
So I think I need to organize myself and forget for the game programing at this moment and learn C++ and the data structures and algorithm analysis.

Please add to this if I am missing something or if my path is wrong(again).
Thank you.
It's true that "real" engines are written in C or C++ most of the time, but that doesn't mean that you have to do that. You can learn about the algorithms while programming in any language, so you can just use whatever you are familiar with for the time being.

On the other hand, you should definitely learn C or C++ if you are serious about board-game programming. I keep mentioning C because that's the most important part of C++ for this purpose. Using C++'s strings and containers makes a lot of things very easy, but you should be very careful not to allocate and release memory during the search, because that's just too slow (and there is no need to do it).

This topic is closed to new replies.

Advertisement