KCheckers isn’t very good at all, but Cake is no cake walk….

Milhouse utterly destroys kcheckers. This game is typical of the five I just played against it.

[Event "KCheckers Game"]
[Date "2009.04.29"]
[Round "1"]
[Black "*Master*"]
[White "Milhouse"]
[Result "0-1"]
[GameType "21"]
1. 12-16 22-18 2. 8-12 24-19 3. 10-15 19x10 4. 7x14 25-22 
5. 9-13 18x9 6. 5x14 23-19 7. 16x23 27x9 8. 12-16 26-23 
9. 6-10 22-18 10. 11-15 18x11 11. 16-20 9-5 12. 1-6 5-1 
13. 3-7 23-18 14. 7x16 18-14 15. 10x17 1x10 16. 17-22 31-27 
17. 16-19 27-24 18. 20x27 32x16 19. 22-26 30x23 
20. 4-8 28-24 21. 13-17 21x14 22. 8-11 16x7 23. 2x11 10-7 
24. 11-16 24-20 25. 16-19 23x16 0-1

On the other hand, I got Martin Fierz’s Checkerboard program running under wine on my Macbook, and it’s “Cake” engine made pretty short work of my program.

[Event "Sparring"]
[Date "2009-04-29"]
[Black "Milhouse"]
[White "Cake"]
[Result "0-1"]
1. 11-15 24-19 2. 15x24 28x19 3. 8-11 22-18 4. 10-14 27-24 5. 7-10 24-20 6. 3-8 19-16 7. 
12x19 23x7 8. 2x11 26-23 9. 10-15 25-22 10. 8-12 31-27 11. 6-10 30-25 12. 1-6 22-17 13. 
15x22 25x18 14. 11-15 18x11 15. 9-13 11-7 16. 13x22 7-2 17. 5-9 2-7 18. 4-8 21-17 19. 14x21 
7x5 20. 21-25 5-1 21. 6-9 1-6 22. 9-13 6-10 23. 25-30 23-19 24. 8-11 27-24 25. 22-26 32-28 
26. 11-15 10-14 27. 13-17 19x10 28. 17-22 20-16 29. 12x19 24x15 30. 26-31 14-18 31. 22-26 
18-23 32. 30-25 23x21 0-1

PBH-10 to launch soon..

Project Blue Horizons is a group which is attempting an unmanned Trans-Atlantic balloon flight from the United States to Europe. They are estimating a launch around 0:00-3:00 UTC on the 30th of April and they are supposed to be sending telemetry on 40m. You can follow their updates on twitter.

This will be PBH-10, you can also see the flight of their previous attempt, PBH-9 on this Google Map PBH-9 set a duration record, spending over 49 hours aloft.

At last, some QRSS news…

A while go, I posted a link to AA5CK’s website and his use of the iduino as a QRSS keyer. He used a little oscillator/buffer from Nightfire Engineering along with a home brew, single transistor amplifier.

So, I ordered two. And built one. At $7, who could resist?

It works, but it obviously isn’t very pure. I’ll get some a snaphot of the oscilloscope output sometime, but it is obviously flat on the bottom of the cycle, with a rather sharp and triangle peak. The tone sounds very
harsh in a receiver. It very obviously needs some kind of output filter. It does appear to be very close on frequency, maybe only 5 hertz low. The peak-to-peak voltage swing into a 50 ohm load was very nearly 2 volts, meaning that the output power is somewhere around 14mw with the 9 volt battery I was using as a supply.

Overall, my “ugly construction” 40m oscillator with buffer that I cribbed from EMRFD seems much cleaner. I suspect that in part this is because the vakits.com oscillator doesn’t have a tuned buffer amplifier, but that’s just my intuition.

I’d like to boost the output power to around 100mw (or maybe even a bit more) (perhaps with a class C amp) and obviously add an output filter, and then get it on the air.

Milhouse needs an opening book…

I decided to play a game against Chinook set on its intermediate level. It was lost before it even began. Fortman’s Basic Checkers lists 3. 16-19 … as the only viable move for Black, and the convincing way that Chinook took me apart is a pretty good ilustration that even with an 18 ply search, Milhouse was unable to extricate itself from that move. I think I need an opening book.

