PDA

View Full Version : Move from alphabeta



OhSoInsane
05-04-2008, 12:16 PM
Hey there,

I am currently making a chess engine using the alpha beta algorithm:



int AlphaBeta(int depth, int alpha, int beta)

{
if (depth == 0)
return Evaluate();

GenerateLegalMoves();

For allMoves{
MakeNextMove();
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove();
if (val >= beta)
return beta;
if (val > alpha)
alpha = val;
}
return alpha;
}


How do i get the best move from this?

Thanks

Kruupy
05-04-2008, 02:41 PM
Hi OhSoInsane.

could u please post some more info on the alpha beta algorithm so I may be able to get an idea of what it is so that I may be able to help you?

Rincewind
05-04-2008, 05:34 PM
I've never written a chess playing engine but my impression from the code above is this...

The best move is the one that returns the highest alpha value. The code above isn't storing the moves anywhere I think you should probably have a global array and when you get a good move (that is when you update the alpha value insid the if statement at the end of the loop) then store it with something like...

moves[depth] = current move.

Then when AlphaBeta finishes the array should have the move tree of the best variation.


If you have trouble following the alpha-beta runing algorithm then you could just implement a simpler Minimax algorithm and introduce AlpgaBeta after you have the mechanics of Minimax worked out.

OhSoInsane
06-04-2008, 11:21 AM
Thanks for the input guys.

But I don't think putting the bestmove = move[depth] will work. This is because the program updates alpha even at all the childs, so the bestmove may not necessarily store the parent move if you get what i mean.

As for the code, I am making this engine in a different language which does not support changing values of a parameter variable so i have to use tempAlpha variable, does that create any problems? Please do check my code:



fcn alphaBeta (depth : int, alpha : int, beta : int, turn : int) : int
var tempAlpha := alpha
if (depth = 0) then
result evaluate (board, turn)
end if

GenerateLegalMoves (turn) %Remember to free the flexible array when the procedure begins

nodes += 1
for x : 1 .. upper (moves)

MakeNextMove (moves (x))


val := -alphaBeta (depth - 1, -beta, -alpha, 1 - turn)

UnmakeMove (moves (x))

if (val >= beta) then
result beta
end if
if (val > tempAlpha) then
tempAlpha := val
end if
end for
result tempAlpha
end alphaBeta


Basically the Generatemoves procedures generates all the moves for the legal turn in the dynamic array called "moves".

So now, how to do i get the move that yields the best move?

Rincewind
06-04-2008, 12:00 PM
But I don't think putting the bestmove = move[depth] will work. This is because the program updates alpha even at all the childs, so the bestmove may not necessarily store the parent move if you get what i mean.

What's why you store it in an array indexed by depth.

After the parent call to AlphaBeta is finished the best move is stored in the element bestmove[depth] where depth is the value you called AlphaBeta with.

The strongest line would be derivable from

for (i = depth; i > 0; i--)
print(bestmove[i]);

Make sense?

OhSoInsane
06-04-2008, 12:45 PM
Ok, so i added this:



if (val > tempAlpha) then
tempAlpha := val

new bestMove, upper (bestMove) + 1
bestMove (upper (bestMove)).pieceType := moves (x).pieceType
bestMove (upper (bestMove)).x := moves (x).x
bestMove (upper (bestMove)).y := moves (x).y
bestMove (upper (bestMove)).px := moves (x).px
bestMove (upper (bestMove)).py := moves (x).py
end if


this basically creates a new dimension on the best array and adds all the data to that array from the moves array.

I searched with a depth of 3 to begin with (i know that ain't getting me anywhere but its just for debugging purposes right now) but it gave me a funny answer, the moves im generating are right cause i debugged it.

After the function has finished, i did this for output:



put bestMove (3).pieceType
put bestMove (3).px
put bestMove (3).py
put bestMove (3).x
put bestMove (3).y


What could be wrong?

OhSoInsane
07-04-2008, 07:37 AM
I think the tempAlpha variables is causing the problems. Is there a way to use tempAlpha and still get the right answer? i mean, too bad the lang doesnt support change of parameter values...