How to select a node using Alpha Beta

Question

I am implementing an AI for an Othello game using MiniMax with Alpha Beta pruning. I have implemented an Alpha Beta algorithm that tells me the value that I can obtain, but not which node it is that I should select? So my question is how can I use Alpha-Beta to tell me which node I should select, not what the resultant value would be. Here is the pseudocode for my Alpha-Beta algorithm.

01 function alphabeta(node, depth, α, β, maximizingPlayer)
02      if depth = 0 or node is a terminal node
03          return the heuristic value of node
04      if maximizingPlayer
05          v := -∞
06          for each child of node
07              v := max(v, alphabeta(child, depth – 1, α, β, FALSE))
08              α := max(α, v)
09              if β ≤ α
10                  break (* β cut-off *)
11          return v
12      else
13          v := ∞
14          for each child of node
15              v := min(v, alphabeta(child, depth – 1, α, β, TRUE))
16              β := min(β, v)
17              if β ≤ α
18                  break (* α cut-off *)
19          return v

Answer 1

If you only want to know the best move in the root position, it is enough to remember which move in the root position had the highest score. For that, just returning the score is enough. No change in the pseudo-code is necessary.

As you are asking about the path to the critical node, I guess you are asking about a way to reconstruct the principal variation, which gives insights about the series of moves that the search expected.

In theory, you can just return the value and the principal variation from the recursive call. That allows you to reconstruct the path. Triangular PV-Tables are data structures optimized for that purpose.

If your search uses a transposition table, a simpler approach is just to start the root position and look up the best move in the transposition table. Then make that move and repeat (look up the best move, make the best move, lookup again, etc.) until the game is over or no entry has been found. In the end, the moves that were made are the principal variation.

The transposition table approach is not as precise as explicitly keeping track of the principal variation, but it is simple to implement and adds no overhead during the search.