[Event "Sparring Match"]
[Date "2009-04-27"]
[Black "Milhouse"]
[White "Chinook (Intermediate)"]
[Site "Internet"]
[Result "0-1"]
1. 10-14 22-18 2. 12-16 24-20 3. 7-10 28-24
4. 8-12 24-19 5. 3-7 25-22 6. 9-13 18x9
7. 5x14 22-17 8. 13x22 26x17 9. 1-5 29-25
10. 14-18 23x14 11. 16x23 27x18 12. 10-15 25-22
13. 15-19 17-13 14. 11-15 18x11 15. 7x16 20x11
16. 6-9 13x6 17. 2x25 21-17 18. 25-29 17-14
19. 12-16 11-7 20. 16-20 7-3 21. 19-23 3-7
22. 20-24 7-10 23. 5-9 14x5 24. 4-8 10-15
25. 23-27 32x23 26. 24-28 15-11 0-1
After 3. 7-10... White to move and win...
After 3. 7-10... White to move and win...

Addendum: With a 20 ply search, you can see that Milhouse thinks that 6-10, 7-10, and 8-12 are all more viable. Broken.

            -9 :  6-10 25-22  8-12 28-24 10-15 22-17 15x22 17x10  7x14 26x10  2-7  10-6   1x10 23-18
            -9 :  7-10 27-24  8-12 24-19 10-15 19x10  6x22 25x18  3-7  28-24  7-10 30-25  4-8  24-19
            -9 :  8-12 28-24  7-10 24-19 10-15 19x10  6x22 25x18  3-7  27-24  7-10 30-25  4-8  24-19
          -109 :  9-13 18x9   5x14 23-18 14x23 26x12  7-10 27-23  6-9  25-22  2-6  30-25 10-15 21-17
          -111 : 11-15 18x11  8x15 20x11  7x16 23-18 15x22 25x18 14x23 26x12  2-7  27-23  6-10 23-18
          -116 : 14-17 21x14 11-15 18x11  8x15 20x11  7x16 23-19  9x18 19x10  6x15 26-23  2-6  23x14
           -97 : 16-19 23x16 14x23 26x19  6-10 25-22 11-15

Well, not really broken. Playing 3. 16-19 requires Black to play a man down for the duration of any reasonable search horizon. Mihouse will have difficulty playing into man down openings because of its relatively weak evaluation function. It will absolutely require an opening book to survive openings like this one.

Addendum: Things to do: try to see if Milhouse does better if the roles were reversed in this position. I also have been pondering coding up some form of opening book generator based upon Lincke’s “drop out expansion” idea. It’s actually pretty straightforward, and I could leverage a couple of multicore desktop machines to probably create a basic opening book in a month or two of runtime. Or, I could just try to make use of Martin Fierz’s book in Cake. But that would be cheating. Sort of. 🙂

Milhouse defeats Chinook (on amateur level anyway)

Oddly Chinook seemed to know the end was coming before Milhouse recognized it. But sure enough, Milhouse managed to navigate itself to a victory.

[Event "Sparring Match"]
[Date "2009-04-27"]
[Black "Milhouse"]
[White "Chinook (Amateur)"]
[Site "Internet"]
[Result "1-0"]
1. 12-16 22-17 2. 16-19 24x15 3. 11x18 23x14
4. 9x18 28-24 5. 8-11 26-23 6. 6-9 23x14
7. 9x18 24-19 8. 2-6 17-14 9. 10x17 21x14
10. 4-8 31-26 11. 11-15 19x10 12. 6x15 25-21 
13. 8-11 29-25 14. 1-6 26-22 15. 6-9 21-17
16. 9-13 27-23 17. 18x27 32x23 18. 15-19 23x16
19. 11x20 30-26 20. 20-24 25-21 21. 7-10 14x7
22. 3x10 26-23 23. 24-27 23-19 24. 27-31 19-16
25. 31-26 16-11 26. 10-15 11-8 27. 26-23 8-3
28. 23-18 3-8 29. 18x25 17-14 30. 25-22 14-10
31. 22-18 8-11 32. 15-19 10-7 33. 13-17 21x14
34. 18x9 11-15 35. 19-23 7-2 36. 23-26 15-10
1-0

Sparring Milhouse versus Chinook

