Hints On Designing INextMoveStrategies


Alpha-Beta Pruning

  1. What is the relationship between alpha-beta pruning and the regular min-max process? Don't re-write code!

  2. What method of an accumulator is used to control the mapping process? Given the difference between a regular min-max process and an alpha-beta process, what is the method in the accumulator where you expect the alpha-beta specific code to reside?

  3. Alpha-beta pruning requires that one be able to access the value of the parent level's accumulator. But who instantiated the the child accumulator?

  4. What technique allows an object to reference the object that instantiated it without using an explicit reference to it? How can you use this to modify the makeOpposite() method?

  5. When instantiating the child accumulator by the parent, what method needs to be overriden? (See the questions above.)

  6. Don't forget to properly initialize your fields! When creating an anonymous inner class based on a class that has a parameterized constructor, use this syntax::

     new MyClass(param1, param2, etc) { ....}

  7. Be sure that you have implemented all those "mystery" no-parameter constructors! Do not duplicate code--to call one constructor from another, simply write "this(....)". This is the same basic idea as using "super" to call the superclass constructor, except that the object is call it's own constructor. Since the no parameter constructor isn't supplied any information with which to initialize the fields, simply supply a reasonable default value(s) to the other constructor when you call it.

  8. The code for alpha-beta pruning can be done is a total of 6-8 lines of code that end in semicolons, where no method has more than one line of code.

  9. To access the outer class instance from an innerclass, use the "[outer class name].this" syntax.

  10. Remember that the accumulator's method is "isNotDone", so watch that you are doing the correct comparison in your conditional.

  11. The conditionals used in the updateBest for MinAcc and MaxAcc must match the conditionals you use in AlphaAcc and BetaAcc! That is, use "<" and">" everywhere, or use ">=" and "<=" everywhere. You will get very funny behavior otherwise, e.g. min-max works but alpha-beta and depth-limited do not. One symptom is that the computer won't block a losing move.


Limited Depth Search

The discussion here will talk about a modified limited depth search which doesn't limit the depth in all cases.

  1. What is the relationship between the limited depth search process and alpha-beta pruning?

  2. Does the limited depth search process depend whether a min or a max accumulation is taking place? What does this imply about whether or not min and max versions of the accumulator is needed?

  3. A very useful design pattern in this situation is the Decorator Design Pattern. Decorators enable you to add functionality to an existing object without disturbing its abstract behavior.

  4. What is the relationship between the depth of a limited depth search accumulator to it's creator? This can be implemented without the use of a depth field! (Think accessor method!)

  5. What does the limited depth process do to the mapping process in a min-max algorithm? What does this imply about which method in the accumulator is the crucial method where we'd expect to see the fundamental issues concerning limited depth?

  6. One of the implicit requirements for the limited depth search implementations is the existence of default behavor defined in the superclass. Consider how this notion impacts the implementation of the method that return the current depth. For instance, if you define the base case behavior for getDepth() in the concrete limited depth accumulator class, the recursive getDepth() process will not work. This is a very subtle, but crucial point--take time to understand it fully.

  7. Be sure to consider what every method needs to do. Think delegation !



Payoff Functions

In a game like Othello, you don't have enough time/cpu horsepower to run even an alpha-beta pruning. You have run some sort of depth-limited approach. But the problem is that at the depth limit, you don't know whether that path is a winning, losing or drawing path. Thus you don't know what value to update the accumulator with. ....Darn.

What we need is to update the accumulator with some sort of intermediate value--something that means "I think this is a pretty good path" or "I think is a pretty lousy path" or some gradation of that. That is, we need to update the accumulator with a value between the winning value and the losing value. Since we are doing a min or max accumulation, these intermediate values will work just fine and the "best" path will still be chosen.

The values we are currently using {-1, 0, +1} were arbitrarily chosen. We are currently using ints, but we could either switch to doubles to express intermediate values between -1.0 and +1.0, or we could simply redefine the winning, draw and losing values to something with a larger spread, say {-100, 0, +100}. Then the intermediate values could still be ints.

The "payoff" function is the function that is used to calculate the intermediate value. The demo uses a random function--you, being the programming sophisticates that you are will probably want something more accurate. To do so, you'll want to analyze the board in some manner. For instance, having more tokens than your opponent is often, but not always, a good thing. Having your tokens in the corners is definitely a good thing though having your opponent's there is definitely a bad thing. Restricting the other player's options in the earlier stages of the game is a very common and effective tactic, a strategy that often results in losing more pieces initially, only to gain far more back later on. Of course, if things don't quite pan out the way you want...well, shall we say there are some potential drawbacks..

The IBoardModel provides several methods that are useful for analyzing the board:


Written by Stephen Wong 12/4/01, updated 11/14/03