reset password
Author Message
rabbott
Posts: 1649
Posted 18:28 Apr 27, 2014 |

I finally got a decent depth-limited alpha-beta search working.  There are two files.

  • MyStateMachineGamer.scala. This class is a subclass of StateMachineGamer and has a number of convenience methods. 
     
  • AlphaBeta.scala. This class contains the alpha-beta algorithm with a depth limit. The primary methods are

def bestMove(state: MachineState, alpha0: Score, beta: Score, indent: String = "  "): (Score, Move)

     Finds and returns the best minimax/alpha-beta Move from state. Also returns the minimax/alpha-beta score that Move guarantees. This is the maximizer.

def lowestStateScore(stateList: Buffer[MachineState], alpha: Score, beta0: Score, indent: String = "  "): Score 

     Finds and returns the lowest score that might occur in states in stateList.This is the minimizer.

The overall idea is that given a state, one wants the Move that guarantees the best score. Each Move leads potentially to a number of states depending on what the other players do. So for each Move we want to know the lowest score that can result. Then we pick the Move whose lowest score is highest.

This code got 20/20 on exercises 7.3, 7.4, and 7.5. It doesn't implement the required heuristics. It's the same code for all three exercises.

You are welcome to copy my code, but please don't modify it in place. eclipse and DropBox are not very compatible.  (I now see that if you click the file links above, a copy of the file is loaded into the browser. You apparently don't have access to the original.)

 

Last edited by rabbott at 10:43 Apr 28, 2014.