Sadly, one of my favorite authors has joined the choir invisible.

Novelist Kurt Vonnegut dies at 84 – BOOKS – MSNBC.com

I want to stay as close to the edge as I can without going over. Out on the edge you see all kinds of things you can’t see from the center.

Sleep well, Kurt.

Ghoulish Addendum: I just received an email offer from Borders Rewards hocking his books. Holy crap. At least wait until he’s in the ground.

Combinatorial Generation by Frank Luskey. Seems generally useful for a variety of puzzles that I have been pondering lately.

Addendum: I didn’t find this very illuminating when I dig right down in it. The style of the pseudocode is very odd, as is the overall discussion of many of the topics.

I wanted to augment a webpage that I use to keep track of MLB games with team logos. Here they are.

I didn’t have much time to work on my checkers program this weekend. Still, in the back of my head, I was troubled by something: the random game player that I wrote revealed that red was winning somewhere around 55% of the total games. That disturbed me a little: I didn’t expect the assymetry of having the first move would create that strong an effect. I also had done some profiling using gprof, and had discovered that the white capture routines were using significantly less time than the red. I thought this was curious too. Finally, a moment of clarity dawned on me, and I set the program up to force white to move first, and the bias toward red victories continued. Well, that meant that there was something assymetric in the routines that generated moves for each side. The vast majority of this code is written by a Python script, and it seemed unlikely that it would be screwed up. A small amount was generated by hand with some assistance from a script to generate some bitmasks.

The offending routine was the one which tried to find the location of all white checker jumps:

BitBoard
WhiteJumpers(CheckerBoard *b)
{   
    BitBoard U = ~(b->R|b->W) ;
    BitBoard M ;
    
    M  = (b->W & JREV_37) & (b->R < < 3) & (U << 7) ;
    M |= (b->W & JREV_47) & (b->R < < 4) & (U << 7) ;
    M |= (b->W & JREV_49) & (b->R < < 4) & (U << 9) ;
    M |= (b->W & JREV_59) & (b->R < < 5) & (U << 9) ;

    BitBoard WK = b->R & b->K ;
    if (WK) {
        M |= (WK & JFWD_37) & (b->R >> 3) & (U >> 7) ;
        M |= (WK & JFWD_47) & (b->R >> 4) & (U >> 7) ;
        M |= (WK & JFWD_49) & (b->R >> 4) & (U >> 9) ;
        M |= (WK & JFWD_59) & (b->R >> 5) & (U >> 9) ;
    }

    return M ;
}

Can you spot the error? Yep, a copy paste error where I compute WK: it should be b->W and not b->R. Stupid me, but kudos to me for being able to localize it based upon my gut instinct.

[tags]Checkers,Programs[/tags]

My son innocently asked “was Hank Aaron really that good?” while they were flashing stats showing how various active players might have a shot at Aaron’s home run record. I said “yes, he really was”, and then ran a quick database query that produced the following career numbers:

Hank Aaron|116.863636363636
Stan Musial|104.556818181818
Willie Mays|103.397727272727
Ty Cobb|99.7840909090909
Babe Ruth|98.7443181818182
Barry Bonds|98.5909090909091
Pete Rose|98.0454545454546
Carl Yastrzemski|94.4147727272727
Eddie Murray|91.9943181818182
Rafael Palmeiro|91.8409090909091
Frank Robinson|91.5852272727273
Dave Winfield|88.9943181818182
Cal Ripken|88.0909090909091
Tris Speaker|86.9488636363636
Lou Gehrig|86.25
George Brett|85.9772727272727
Mel Ott|85.9261363636364
Jimmie Foxx|84.4772727272727
Ted Williams|83.25
Honus Wagner|82.875

The number associated with each name if the total bases by each player expressed in miles. Aaron had more than twelve miles more career total bases than the next in line. Bonds has no chance of beating that record.

[tags]Baseball, Fun with Databases[/tags]

The usual easy rule to deciding whether a particular book is under copyright (at least in the U.S.) is to examine its publication date: works published before 1923 are in the public domain. But there are many works published before 1964 whose copyright notices were not renewed, and these works are also in the public domain. Normally, to determine if the copyright was renewed, you needed to do a search in the Library of Congress for a copyright renewal, and this normally is only done for a fee.

Stanford has now created a searchable index that can be used to find these renewal records for potentially public domain works:

Copyright Renewal Database

This would seem to be very useful.

[tags]Public Domain[/tags]

In some of my reading up on checkers, I encountered this quotation from Poe’s Murders in the Rue Morgue:

