This is an iterative implementation of alpha beta tree search in C#. Please help me confirm the correctness of my code. search()
is called when the search begins.
int depth;
Func<board, int> value;
Func<board, List<string>> legalmoves;
Random randomgenerator = new Random();
board board;
Stack<int> alphas = new Stack<int>();
Stack<int> betas = new Stack<int>();
Stack<int> calllevels = new Stack<int>();
Stack<string> nodesleft = new Stack<string>();
Stack<string> callstack = new Stack<string>();
void search()
{
alphas.Push(int.MinValue);
betas.Push(int.MaxValue);
pushlegalmoves();
//initialize the alpha, beta, and push all legal moves
while (nodesleft.Any())
{
string currentnode = nodesleft.Pop();
int calllevel = calllevels.Count;
int movesleft = calllevels.Pop();
callstack.Push(currentnode);
move(currentnode);
//extract all information about the node and play the move
if (calllevel != depth)
{
calllevels.Push(movesleft);
alphas.Push(alphas.First());
betas.Push(betas.First());
pushlegalmoves();
//expand the tree if not terminal(aka not enough depth here)
}
else
{
if (calllevel % 2 == 0) max(calllevel, movesleft, currentnode);
else min(calllevel, movesleft, currentnode);
//cleanup and process everything if node is terminal
}
}
}
void max(int calllevel, int movesleft, string currentnode)
//cleans up and processes tree, starting from a max player terminal node
{
bool color = true;
bool cleanup = false;
//color means which player is the function currently processing. true = max player, false = min player
//cleanup means whether to process the the search tree up to the next level
int score = value(board);
if (score >= betas.First())
{
cleanup = true;
score = betas.First();
}
if (score > alphas.First())
{
alphas.Pop();
alphas.Push(score);
}
if (movesleft == 1) cleanup = true;
unmove(callstack.Pop());
//changes the alpha and beta values. if the move is last move or a beta cutoff is issued, then clean up the current tree level. undo the current move.
while (cleanup)
{
color = !color;
cleanup = false;
//change the player. reset whether to clecan up
for (; movesleft > 0; movesleft--)
{
nodesleft.Pop();
}
movesleft = calllevels.Pop();
unmove(callstack.Pop());
alphas.Pop();
betas.Pop();
//climbing up the next level
if (color)
{
if (score >= betas.First())
{
cleanup = true;
score = betas.First();
}
if (score > alphas.First())
{
alphas.Pop();
alphas.Push(score);
}
}
else
{
if (score <= alphas.First())
{
cleanup = true;
score = alphas.First();
}
if (score < betas.First())
{
betas.Pop();
betas.Push(score);
}
}
if (movesleft == 1) cleanup = true;
//processing the next level and deciding whether to keep cleaning up
}
calllevels.Push(movesleft - 1);
//puts in the correct number of unprocessed moves
}
void min(int calllevel, int movesleft, string currentnode)
//cleans up and processes tree, starting from a min player terminal node
{
bool color = false;
bool cleanup = false;
//color means which player is the function currently processing. true = max player, false = min player
//cleanup means whether to process the the search tree up to the next level
int score = -value(board);
if (score <= alphas.First())
{
cleanup = true;
score = alphas.First();
}
if (score < betas.First())
{
betas.Pop();
betas.Push(score);
}
if (movesleft == 1) cleanup = true;
unmove(callstack.Pop());
//changes the alpha and beta values. if the move is last move or a alpha cutoff is issued, then clean up the current tree level. undo the current move.
while (cleanup)
{
color = !color;
cleanup = false;
//change the player. reset whether to clecan up
for (; movesleft > 0; movesleft--)
{
nodesleft.Pop();
}
movesleft = calllevels.Pop();
unmove(callstack.Pop());
alphas.Pop();
betas.Pop();
//climbing up the next level
if (color)
{
if (score >= betas.First())
{
cleanup = true;
score = betas.First();
}
if (score > alphas.First())
{
alphas.Pop();
alphas.Push(score);
}
}
else
{
if (score <= alphas.First())
{
cleanup = true;
score = alphas.First();
}
if (score < betas.First())
{
betas.Pop();
betas.Push(score);
}
}
if (movesleft == 1) cleanup = true;
//processing the next level and deciding whether to keep cleaning up
}
calllevels.Push(movesleft - 1);
//puts in the correct number of unprocessed moves
}