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]