I will, therefore, take occasion to assert that the higher powers of the reflective intellect are more decidedly and more usefully tasked by the unostentatious game of draughts than by a the elaborate frivolity of chess. In this latter, where the pieces have different and bizarre motions, with various and variable values, what is only complex is mistaken (a not unusual error) for what is profound.

Very nice…

Yesterday I managed to get most of the move generator for my own checkers program, tentatively named Milhouse mostly working. I have taken a somewhat odd approach in that I am generating most of the move generator by writing a couple of Python scripts which generate the C code for the move generator. The particular board representation that I have chosen to use is a structure containing only three 32 bit integers. Coincidently, a checkerboard has 64 squares, but the game is played on only 32 of them. This makes for a fairly nice and compact representation: one integer contains a bitmask showing where the red checkers are, another, the white checkers, and a third to indicate which of the pieces are kings. This representation is compact, and fairly useful for move generation as well. Once I got the basics working, I coded up a loop to play one million games, each doing a legal move randomly chosen from the available legal moves.

[ markv@checkers .../milhouse ] % time milhouse
537359 red wins, 462641 white wins, 474661073 nodes 90572579 total moves
22.083u 0.091s 0:22.25 99.6%    0+0k 0+0io 1pf+0w

It played the million games in just 22 seconds, generating over 90 million total moves (really plies, or half moves) and 474 million total board positions. I think it’s a fairly good start.

Addendum: The assymetry in red and white wins seemed a bit extreme. It turns out I had a fairly serious bug caused by a copy paste error.

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

Thomas Lincke invented a technique called “drop-out-expansion” for the automatic construction of opening books. That seemed like a pretty nifty thing: it’s used by Martin Fierze’s Cake program to compute a vast database of opening positions in checkers. I wanted to know what it was about, and my Google Fu revealed this thesis:

Exploring the Computational Limits of Large Exhaustive Search Problems

Neat.

[tags]Checkers[/tags]

Dodgen and Trice talk about their 7 piece perfect play endgame database, which can be used to guarantee wins or stall defeats as long as possible when confronted by positions having 7 or fewer pieces. Most endgame databases contain only the game theoretic value for positions, and therefore might have difficulty actually finding the winning combinations even though they “know” that the position is a win. I was beginning to think about this, so it was interesting to find this paper.

WCC_Database.pdf (application/pdf Object)

I’ve got about half of my bitboard based move generator for checkers working. Once I get it finished, it should only take me an evening or so to get a basic checkers implementation working. The code was about half-machine generated, which made getting it correct much simpler than had I tried to do so by hand.

[tags]Checkers,Endgame Database[/tags]

Truly, this guy has more metachlorians than I do.

BattleBricks: WiigoBot, The Perfect Game

[tags]Wii,Lego[/tags]

Courtesy of The Unapologetic Magician, check out George Bell’s paper Solving Peg Solitaire on arxiv.org.

[tags]Mathematical Recreations,Games[/tags]

Find out a bit more about Google’s new free wireless broadband service!

Frankly, I bet it stinks.

I have thought about dusting off my never-finished (or even really started) checkers program that I aborted work on about three years ago. I basically know very little about checkers, but the rules are a little more straightforward, which makes creation of a checkers program of average quality probably slightly easier than writing a chess program of average quality.

One of the minor details you have to get right is how the notation works (how squares are numbered etc). So, I surfed over to Jim Loy’s page on the subject. It includes the following statement:

Note that even though the game of checkers is played on the dark squares of the board, in checkers diagrams the pieces are on the light squares, to enhance readability. Note also that the official colors for the pieces are red and white. In older publications, they are called black and white. If you have a checker set with black and red pieces, the black pieces are called red, and the red pieces are called white. Sorry, that’s the way it is.

So even though you are supposed to play with the dark square on the players left, his diagrams show light squares on the players left. Even though checkers is played on dark squares, his diagrams show you playing on light squares. All those $.99 checkers sets you get have red and black checkers, but real checkers is played with red and white markers, so if you want to play it with your cheap set, black is red and red is white. Oh, and red moves. I mean black.

Ouch.

[tags]Checkers[/tags]

Addendum: A couple of years ago I was working on a PostScript font for typesetting checkers games. I can’t find the work I did, so I decided to try to dust off those braincells and work on it again. All this blather about colors above made me want them to work in color. This is ugly, but at least shows the basic idea:

Red is seated at the bottom, White at the top. White to move and win.

Addendum²: In many ways, i like the old font that I did better (it has that classic look). I’ll probably try to resurrect it, but I did learn some things about PostScript fonts this time, so it will probably work better.