6.034 Artificial Intelligence - Recitations, fall 2004 online slides on games

Next: Alpha Beta Properties Previous: Example

Bad and Good Cases For Alpha-Beta Pruning

Bad: Worst moves from min perspective encountered first (worst moves ordered on the left)

                                  4                              MAX
                 +----------------+----------------+
		 2                3                4             MIN
	    +----+----+      +----+----+      +----+----+
	    6    4    2      7    5    3      8    6    4        MAX
	 +--+  +--+  +--+ +-+-+  +--+ +--+  +--+  +--+ +--+--+
	 6  5  4  3  2  1 1 3 7  4  5 2  3  8  2  1  6 1  2  4

Good: Good moves from min perspective ordered first

                                  4                              MAX
                 +----------------+----------------+
		 4                3                2             MIN
	    +----+----+      +----+----+      +----+----+
	    4    6    8      3    x    x      2    x    x        MAX
	 +--+  +--+  +--+ +--+             +-+-+
	 4  2  6  x  8  x 3  2             4 2 1

If we can order moves, we can get more benefit from alpha-beta pruning.