Sign in to follow this  

Help in understanding Negamax and Alpha-Beta Pruning

This topic is 2541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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? :)

Share this post


Link to post
Share on other sites
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").

Share this post


Link to post
Share on other sites
@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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
@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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites

This topic is 2541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this