Chess

Claude Shannon (1916-2001):

• A pioneer in math, CS and electrical engineering.

• Major contributions:
  • Boolean logic (based on Boolean algebra).
  • The idea that Boolean algebra can be used to optimize and realize circuits for binary arithmetic.
  • Cryptography.
  • Information theory and communications
          → How can you encode symbols so that they can be transmitted over noisy media?
  • Game trees for chess (1950).

• Also, the Ultimate Machine

  Exercise: Look up the ultimate machine on youtube.

Shannon's game tree:

• The idea:
  • Express possible moves as a minimax (game) tree.
  • Every node in the tree is a game configuration (possible arrangement of pieces).
  • Devise an evaluation function to score a configuration.
  • Search tree for optimal moves.

• Two types of searches:
  • Type-A search: search completely until some fixed depth.
  • Type-B search: search some tree paths more than others.

Let's look a little deeper into game trees:

• First, some assumptions:
  • This is for two-person games, with strict alternation.
  • Given a position, the history of how you got there doesn't matter
          → The rest of the game only depends on the current position.
  • The game is a zero-sum game
          → Roughly, a high evaluation for player A is a low one for player B.
          → The same evaluation function works for both players (with opposite meaning).
  • The evaluation function only assesses a particular position (configuration).
          → It does not score "how you got there".
  • Most important: both player play optimally.

• Notation: Players A and B, with A playing first.

