I spend what I think is a very substantial part of my life thinking. Not the usual kinds of thinking, like what am I having for dinner, how much money is left in my checking account, or whether the people I work with like and respect me. Don’t get me wrong: I do spend time thinking about those things. But I seem to spend a lot more time thinking about some different kinds of things. Like how to write a checkers program that can beat master level players. Like whether podcasting is actually effecting a change in the nature of communication in society. Like whether I could create a PVR that was simple to install and use on my Linux box. Or even whether I can create an Enigma machine simulator on an Atari 2600.

These things are pretty eclectic, but I really can’t imagine my life without these kinds of thoughts. I think the biggest problem would be that without these (admittedly obscure) topics to keep my mind busy, I’d simply be bored. Bored out of my mind. It’s not that any of these things are really important, they are just colorful billboards along the at times boring straight patches of the highway that is human life. I suspect that we owe much of the Web and the open source movement to feelings of boredom.

A more erudite exposition can be found here:
The Long Tail: The Awesome Power of Spare Cycles

I haven’t had any time to work on my checkers program with any degree of concentration. I was trying to work out some of the details in creating an endgame database, and thought that maybe I could prototype an example fairly quickly. The particular endgame I was most interested in was the 3 kings versus 2 king database, which is a bit complicated for beginners like myself to master, but key to understanding the game (amateurs can often not find the winning combinations even when playing with the 3 king side). Anywhoo, if you have only kings, the math of calculating how many positions there are for each combination is pretty straightforward, and I coded up a Python script that computed these numbers in a few minutes:

1 0              32
1 1             992
2 0             496
2 1          14,880
2 2         215,760
3 0           4,960
3 1         143,840
3 2       2,013,760
3 3      18,123,840
4 0          35,960
4 1       1,006,880
4 2      13,592,880
4 3     117,804,960
4 4     736,281,000
5 0         201,376
5 1       5,437,152
5 2      70,682,976
5 3     589,024,800
5 4   3,534,148,800
5 5  16,257,084,480

It seems that generating a 3×2 database with Python would certainly be in the realm of feasibility.

[tags]Checkers,Programming[/tags]

1. I’m on what is scheduled to be my last week of production on Ratatouille. If my blog isn’t fascinating in the degree that you have come to expect, that’s probably one of the reasons. I haven’t had much time for extra-curriculars. I’ve had a blast on Ratatouille, and hope you all enjoy it when it hits theaters on June 29.
2. Congratulations to the Golden State Warriors. They made history by being the first team in NBA history to defeat the #1 seed as a #8 seed. I must admit that I have enjoyed watching their games down the stretch. While I believe basketball to be inferior to baseball in every respect (heh) I find their style of basketball to be more entertaining and more in sync with the fast-breaking style that I liked as a kid.
3. l’m trying to decide whether I should by a new motherboard for my son’s computer, or just avoid the headache and buy him a new computer. It is basically a question that is decided on the “how much is my time and aggravation worth”? This week, I’m leaning towards “quite a bit”.

Have a good weekend all.

My wife has been trying to get me to listen to a song called “Code Monkey” from someone named Jonathan Coulton. I didn’t have any idea who he was, but somehow today I ended up at his website listening to a song called Chiron Beta Prime. It’s a free download from his website, and it cracked me up. Nothing like a Christmas song with robots. Anyway, check out his site, and buy his music.

Addendum: Code Monkey is pretty awesome too. As is this video:

My brother mocked my use of ffmpeg to create flash video as I did a couple of days ago. He sent me this set of command line options for the Swiss Army knife of video encoders: mencoder. I went ahead and encoded the classic civil defense film “Duck and Cover”, and then used the flvtool2 to add indexing.

Here is the result:

Here is a little shell script that shows the options. I used mencoder as installed fresh from a new Fiesty Fawn Ubuntu installation. If you install rubygems, you can then type “sudo gem install flvtool2” to get flvtool2 installed (it is in /var/lib/gems/1.8/bin/flvtool2, which is not in my path, but it’s there), and it seems to work well too.

Anyway, Kevin wanted me to test it, and it seems to work.

I dropped in at work over the weekend (we are in the final death throes of production on Ratatouille, so I’m basically doing 7 days a week for the next couple of weeks) and noticed that the traffic along 80 was pretty bad. I didn’t think too much of it, but apparently the cause was a collapsed overpass very near Pixar. A tanker truck apparently exploded and burned on one of the overpasses, and the deck above it collapsed. It’s quite the mess, and will likely take months to fix. I went over to an adjacent overpass and took this photo. It’s ugly. Really ugly.

My checkers program has developed some annoying quirks (read: bugs) and I haven’t made any good progress in figuring them out, except to assertain that most of them appear to be centered around the use of transposition tables (when I disable the transposition tables, my program is much better behaved). Because I didn’t know what was wrong, the code has been mangled in a way I don’t like. Oh well. Rather than mangle it further, I thought I’d dig up some more reading material. The links o’ gold today are T. A. Marlsand’s older papers, including a review on game-tree pruning that seems to answer many questions. Good stuff.

Oh well. I’ll work on it this weekend.

During my lunchbreak, I ran across this miniscule chess program. Very, very neat.

Micro-Max

Bruce Morleland has some excellent stuff on his Computer Chess page, including some details on transposition tables that seems useful.

