Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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. Thanks in advance.

            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
            }
share|improve this question
4  
You need to change your user name. –  codesparkle Nov 25 '12 at 10:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.