Iterative implementation of alpha beta tree search

Question

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
}

Answer 1

Readability

The indentation is good and you have good variable names, but some of them are hard to read. Why? More or less because they're lowercase. Variables and parameters should be camelCase.

• calllevels >> callLevels
• nodesleft >> nodesLeft
• callstack >> callStack

Method names like search and max should be PascalCase. In other words, Search and Max.

---

This could use some braces.

else
{
    if (calllevel % 2 == 0) max(calllevel, movesleft, currentnode);
    else min(calllevel, movesleft, currentnode);
    //cleanup and process everything if node is terminal
}

It seems like a minor thing, but if you go to change it later, and forget to add braces then, it could cause trouble.

---

I'm not a big fan of for loops without an index declared right in it. Opt for a while loop instead.

for (; movesleft > 0; movesleft--)
{
    nodesleft.Pop();
}

Vs

while (movesLeft > 0) 
{
    nodesLeft.Pop();
    movesLeft--;
}

---

It's not obvious to me how to fix it, but there should be some way to clean up the seeming duplication here. It should be possible to write a single function to do this work. Perhaps it takes a boolean parameter. I'm not sure, but I know there's a way.

                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);
                    }
                }

---

Here is some duplication that we can pretty easily fix. There are a lot of places where you Pop an item off the stack and immediately push the score on. Replace every instance of it with a method. It's a small step toward DRYing this up.

private void PopThenPushScore(Stack<int> stack, int score)
{
    stack.Pop();
    stack.Push(score);
}