More on checkers…

I’ve been thinking about improving the evaluation function that milhouse uses, and have been particularly interested in automatic tuning of these functions. The two obvious contenders as far as methods go are the TDLeaf algorithm and some kind of evolutionary approach. So, as I was reading Chellapilla and Fogel’s paper “Evolving an Expert Checkers Playing Program without Using Human Expertise”, and pondered it a bit. In the paper, they list a game which was listed as “Played Against Human Rated 2173”, which yielded the following position at move number nine:

	   White  
	+--------+
	| - w w w|
	|w w - - |
	| w w - w|
	|- w - - |
	| - r r w|
	|r r r - |
	| - r r -|
	|- r r r |
	+--------+
	   Red    

The human “expert” picked 11-16 here. It’s not a very good move. In fact, it loses a checker almost immediately. The response is 24-20, and the computer gets the better of a bunch of forced exchanges.

Later, at turn 17 Red, our human is faced with this position:

	   White  
	+--------+
	| - - - -|
	|- w w w |
	| w w - w|
	|r - - - |
	| - r r -|
	|- w r w |
	| - - - r|
	|- r r - |
	+--------+
	   Red    

and selects 3-7, which is another dog. The human in this case blundered into a pair of pretty obvious exchanges, which can be found with even really relatively shallow searches and even the most modest evaluation functions. In other words, this position doesn’t actually illustrate any deep understanding of the positions involved. I’ve heard some pretty stiff criticism of this before, but this is the first time I actually worked through the position.

Milhouse v. Chinook

Well, this morning as I woke up, I decided to try to play milhouse against Chinook. Deluded by feelings of competency, I felt like it might be able to compete (at least at the novice level settings) against Chinook.

Well, it didn’t go as badly as it might. With 15 ply search, milhouse decisively dispatched Chinook at the novice level! Woohoo! Flush with confidence, I decided to play it at intermediate level, and.. well, milhouse obviously played into a serious mistake. It blissfully saw a nearly even position for a couple of turns, while Chinook was taunting me with “Chinook is winning!”. We ended up in a very oddly cramped position, which it doesn’t surprise me that milhouse can’t play very well, because milhouse doesn’t really have an evaluation function which deals with mobility and cramps at all. Chinook polished me off with a 3 for 2 trade.

I would post the pdn files for the games, but my program doesn’t automatically write them, which is an excellent feature that should be added. I need to do some work to transcribe them. Perhaps early in the week.

Loy’s Checkers Problems

I was looking for some more difficult checkers positions to test my checker program milhouse against. Jim Loy’s excellent page has a list of difficult ones. Unlike the typical puzzles I have in my Encylopedia of Checkers Puzzles by Pike, these aren’t the kind of puzzles you typically find in 10 ply. In particular, his puzzle #2 was marked as “difficult”, and was a “cook” of a position thought to be a draw. Interestingly enough, my checkers program, as feeble as its evaluation function is, seems to find the winning line for Red with a 15 ply search.

Loy’s Checkers Problems

Puzzle Jim Loy, Puzzle #2 loaded.
Color is set to red.
	   White  
	+--------+
	| - w - -|
	|w - - w |
	| w r - w|
	|w w - w |
	| w r - w|
	|r - r - |
	| - r - r|
	|- r r r |
	+--------+
	   Red    

milhouse: depth 15
search depth is now 15
milhouse: annotate
	1-6 : -359
	2-6 : -61
	3-8 : -425
	5-9 : -111
	7-11 : -180
	10-14 : -239
	15-18 : -119
	23-26 : 124
	23-27 : -40
milhouse: playout
     1. 23-26 [  124] 31x22 [ -119]
     2.   2-6 [  182] 16-11 [ -181]
     3.  7x23 [  188] 24-19 [ -187]
     4. 15x24 [  238] 28x19 [ -237]
     5. 10-14 [  239] 17x10 [ -239]
     6.  6x24 [  242] 22-18 [ -241]
     7. 24-27 [  244]  13-9 [ -235]
     8.  5x14 [  261]  18x9 [ -233]
     9. 27-31 [  237] 25-22 [ -202]
    10. 31-26 [  251] 22-18 [ -251]
	   White  
	+--------+
	| - - - -|
	|- - R - |
	| - r - w|
	|w - w - |
	| - - - -|
	|r - - w |
	| - - - -|
	|- r - r |
	+--------+
	   Red    

milhouse: playout
     1. 26-22 [  251] 18-15 [ -249]
     2. 23-27 [  271] 15-11 [ -312]
     3. 22-18 [  313] 21-17 [ -264]
     4. 18-15 [  267]  11-8 [ -267]
     5. 27-31 [  312]   8-4 [ -269]
     6. 15-11 [  335] 17-13 [ -341]
     7. 31-27 [  342]   9-6 [ -342]
     8.  1x10 [  346]  13-9 [ -346]
     9. 12-16 [  346]   9-6 [ -346]
    10. 27-24 [  352]   6-1 [ -352]
	   White  
	+--------+
	| - - - -|
	|- - - - |
	| R - - -|
	|w - - - |
	| r - - -|
	|- R r - |
	| - - - -|
	|W r - W |
	+--------+
	   Red    

milhouse: playout
     1. 16-19 [  352]   1-5 [ -354]
     2. 19-23 [  377]   5-1 [ -375]
     3. 23-26 [  393]   1-5 [ -400]
     4. 26-30 [  401]   5-9 [ -450]
     5. 24-19 [  401]   9-5 [ -451]
     6. 30-25 [  521]   5-1 [ -656]
     7. 10-14 [  656] 20-16 [-9986]
     8. 11x20 [ 9987]   4-8 [-9988]
     9.  3x12 [ 9989]   1-6 [-9990]
    10. 19-15 [ 9991]   6-9 [-9992]
	   White  
	+--------+
	| - - - -|
	|- - - R |
	| - - - -|
	|R - - - |
	| - R r -|
	|r - - W |
	| - - - -|
	|- - - - |
	+--------+
	   Red    

milhouse: playout
     1. 15-10 [ 9993]  9x18 [-9994]
     2. 20-24 [ 9995] 18-23 [-9996]
     3. 24-19 [ 9997] 23x16 [-9998]
     4. 12x19 [ 9999]	   White  
	+--------+
	| - - - -|
	|- - - R |
	| - - - -|
	|- r - - |
	| - - - -|
	|- - R - |
	| - - - -|
	|- - - - |
	+--------+
	   Red    

milhouse: