0
\$\begingroup\$

I'm stuck with coding the Alpha Beta algorithm for a console-based game I'm developping at the moment. I tried to understand how it works for a week but still no idea how to get started with it. Here is the algorithm in pseudo-code :

    minimax (in game board, in int depth, in int max_depth,
         in boolean alpha_beta, in score black_best, in score white_best, 
         out score chosen_score, out score chosen_move)
begin
        :   
        :
        minimax(new_board, depth+1, max_depth,
                alpha_beta, black_best, white_best, 
                the_score, the_move);
        if (alpha_beta) then
            if (to_move(black) and (the_score > black_best))
                if (the_score > white_best)
                    break;  /*  alpha_beta cutoff  */
                else
                    black_best = the_score;
                endif
            endif
            if (to_move(white) and (the_score < white_best))
                if (the_score < white_best)
                    break;  /*  alpha_beta cutoff  */
                else
                    white_best = the_score;
                endif
            endif
        endif
        :
        :
end.

I've already done the Min Max algorithm for a fixed depth of 2. Minmax pseudo-code :

minimax(in game board, in int depth, in int max_depth,
        out score chosen_score, out score chosen_move)
begin 
    if (depth = max_depth) then
        chosen_score = evaluation(board);
    else 
        moves_list = generate_moves(board);
        if (moves_list = NULL) then
            chosen_score = evaluation(board);
        else 
            for (i = 1 to moves_list.length) do
                best_score = infinity;
                new_board = board;
                apply_move(new_board, moves_list[i]);
                minimax(new_board, depth+1, max_depth, the_score, the_move);
                if (better(the_score, best_score)) then
                    best_score = the_score;
                    best_move = the_move;
                endif
            enddo
            chosen_score = best_score;
            chosen_move = best_move;
        endif
    endif
end.

and my code (it is really messy sorry for that) :

char *minimax (Data *t, Data *u)
{
    int bestScore1=0, bestScore2=0, i,p,k,pn1=0,pb1=0,pn2=0,pb2=0, bestMove=0,score1=0,score2=0;
    Data *saveState1,*saveState2;
    saveState1=malloc(sizeof(Data));
    saveState2=malloc(sizeof(Data));
    *saveState1=*t; //Saving the state of the game before testing a move (first row which is AI's move)

    for (i=11; i<89; i++)
    {
        *t=*saveState1;

        if (check(i,t,u,1) > 0) //We're checking if the cell i is playable for WHITES
        {
            t->p[i]=BLANC; //Make the move (BLANC = WHITE in french)

            pn1=0; pb1=0; //PN1: number of BLACKS PB1: number of WHITES
            for (k=11;k<89;k++) //counts the white and black game pieces
            {
                if(t->p[k]==NOIR)
                    pn1++;
                else if(t->p[k]==BLANC)
                    pb1++;
                //printf("\npb1=%d",pb1); //DEB
            }
            score1=pb1-pn1; //Save the score
            if (score1 > bestScore1) //Set as best score if better than previous
                bestScore1=score1;
            *saveState2=*t; //Saving state for second row which is the player's move
            //printf("\n%s played by white",tostring(i)); //DEB
            for (p=11; p<89; p++) //Testing all the cells of the game
            {
                *t=*saveState2; //saving state before making a move

                if (check(p,t,u,-1)) //Checking if BLACK can play the cell i
                {
                    t->p[p]=NOIR; //Do the actual move

                    pn2=0; pb2=0; //PN: number of BLACKS PB: number of WHITES
                    for (k=11;k<89;k++) //Counts the white and black game pieces
                    {
                        if(t->p[k]==NOIR)
                            pn2++;
                        else if(t->p[k]==BLANC)
                            pb2++;
                            //printf("\npb2=%d",pb2); //DEB
                    }
                    score2=pb2-pn2; //Saving score for second row
                    if (score2 > bestScore2) //Setting score as bestScore if better than previous
                    {
                        bestScore2=score2;
                        bestMove=i;
                    }
                    else if (score2 == 0 || score1 == 0) //Setting default move if scores are ex aequo
                    {
                        bestMove=i;
                    }
                    else if (score2 < 0 || score1 < 0) //Setting default move if both scores are making the AI lose points
                    {
                        bestMove=i;
                    }
                    //printf("\n%s played by black",tostring(p)); //DEB
                    //printf("\nscore1=%d\tscore2=%d\tbestMove=%s",bestScore1,bestScore2,tostring(bestMove)); //DEB
                }
            }
        }
    }
    return bestMove;
}

Where *t is the array representing the current game and *u the precedent state of the game. Each array has 100 cells with the following values :

  • 0 : black
  • 1 : white
  • 2 : empty
  • 3 : border

Thanks for reading and sorry for the bad english skills. Sources : http://pressibus.org/ataxx/autre/minimax/node2.html

\$\endgroup\$
  • \$\begingroup\$ Asking a bunch of people you don't know to read code you admit is messy is a sketchy proposition at best. \$\endgroup\$ – Almo Apr 10 '15 at 19:10
  • \$\begingroup\$ @Almo Do you think I should delete this post? \$\endgroup\$ – Hardrow Apr 10 '15 at 19:18
  • \$\begingroup\$ I would say that you should format your code properly so it's more legible before asking other people to read it and help you find problems in it. Second, asking narrower questions gets better help faster. But I'm undecided about whether the question in its current form is ok for the site or not. Usually super-bad questions get flagged and held almost immediately, so maybe just edit the code bits for clarity and see what happens. Incidentally, my first minimax AI was for Othello. :) \$\endgroup\$ – Almo Apr 10 '15 at 19:41
  • \$\begingroup\$ alpha-beta is a method to chose your next move, given the opponents most likely next move. In general each possible next position is evaluated via the min-max strength. (you want to maximize your position while minimizing the opponents position.) The alpha-beta algorithm is a method to eliminate non productive sequences of moves from consideration. you might want to read: <en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning> for details \$\endgroup\$ – user3629249 Apr 10 '15 at 19:41
  • \$\begingroup\$ @Almo Thanks, I will make it as clear as I possibly can. \$\endgroup\$ – Hardrow Apr 12 '15 at 23:20
1
\$\begingroup\$

There are a lot of resources on the web for understanding alpha-beta. This short video will probably help you understand: https://www.youtube.com/watch?v=xBXHtz4Gbdo

My 1st game was an alpha-beta Othello, back in 1981. Good luck!

Footnote: once you get alpha-beta working, if you want to search deeper, I recommend the "MTD(f)" algorithm with "Iterative Deepening".

\$\endgroup\$
0
\$\begingroup\$

here is the alpha-beta algorithm definition:

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.[1]

\$\endgroup\$
  • \$\begingroup\$ It looks like the question is not asking for the definition but rather how the algorithm itself works. AKA how to algorithmically find if one move is worse than another. \$\endgroup\$ – Superdoggy Apr 10 '15 at 20:10
  • \$\begingroup\$ It is exactly what @Superdoggy said that I'm searching for. I understand what is the purpose of using it but I've got no idea how to make it work for my program. \$\endgroup\$ – Hardrow Apr 12 '15 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.