C++

Forum

 
Help implementing AlphaBeta

Niven (114)
Using the follow pseudocode as a basis, I wrote a class for performing minimax with the alphabeta algorithm: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
   function alphabeta(node, depth, α, β, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return the heuristic value of node
      if maximizingPlayer
          for each child of node
              α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
              if β ≤ α
                  break (* β cut-off *)
          return α
      else
          for each child of node
              β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
              if β ≤ α
                  break (* α cut-off *)
          return β
http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning#Pseudocode

When everything looked good and I was finished (or at least I thought I was), I compiled my code and found one major bug. The program crashes whenever the GetChoice function (implementation below) is called. All the code I thing should be relevant to the issue is below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
template<class T>
float MiniMax_Branch<T>::GetValue(int Depth, float Alpha, float Beta)
{
    if ( Depth >= MaxDepth )
        return StaticEvaluation(Representative, Type);
    else
    {
        if ( Type == MINIMAX_MAX )
        {
            while ( GenerateMove(this, Children.size()) )
            {
                Alpha = Max( Alpha, Children.back()->GetValue(Depth+1,Alpha,Beta) );
                if ( Beta <= Alpha )
                    break;
            }
            if ( Children.size() == 0 )
                return StaticEvaluation(Representative, Type);

            return Alpha;
        }
        else
        {
            while ( GenerateMove(this, Children.size()) )
            {
                Beta = Min( Beta, Children.back()->GetValue(Depth+1,Alpha,Beta) );
                if ( Beta <= Alpha )
                    break;
            }
            if ( Children.size() == 0 )
                return StaticEvaluation(Representative, Type);

            return Beta;
        }
    }
}

template<class T>
T* MiniMax_Branch<T>::GetChoice()
{
    while ( GenerateMove(this,Children.size()) ) ///Make all the children for the origin node
        NULL;

    struct
    {
        unsigned short Index;
        float Value;
    } BestChild;
    BestChild.Index = 0;
    BestChild.Value = Children[0]->GetValue(1);

    for ( int i = 1; i < Children.size(); i++ )
    {
        float Value = Children[i]->GetValue(1);
        if ( Value > BestChild.Value && Type == MINIMAX_MAX )
        {
            BestChild.Index = i;
            BestChild.Value = Value;
        }
        else if ( Value < BestChild.Value && Type == MINIMAX_MINI )
        {
            BestChild.Index = i;
            BestChild.Value = Value;
        }
    }

    return Children[BestChild.Index]->Representative;
}


Some notes about variables and stuff:
1
2
3
4
5
6
 
*Children is a vector of MiniMax_Branch<T>* 
*T represents the object minimax is being performed on (In my current case, tic-tac-toe boards)
*Representative is a T* that points to the T associated with that branch/node
*GenerateMove and StaticEvaluation generate a single child node and add it to the tree/evaluate a node with no children
*When I use my debugger, it reports the crash at line 29 (not a typo), and I have no idea how that line could cause a crash
*Alpha and Beta are initialized with essentially -inf and +inf


Does anyone have any idea what the problem could be or does anyone need more information about the program to be able to help? Thanks in advance.
Topic archived. No new replies allowed.