If you are one of those people who leaves the ballpark early, all I can say is shame on you. SHAME!

Today was an excellent example of why I don’t leave the ballpark early. After scoring two early against Andy Pettit, the A’s would eventually fall behind 4-2 going into the bottom of the ninth. When in the ninth, you see Mr. Automatic, Mariano Rivera, and he gets Chavez to ground out, and then Bobby flies out to deep right. If there was ever a time that heading to the exits might seem reasonable, this is it.

But instead, it turned into an example of why you stay till the last out.

Walker gets a single, and then goes to second on fielder’s indifference. After a good AB, Kendell fights off some high pitches and draws a walk. Up comes Marco Scutaro, who had 7 walkoff hits in his career. He quickly goes down 0-2.

And then hits one deep to left field, off the left field foul pole. Walk off home run.

That’s why I stay to the last pitch.

MLB – New York Yankees/Oakland Athletics Recap Sunday April 15, 2007 – Yahoo! Sports

[tags]Oakland Athletics,Yankees Suck,Marco Scutaro[/tags]

Today also happens to be the 60th anniversary of Jackie Robinson becoming the first African American MLB baseball player. I can’t decide whether we’ve come a long way, or we have a long way to go. Probably both.

Well, I’ve got my first trivial attempts at alpha-beta search working, and my confidence in the general framework that I had constructed was growing, when I discovered that there are some circumstances where milhouse (which mostly just plays itself at the moment) seems to forget which side it is playing, and moves red checkers when it should be moving white ones. I’m kind of baffled as to the cause. I’ll have to think about it some more. In the mean time, I have begun to consider what work I need to interface milhouse to the world at large: this mostly means understanding how to compile it to play with xchecker, and also to be able to read and produce Portable Draughts Notation files. I haven’t done any work on the former, but the latter is described in the following format description document:

PDN 2.0 Specification

[tags]Checkers,Programming[/tags]

With white to have the first move, my checkers program was able to chart its way to a win for white.

Here’s the log.

It’s almost certainly chocked full of bugs, and is using a hideously childish evaluation function, and has no interface at all, but it’s making progress.

[tags]Checkers,Programming,Alpha Beta Search[/tags]

Sure, it’s from 1910, but it’s a free atlas. Maps are kind of cool. Enjoy.

People’s Handy Atlas of the World

[tags]Public Domain,Project Gutenberg[/tags]

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]