Well, I’ve mucked around a bit, and begun to add PDN (Portable Draughts Notation) logging to Milhouse. Here is a sparring match between the novice version of Chinook that you can play online versus Milhouse, running at around 15 ply search with a six piece endgame database. It seemed clear that the position was a draw at the end. Chinook seemed to think I had it on the ropes around move 19. Did milhouse miss a strong line, or is the novice level of Chinook misguided? I’m not sure.

[Event "Sparring Match"]
[Date "2009-04-27"]
[Black "Milhouse"]
[White "Chinook (Novice)"]
[Site "Internet"]
[Result "1/2-1/2"]
1. 11-15 22-18 2. 15x22 25x18 3. 8-11 29-25 4. 4-8 24-20 5. 12-16 26-22
6. 8-12 28-24 7. 9-13 30-26 8. 10-15 24-19 9. 15x24 18-15
10. 11x18 20x11 11. 7x16 27x11 12. 18x27 31x24 13. 12-16 32-27 14. 6-10 24-20
15. 10-15 11-8 16. 3x12 20x11 17. 12-16 11-8 18. 15-19 21-17
19. 16-20 27-23 20. 19-24 23-19 21. 24-27 19-16 22. 27-32 17-14
23. 20-24 8-4 24. 24-27 25-21 25. 1-6 16-11 26. 13-17 22x13
27. 6-9 13x6 28. 2x18 26-23 29. 18-22 21-17 30. 22-25 17-14
31. 27-31 23-19 32. 31-26 19-16 33. 25-29 14-10 1/2-1/2

Goofing around with Unicode…

I’m kind of old school. I tend to write a lot of programs with character, line oriented interfaces. Part of it is sort of an organized laziness: I’d rather spend my time working on “the real” part of the program. But sometimes, you realize that your program could be enhanced by a little nicer look. Recently, I’ve become interested in the potential of using Unicode to augment the kind of symbols that we can use in program output. I recently discovered that there are Unicode glyphs for checkers in the map. While they aren’t as nice as the postscript generated graphics that I’ve done before, they are nicer than just using R and W like in my conventional program. To test out what could be done, I made a little Python program that output the starting board. Witness:

picture-1

This is rendered with the GNU unifont, which don’t exactly have glamorous glyphs, but they are quite legible. I might actually add this to my checkers program.

Addendum: I wrote the above in Python, which has a lot of nifty support for Unicode strings. I thought it would be relatively simple to figure out how to do this in C, but as it turns out, it’s not as easy as I thought. Also, the checkers characters are double width, and editors like vim don’t seem to really like double wide characters that much. Harumph. I’ll figure out how to do this some other time.

Milhouse beginning to show signs of promise…

Well, I got move ordering implemented, and the performance on my two previous test cases seem much more comparable. And with this addition, milhouse is able to solve some fairly subtle problems, not just the toy one’s from Pike’s book of Checkers puzzles. For instance, consider this position:

board4

Red is to move and draw. Only one move leads to a draw.

Give up? Me too. I wrote a checkers program so I wouldn’t have to think. 🙂 I made some changes so it could do some rudimentary analysis of positions. Here’s the output:

         -7602 :  1-6  10x1  18-15  1-6  15-11  5-1  11-8   1-5   8-12  5-9   4-8   9-14  8-11  6-2 
         -7421 :  4-8  20-16  8-12 16-11 18-22 10-14 22-25 14-9  25-21  9-14 21-25 14-9  25-21  9-14
         -7600 : 18-14 10x17  1-6   5-1   6-10  1-5  10-15  5-1   4-8   1-5   8-11  5-9  15-18 20-24
         -7600 : 18-15 10x19  1-6   5-1   6-9   1-5   9-13  5-1  13-17 20-16 17-21  1-5  21-25  5-1 
         -7421 : 18-22 10-14  4-8  20-16  8-12 16-11 22-25 14-9  25-21  9-14 21-25 14-9  25-21  9-14
            +0 : 18-23 10-7  23-18  7-2  18-14  2-7  14-9   7-2   9-14  2-7  14-9   7-2   9-14  2-7 

Yep, 18-23 leads to a draw (by repetition). All others, doomed.

Milhouse still hides some mysteries…

