How do you implement Alpha-Beta search when you can only compare 2 positions to each other?

Question

In their paper about DeepChess, http://www.cs.tau.ac.il/~wolf/papers/deepchess.pdf, David et al show a cool way to train a net to play chess. I've trained my net to some degree of success and I want to test how well it performs in play. The neural net can only compare 2 positions to each other - it has no static evaluation function. The paper briefly talks about Alpha-Beta search for this net. I'm trying to write the pseudo-code for this algorithm, and would appreciate any help:

function alphabeta(node, depth, α, β, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return eval(node, α, β, maximizingPlayer)
      if maximizingPlayer
          v := -∞
          for each child of node
              α := alphabeta(child, depth – 1, α, β, FALSE)
              if net(β, α) == β //beta is the winner
                  break (*β cut-off *)
          return α 
      else
          v := ∞
          for each child of node
              β := alphabeta(child, depth – 1, α, β, TRUE)
              if net(β, α) == α //alpha is the winner
                  break (* α cut-off *)
          return β 

function eval(node, depth, α, β, maximizingPlayer)
    if maximizingPlayer and net(node,α) == α //alpha is the winner
         α = node
    if not maximizingPlayer and net(node,β) == β //beta is the winner
         β = node 

Am I on the right track? Is this totally wrong? I know that I haven't account for no legal moves, which means I have to return negative infinity, and I'm also not sure how to initiate the call... Any help would be appreicated!

Answer 1

This looks right to me, but there are two big caveats, one technical nitpickery in your pseudocode and one much deeper. The nitpickery is that your net() function shouldn't return a position because comparing positions is expensive; instead it should return something along the lines of 'left is better' or 'right is better' (i.e., a boolean) and your conditionals should be on the value of that boolean.

Your negative infinity case (as well as initiation) can be handled pretty easily with sentinel positions: these are fake positions that serve exactly the same function that −∞ does in 'traditional' alpha-beta, in that (using your pseudocode convention) net(sentinel, P) will always return that P is better for any (non-sentinel) position P. (The simplest way of doing this is likely with something like an IsSentinel boolean in the position structure, but that's a very code-specific decision).

There's a much deeper caveat, though: you're making the implicit assumption in this pseudocode that your neural network is linearly ordering positions, or at least close enough to linearly ordering them to make this algorithm viable; that is, there are no three positions A, B, C with A<B, B<C, but C<A (where A<B here is just shorthand for 'net(A,B) returns that B is better'). If your neural network isn't at some level returning a value for each position, or at least the results of comparing two values one generated from each position, then it's almost certain that it will run into some measure of this 'rock-paper-scissors' issue. Unfortunately, there isn't an easy answer there, because the very premise of game tree search (that there is an Objectively Best position) breaks down in that case. There are certainly ways of trying to tackle that issue, but now we're starting to get into thesis-level research mathematics, in the sense that you could probably get a pretty good thesis out of working through various approaches to the problem...