• Example: a part of a tic-tac-toe game tree:

  

  • Let a winning position for A be given a score of 1.
  • A winning position for B has a score of -1 (from A's point of view).

The minimax formulation:

• Player A is called Max
        → Will maximize score.

• Player B is called Min
        → Will minimize score.

• Consider working bottom up through a game tree:

  

  • Player B picks the best move for B at each of the three B possibilities
          → e.g., min (24, 32) = 24
  • This is defined as the value of the first interior node for B.
  • At the next level, A picks max(24,16,11)
          → The value at the upper A node is 24 (best move for A).

• We can write this recursively:

  
       value(node) = score(node),      if node is a terminal node
                     maxs value(s),    (over successors s), if node is a max-node (A-node).
                     mins value(s),    if node is a min-node (B-node).
       

• Which translates into an algorithm:

  
       Algorithm: findMax (state)
       Input: the current "board" or state
       1.   if state is terminal
       2.      return value (state)
       3.   endif
  
            // Search recursively among child states
       4.   S = generate successor states
       5.   maxValue = -∞
       6.   for s ε S
       7.      v = findMin (s)
       8.      if v > maxValue
       9.         maxValue = v
       10.     endif
       11.  endfor
       12.  return maxValue
  
       Algorithm: findMin (state)
       Input: the current "board" or state
       1.   if state is terminal
       2.      return value (state)
       3.   endif
  
            // Search recursively among child states
       4.   S = generate successor states
       5.   minValue = -∞
       6.   for s ε S
       7.      v = findMax (s)
       8.      if v > minValue
       9.         minValue = v
       10.     endif
       11.  endfor
       12.  return minValue
       

• This computes the best value at each intermediate node, but what about the best move?
        → We need to record the move that achieved the best value.

• Let's re-write findMax for this purpose:

  
       Algorithm: findMax (state)
       Input: the current "board" or state
       1.   if state is terminal
       2.      return (null, value(state))
       3.   endif
  
            // Search recursively among child states
       4.   M = generate all possible moves
       5.   maxValue = -∞
       6.   for m ε M
       7.      s = state (m)          // s is the state you get when applying move m
       8.      (m',v) = findMin (s)   // m' is the best min move
       9.      if v > maxValue
       10.        maxValue = v
       11.        bestMove = m
       12.     endif
       13.  endfor
       14.  return (bestMove, maxValue)
       

  findMin is similarly modified.

• How does this apply to an actual game?
  • At any moment in the game, when it's A's turn with state s, A executes

    	 1.  (m, v) = findMax (s)
    	 2.  play move m
           

• Note: Shannon used the mathematical formulation of minimax for game theory
        → From Von Neuman and Morgenstern

Exercise: Apply the minimax algorithm to this game tree:

Do all subtrees need to be explored?

• Consider this example with part of the tree explored:

  

• Suppose we knew the max-value A=24

  

  • After we have explored the B=24 node, we next explore the B=16 node.
  • There is no need to explore the right child of B=16.
          → Because this is already lower than α=24

• Suppose we recorded the "best so far" during execution

  

• The alpha-beta algorithm:

  
       Algorithm: findMax (state, α, β)
       Input: the current "board" or state
       1.   if state is terminal
       2.      return (null, value(state))
       3.   endif
  
            // Search recursively among child states
       4.   M = generate all possible moves
       5.   maxValue = -∞
       6.   for m ε M
       7.      s = state (m)                // s is the state you get when applying move m
       8.      (m',v) = findMin (s, α, β)   // m' is the best min move
       9.      if v > maxValue
       10.        maxValue = v
       11.        bestMove = m
       12.     endif
               // If we've exceeded some earlier B's min-value, there's no point searching further in this A-node's children.
       13.     if maxValue ≥ β
       14.        return (bestMove, maxValue)
       15.     endif
               // Update this node's best value so far.
       16.     if maxValue > α
       17.        α = maxValue
       18.     endif
       19.  endfor
       20.  return (bestMove, maxValue)
       

  
       Algorithm: findMin (state, α, β)
       Input: the current "board" or state
       1.   if state is terminal
       2.      return (null, value(state))
       3.   endif
  
            // Search recursively among child states
       4.   M = generate all possible moves
       5.   minValue = ∞
       6.   for m ε M
       7.      s = state (m)                // s is the state you get when applying move m
       8.      (m',v) = findMax (s, α, β)   // m' is the best max move
       9.      if v > maxValue
       10.        minValue = v
       11.        bestMove = m
       12.     endif
               // If we've exceeded some earlier A's max-value, there's no point searching further in this B-node's children.
       13.     if minValue ≤ α
       14.        return (bestMove, minValue)
       15.     endif
               // Update this node's best value so far.
       16.     if minValue < β
       17.        β = minValue
       18.     endif
       19.  endfor
       20.  return (bestMove, minValue)
       

  Exercise: Use the example in the previous exercise and work out the steps in the α-β algorithm.

• Note:
  • The α-β values change along a path of execution down the tree.
          → The bounds don't hold for the whole tree.

    

  • It can be shown that α-β pruning effectively allows doubling the search depth (given the same amount of time).
  • No tree is actually built (just implied by the search algorithm).
  • The effectiveness of α-β depends heavily on the child node ordering:

    

    
          → Many type-B programs order child nodes according to value.

Exercise: Modify the Minimax code to implement α-β pruning and test it out with tic-tac-toe.

Iterative deepening:

• An idea that's been around since the early days of search.

• How it works:
  • Start with max-depth d=1 and apply full search to this depth.
  • Make d=2, and search.
  • Increment d, repeat.

• Let's take this a step further by writing it in pseudocode:

  
       Algorithm: Iterative-Deepening (search, maxTime)
       Input: a search algorithm, and a time limit.
       1.   d = 1
       2.   while currentTime < maxTime
       3.      m = search (d)              // Apply search algorithm, e.g., α-β, to depth d
       4.      d = d + 1
       5.   endwhile
       6.   return m                       // Best move found so far
       

• Wait a minute - why waste time doing the first few iterations?
  • One has limited time in games
          → This way, one has a "best" move at some depth d.
  • More importantly, one can re-order the root's children based on previous depth
          → Makes α-β more effective.

    
         Algorithm: Iterative-Deepening (search, maxTime)
         Input: a search algorithm, and a time limit.
         1.   d = 1
         2.   while currentTime < maxTime
         3.      m = α-β-search (d)              // Apply search algorithm, e.g., α-β, to depth d
         4.      re-order children of root.
         5.      d = d + 1
         6.   endwhile
         7.   return m                           // Best move found so far
         

  • Also, with each iteration, the transpostion table adds positions
          → These won't be searched.

The chess tree:

• Average of 35 possible moves per position (average branching factor).

• For a 50-move (100-ply) game
        → 35¹⁰⁰ nodes (approx. 10¹⁵⁴) in tree.

• Note: an endgame might have as few as 4-6 pieces
        → These game trees can be explored off-line (and have been).

Back to Shannon:

• Shannon realized that a full exploration is not possible.
  • Instead of going down to a leaf-level, stop at some depth.
  • Use a scoring function to evaluate positions at max-depth.

• Two types of search:
  • Type-A: fix a depth and do a complete search of tree until that depth.
  • Type-B: explore some promising moves more deeply than others.

• Shannon's scoring function:
  • Material points: Q=9, R=5, B=K=3, P=1, K=200.
  • Pawn structure: penalty of 0.5 for each doubled or isolated pawn.
  • Piece-mobility: 0.1 points per possible move per piece.
  He also recommended other scoring attributes.

• Note: score granularity = 0.1.

• For comparison: Deep Blue's scoring function
  • Much smaller granularity.
  • 8000 different contributing factors.

• Searching:
  • Shannon used minimax (depth-first) search.
  • Because recursion was not supported then, an elaborate data structure was used to track the state and the current position in the (implied) tree.

• Shannon never got around to implementing his (seminal) ideas.

The first decade: Kotok and Kaissa