So, I was doing some more testing this morning, and noticed an anomaly in my checkers program, Milhouse. Consider the following position:

LOADED puzzle 177: Testing move ordering..
Color is set to red.
           White
        +--------+
        | R - - R|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - W |
        +--------+
           Red

This has a 33 ply solution, which milhouse finds pretty easily, yielding the following statistics:

final score = 10000
transposition tables
... 1049502 gets (1015774 tier0 / 0 tier1 / 33728 failed)
... 757147 puts (33728 tier0 / 723419 tier1) (298250 L/365516 X/93381 U)
... 349949 chinook database accesses.
        1. 29-25
1.173 seconds elapsed.

Not bad. The caching works reasonably well, and I only need to access about 349K positions from the Chinook endgame database (which is basically the entire thing a couple of times over, which isn’t good, but not fatal). But let’s try the same position, but with the board rotated 180 degrees:

LOADED puzzle 178: Testing move ordering..
Color is set to red.
           White
        +--------+
        | W - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |R - - R |
        +--------+
           Red

Much to my chagrin, this took a lot longer, but also found a shorter solution (29 ply). Grumble!

... 78459032 gets (78280388 tier0 / 14207 tier1 / 164437 failed)
... 65025084 puts (164623 tier0 / 64860461 tier1) (19696902 L/36414475 X/8913707 U)
... 34724781 chinook database accesses.
        1. 1-5
55.834 seconds elapsed.

I’m guessing that move ordering plays a huge role in this (I haven’t implemented even the most rudimentary version). My move generator basically generates moves in a fixed order, which means that the entire search tree is searched in a consistent order. It’s not surprising particularly that this order doesn’t cause optimal pruning of the search tree. My guess is that implementing some form of move ordering is a good idea. I suspect I can do it by just searching the “best move” previously recorded in the hash table before all others. That should be pretty straightforward to implement.

I’m still a little concerned about the discrepency in the depth of searches.

I’ll ponder that some more later.

Some advances on Milhouse…

I finally got around to totally ripping out the old implementation of transposition tables, and installing a new one based upon hints I read about on various web pages, mostly originating with some of the ideas for cache management that Ken Thompson implemented for his chess program Belle. The idea is to implement two caches, one of which is used to store board positions near the root of the tree, the other which contains all other nodes. The idea is that if you cache near the leaves, then you are likely to need the same values again soon, but if you cache higher up in the tree, you are more likely to save yourself long searches.

Using this, I managed to get my “two king vs. one king” endgames working, searching out 33 ply in just a few seconds.

LOADED puzzle 173: Simple Tests (harder)..
Color is set to red.
           White  
        +--------+
        | R - - R|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - W |
        +--------+
           Red    

milhouse: depth 40
search depth is now 40
milhouse: playout
     1. 29-25 {10000}   1-5 {-10000}
     2. 25-21 {10000}   5-1 {-10000}
     3. 21-17 {10000}   1-5 {-10000}
     4. 17-13 {10000}   5-1 {-10000}
     5. 32-27 {10000}   1-5 {-10000}
     6. 27-23 {10000}   5-1 {-10000}
     7. 23-18 {10000}   1-5 {-10000}
     8. 18-14 {10000}   5-1 {-10000}
     9.  13-9 {10000}   1-5 {-10000}
    10.   9-6 {10000}   5-1 {-10000}
           White  
        +--------+
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - R -|
        |- - - W |
        +--------+
           Red    

milhouse: playout
     1. 14-10 {10000}   1-5 {-10000}
     2.   6-1 {10000}   5-9 {-10000}
     3.   1-5 {10000}  9-13 {-10000}
     4. 10-15 {10000} 13-17 {-10000}
     5. 15-18 {10000} 17-13 {-10000}
     6. 18-22 {10000}  13-9 {-10000}
     7.  5x14 {10000}
           White  
        +--------+
        | - - - -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - - -|
        |- - - - |
        +--------+
           Red    

milhouse: 

I then tried to play a game against the novice level of Chinook. I ended up in this position, with Chinook playing white and Milhouse black. Chinook kept bragging that I was in “serious trouble”, but the reality is that the position is drawn, and once in a six piece drawn end game, Milhouse won’t stumble (barring bugs) so I called this a draw.

board3