Today was a miserable day for my checkers program. I suspected that some of the cases that were causing me some difficulty in the puzzles that I have attempted to date were caused by some problems with my alphabeta search. To resolve this, I coded up some simpler versions and a simple version of minimax. Indeed, I found that these worked reasonably well, but that my transposition table code bolluxed things. I obviously didn’t have the brain cells firing on all cylinders, so here it is, 12:35AM and I’m scanning the web for papers that might help. I found that Zobrist’s original paper on transposition tables was available for download.

Here it is: Tech Report TR88

[tags]Computer Game Programming, Checkers[/tags]

I didn’t realize that the data for The Internet Movie Database (IMDb) was available for download as plain text files. Did you?

Thanks to the Foxmath blog for pointing this out to me.

My checkers playing program milhouse is currently advancing at a good clip. I’ve added iterative deepening and a transposition table, and probably will add a history heuristic for move reordering to improve the search further. I’ve also started typing in a bunch of problems from Pike’s Little Giant Encyclopedia of Checkers Puzzles, and used them as test cases. It’s able to solve lots of them, but also stumbles on a few. I’m not certain that the basic alphabeta framework is completely bugfree (in fact, I’m pretty sure it is not) but it is still somewhat gratifying to find it solve problems like the one below:

EXECUTING PUZZLE From D. Oldbury, WHITE TO MOVE FIRST
        +--------+
        | - - - -|
        |- w r R |
        | - w w -|
        |r w w - |
        | - w w R|
        |r - w - |
        | - r w -|
        |- r - r |
        +--------+

1.      ...     27-24 [10001]
2.      20x27 [-10001]
2.      ...     14-9 [10001]
3.      7x14 [-10001]
3.      ...     15-11 [10001]
4.      1x10 [-10001]
4.      ...     11-7 [10001]
5.      13x6 [-10001]
5.      ...     18x2 [10001]
6.      25x18 [-10001]
6.      ...     23x14 [10001]
7.      10x17 [-10001]
7.      ...     19-16 [10001]
8.      3x10 [-10001]
8.      ...     2-6 [10001]
9.      12x19 [-10002]
9.      ...     6x13 [10003]

        +--------+
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - W|
        |- - - - |
        | - - - -|
        |- - - - |
        +--------+

transposition: 61096470 lookups, 7241926 finds, 
    53839352 stores, 1048576 entries

[tags]Checkers,Programming[/tags]

Lennart has a nice writeup on automatic differentiation in Haskell. I keep trying to come up with a reason to learn more about Haskell, and examples like this (which are difficult or at least less understandable in C or C++) go quite some way in convincing me that I should invest the time to understand how lazy, functional, polymorphic languages like Haskell can change the way I write programs.

[tags]Programming.Haskell, Automatic Differentiation[/tags]

Caught Sam’s cat on the wireless webcam, but mostly this is just a test of the embedded flash player.

Addendum: Here is WP-FLV, the WordPress Plugin you need.

Addendum²: You can create flash video using only open source, free tools. I took the AtomBomb1946.mpeg from archive.org, and then ran:

ffmpeg -i AtomBomb1946.mpeg -s 320x240 atombomb.flv

and then just created the viewer:

Nifty.

Well, I had maxed my vacation time out again, so was forced to take a day off. Oh darn. My son and I decided to take the opportunity for a little daytime baseball. Despite some early fear that it would be cold and windy, it was only a little windy, but a very nice day at the ballpark. The Atheletics were battling the Angels, Haren vs. Lackey. Nice. Haren pitched a sweet 3-0 shutout, and Street got the save.

When I got home, I wasn’t up to figuring out what the problem was with my checkers program, so instead I revamped the program that I wrote that fetched the major league schedules to get more up-to-date info, and include the likely pitchers for
the current day. My idea is that this will run at 3:00AM or so, and save the info off into the /etc/motd file, and I can view it whenever I log in.

A bit of hacking, and this is what today’s lineup would have looked like.

------------------------------------------------------------
                MLB SCHEDULE FOR 04/18/2007                 
------------------------------------------------------------
04/18 10:05 AM  KC @ DET Meche (1-1) vs Bonderman (0-0)
04/18 12:10 PM BAL @ TB  Bedard (3-1) vs Kazmir (1-1)
04/18 12:35 PM LAA @ OAK Lackey (2-2) vs Haren (1-2)
04/18 04:05 PM CLE @ NYY Sowers (0-1) vs Igawa (1-0)
04/18 04:05 PM NYM @ FLA Maine (2-0) vs Willis (3-1)
04/18 04:05 PM PHI @ WSH Eaton (1-1) vs Bergmann (0-1)
04/18 04:07 PM BOS @ TOR Wakefield (2-1) vs Ohka (0-2)
04/18 04:10 PM HOU @ CIN Sampson (2-0) vs Harang (2-0)
04/18 04:35 PM CHC @ ATL Zambrano (1-2) vs Davies (0-0)
04/18 05:05 PM PIT @ MIL Maholm (0-2) vs Vargas (1-0)
04/18 05:11 PM TEX @ CWS Millwood (2-2) vs Buehrle (1-0)
04/18 05:35 PM LAD @ COL Lowe (2-2) vs Lopez (1-0)
04/18 07:05 PM ARI @ SD  Webb (1-1) vs Wells (0-1)
04/18 07:05 PM MIN @ SEA Silva (1-1) vs Hernandez (2-1)
04/18 07:15 PM STL @ SF  Keisler (0-0) vs Morris (2-0)

[tags]Baseball,Programming[/tags]