Car bomb! Twice!

There, did I get your attention?

So yesterday was a really warm day, the first of the new year really. According to weather.com, temperatures in Emeryville reached a high of 89 degrees. Pretty darned nice. In fact, actually hot.

After work, I hopped into my car (around 6:30PM, well past the heat of the day) and decided to grab my hands free headset and give a call to my buddy Jeff. As I was pulling out of the parking lot, I heard a rather loud POP and found myself covered in lemon lime soda. Witness:

explode1

This guy had been sitting in my back seat for a couple of months, but apparently the temperature combined with the mechanics of jostling around was too much for it. I amusedly told Jeff about the explosion (it wasn’t a lot of soda, since it was one of those ridiculous half cans) and we proceeded to chat.

Of course, he was busy grilling himself some burgers and eventually had to sit down and have his dinner. I jokingly told him that if he hung up on me, he’d never know what was next to explode in my car.

And of course, a few minutes after hanging up:

explode2

I’ve now gone through my car to make sure all soda cans have been removed.

Alpha-Beta Search is Hard To Debug

So, I’ve spent a few hours over the last couple weeks to try to debug milhouse, my computer checkers program that I tinkered together over the last few years. It’s kind of maddening, because in so many ways it seems to work, but it has a number of rather maddening behaviors which can only be classified as bugs. Here’s an example. Consider this simple 2 K vs. 1K endgame (entirely typical, and the kind of endgame that I can even do).

board1

It’s easy, right? Sure enough, Milhouse finds the 14 move sequence that basically forces the White king to flee the double corner, where disaster awaits. The search is very quick, taking just a fraction of a second.

But here’s the thing: nominally more difficult puzzles seem to confuse milhouse entirely. Let’s modify the puzzle to make the winning sequence just a bit longer.

board2

Obviously, this is just 8 half moves (or plies) away from the previous one. (You can see that if White does anything but jigger back and forth, he does nothing but hasten his own demise.) But for some odd reason, a 25 ply search doesn’t discover this winning line.

So, here’s the thing: alpha-beta search is a lot like binary search. To write a bug free binary search is remarkably challenging. Try it sometime. There are all sorts of odd edge conditions you can get wrong if you aren’t careful. Jon Bentley uses it as the prototypical example of how to develop and debug software in his classic work Programming Pearls. And alpha-beta search is 10x worse, for a number of reasons:

  1. The algorithm has the same sort of hidden subtlety that binary search does. There are many edge conditions (is the invariant that alpha < beta? alpha <= beta? do cutoffs occur when score is > alpha? or >= alpha?) that aren’t consistently described in the classic literature on algorithms.
  2. It operates on (typically) very large search trees. It’s hard to find bugs by examining the search tree because of its raw size, and because many minor problems (such as the comparison issues above) are effectively hidden because they often don’t affect the outcome of searches.
  3. There is lots of information about alpha beta search on the web, but almost all available sources suffer from poorly described invariants, and often don’t implement the necessary complications (such as transposition tables) which further complicate the design.
  4. If you do find code that does work and is non-trivial, you can’t understand it. Game programmers love to “optimize” code, which means that all useful patterns and structure have been abstracted out of the program, using only a helpless hodge podge.

Okay, I’m just bitching. I’ve got 99% of this code right, but the 1% is causing me grief.

Addendum: Oh, and here’s another interesting thing. You might remember from a previous blog posting that I counted the number of possible checkers positions for each number of pieces. If you look at the table, you’ll find that there are about a quarter of a million positions with three pieces or less. My checkers program can compute about twenty five million positions a second, yet I’m not finding the winning search. It’s not too hard to imagine what the problem is. Let’s assume that the branching factor for this problem is roughly eight. If the winning line is 25 ply long, the full search tree is 825 nodes. That’s 3.7E22 positions. Even with alpha-beta searching, that’s a huge number of nodes. This is where transposition tables are supposed to come in. There are many paths that lead toward equivalent positions, so there is no reason to research the same trees over and over again. So, you maintain a table that records the outcomes of previous searches, and if the same position shows up, you already know the answer and don’t have to search.

Obviously, mine isn’t working too well. If it were, I’d expect to quickly expand the search perimeter to find nodes I hadn’t seen before, and locate the winning line.