Are improvements in computer chess due mostly to hardware or software?

file000183685005My recent revival in interest in computer chess/checkers/gameplaying was in part spawned by the impression (not particularly support by evidence at the time) that the dramatic increase in computer chess strength must have come from more than just basic hardware improvements. It seemed obvious to me that some fraction of the increase in the play was due to new cleverness and discoveries by chess programmers. But I had no real datapoints to figure out what that split might have been.

Until I found this 2010 post by Bob Hyatt. Bob has been an expert programmer in computer chess for decades, first for Cray Blitz and later for Crafty, an awesome open source Chess program. It’s source code is amazingly interesting, and has tons of features which are pretty cool.

In the forum post, Bob compared Crafty 23.4 (which was at the time the highest ranked version he had produced) with Crafty 10.18, the version which was available 15 years earlier from 1995. Running on the same hardware, you find that Crafty 23.4 was 360 ELO points higher than older version.

But how much would we expect to gain from the factor of 1000x increase in speed between 1995 and 2006? I remember reading that each doubling of CPU speed would be worth about 100 ELO points. Bob did some experiments that suggests for Crafty, that result might be something more like 80 ELO points. That means that from hardware improvements alone, you might expect to see an increase of 800 ELO points.

This would seem to imply that only 1/3 of the improvement of Crafty was due to software, with the remaining 2/3 of the improvement due to increases in hardware speed. Bob doesn’t believe the 360/800 numbers are accurate (they are likely too broad, 1995 Crafty was probably not 1100 points weaker than 2010 Crafty) but that the ratio of the two is likely to stand up.

Bob did this post to respond to this rather long thread which I find much harder to draw any real conclusions from. But it’s still good reading.

But it would seem that my intuition is likely wrong: that at least for Crafty, about 2/3 of its gains are likely to increases in hardware speed, with only 1/3 coming from software improvements. Interesting.

On Computer Chess, including Stockfish and SmallFish

Off and on I’ve been pondering some changes to my computer checkers program called Milhouse. Most of these changes have relatively little to do with checkers per se, but are just changes to the algorithms that are common to nearly all game-tree search programs. Since computer chess has always been more popular than computer checkers, that means I’m reviewing a lot of chess programs and papers on chess.

Years ago when I started milhouse, the open source chess programs that I knew about were basically gnuchess (which has gone through a bunch of different versions, including some complete changes of the underlying chess engine) and Bob Hyatt’s Crafty. Bob is a veteran of computer chess, having written the famous program Cray Blitz which one several ACM chess events, and two World Computer Chess Championships. Crafty is very cool, and can obviously play chess at a much higher level than I ever aspire to.

But it turns out that in the last few years, chess engines continue to get better. Like a lot better. The top ranked computer programs now have ELO rankings of around 3200. By way of perspective, Gary Kasparov was the first human to break the 2800 barrier in 1989. A 400 point difference between (say) Houdini and Gary Kasparov means that we’d expect Houdini to win 92% of all games between the two. (You can find some some ratings for current chess engines here)
Poor old Crafty, ranked 600 points below at around 2621 (with 2 cpus) would probably struggle to win one game out of 100.

I find this fascinating: it’s clear that modern chess engines are plumbing depths of chess knowledge which have been beyond human understanding, and that the difference between the best human play and what is achievable by “God’s algorithm” is still pretty broad.

Anyway…

During this, I found out a few things.

First, the latest version of GNUchess is based upon the Fruit engine, and that it is probably at least in the same league as Crafty, which it wasn’t before. So, if you were dissatisfied with the old versions of GNUchess, revisiting it might be a good thing to do.

Second, a very competitive engine called Stockfish was available. The multi-cpu versions of Stockfish are very near the top performers on every ranking list I could fine, and probably represent more chess knowledge than you could ever home to find.

Third, and perhaps what is cooler, is that you can get nice IOS versions of chess programs that use Stockfish, with cool interfaces! Download versions for IOS, Android, or get the source code!, and it’s free on the iPad/iPhone. Very, very nice. I particularly like that the app includes the ability to mail the log of completed games, so you can use other programs to analyze your play.

But perhaps you are thinking: “I don’t need the best chess engine in the world, I’m just an average player, and being crushed repeatedly doesn’t help me enjoy the game.” Well, then you can definitely try out SmallFish. SmallFish uses the same powerful insides as Stockfish, but it’s wrapped in a friendly wrapper that allows you to tone it down. In fact, I found it’s default “average” difficulty level to be a bit too easy for me to beat. Here’s the log from a game I played over lunch, where I easily crushed it. I let Crafty provide an annotation to the game, so I could find out how many blunders it made. The answer appears to be about 4x as many as I made, and often quite serious ones. I’ll have to tune it up (probably to ELO 1600 or so) to keep me on my toes.

[Event "?"]
[Site "Pixar Atrium"]
[Date "Jan 13, 2014"]
[Round "1"]
[White "Mark"]
[WhiteElo ""]
[Black "Average"]
[BlackElo "1200"]
[Result "1-0"]
[Annotator "Crafty v23.4"]
{annotating both black and white moves.}
{using a scoring margin of +1.00 pawns.}
{search time limit is 10.00}

  1.      d4     Nf6
  2.     Nf3      d5
  3.      e3     Bf5
  4.     Bd3    Bxd3
  5.    Qxd3     Nc6
  6.     O-O      a6
  7.     Bd2      e6
  8.      c4     Be7
  9.     Nc3     Nb4
 10.     Qe2    dxc4
 11.    Qxc4     Nc6
 12.      a3     O-O
 13.      e4     Qd7
 14.    Rad1    Rfe8
 15.     Bf4     Bf8
 16.     Ne5     Na5
 17.    Nxd7    Nxc4
 18.    Nxf8     Nh5
                ({18:+1.99}  18. ... Nh5 19. Nxe6 fxe6 20. Bc1 Nf6 21. e5 Nd5 22. Nxd5 exd5 23. Rfe1 Re6 24. b3 Na5 25. Rd3 Rf8 26. Bg5 Nc6 27. Rc3 $18)
                ({18:+0.35}  18. ... Kxf8 19. a4 Nh5 20. Bc1 Rad8 21. e5 c5 22. dxc5 Nxe5 23. Ne4 Nd3 24. Nd6 Nxc1 25. Rxc1 Re7 26. Rfd1 Nf4 27. Rd2 $14)
 19.    Nxe6      c5
                ({18:+4.47}  19. ... c5 20. Nc7 Nxf4 21. Nxa8 Rxa8 22. dxc5 Nxb2 23. Rd7 Nc4 24. Rxb7 Nxa3 25. c6 Nc4 26. c7 Rc8 27. Rd1 Ne6 28. Rb8 $18)
                ({18:+2.02}  19. ... fxe6 20. Bc1 Rf8 21. f4 Rad8 22. e5 g6 23. d5 exd5 24. Nxd5 c6 25. Ne3 Rxd1 26. Nxd1 Rd8 27. Ne3 Nd2 28. Rd1 $18)
 20.     Nc7    Nxf4
 21.    Nxa8    Rxa8
 22.    dxc5      h6
 23.     Rd7     Rb8
 24.    Rfd1     Ne5
                ({21:+7.13}  24. ... Ne5 25. Rd8+ Rxd8 26. Rxd8+ Kh7 27. b4 Ne6 28. Rb8 a5 29. Rxb7 h5 30. f3 Nd8 31. Rb5 Nc4 32. c6 Nxc6 33. Rxh5+ Kg6 34. Rc5 N6e5 35. bxa5 f5 36. Nd5 fxe4 37. fxe4 Nxa3 $18)
                ({21:+4.95}  24. ... Ne6 25. Na4 g5 26. R7d5 Kh7 27. g3 g4 28. Rc1 Na5 29. Nb6 Nb3 30. Rc4 Re8 31. Nd7 Kg7 32. Kg2 Rc8 33. Ne5 Na5 34. Rb4 h5 $18)
 25.    Rd8+    Rxd8
 26.   Rxd8+     Kh7
 27.      b4      h5
 28.     Rb8      h4
 29.    Rxb7     Nc6
 30.    Rxf7     Nh5
                ({22:+12.07}  30. ... Nh5 31. Rc7 Nd4 32. c6 Ne6 33. Rf7 h3 34. gxh3 Kh8 35. c7 Nxc7 36. Rxc7 Nf4 37. Rc6 g5 38. Rxa6 Nxh3+ 39. Kg2 Nf4+ 40. Kf3 Nd3 41. Re6 Ne1+ 42. Ke2 Nc2 $18)
                ({22:+9.96}  30. ... Ng6 31. Rc7 Nd4 32. Ra7 Nf4 33. Rxa6 h3 34. gxh3 Nde6 35. Rd6 Nxh3+ 36. Kg2 Nhg5 37. Rb6 Nf4+ 38. Kg3 Nge6 39. Ra6 Kg8 40. Nd5 g5 41. Nxf4 gxf4+ 42. Kf3 Kf7 $18)
 31.      e5
                ({23:+10.21}  31. e5 Kh6 32. Rd7 Kg5 33. Rd6 Ne7 34. c6 Nf4 35. c7 Kf5 36. Rxa6 Ne6 37. Nd5 Nc8 38. Ne3+ Kxe5 39. Ra8 Nd6 40. Re8 g5 41. Ng4+ Kf5 42. c8=Q Nxc8 43. Ne3+ Ke5 44. Rxc8 $18)
                ({24:+12.17}  31. Rc7 Nd4 32. c6 Ne6 33. Rf7 Kg8 34. c7 Nxc7 35. Rxc7 Nf4 36. Rc6 h3 37. gxh3 Kf7 38. Rxa6 g5 39. a4 Nxh3+ 40. Kf1 Nf4 41. b5 Ke7 42. Rc6 Kd7 43. Nd5 Nxd5 44. exd5 $18)

 31.     ...     Kh6
 32.      e6     Nf6
 33.      e7     Kh7
 34.    Rxf6    gxf6
                ({17:Mat09}  34. ... gxf6 35. e8=Q Ne5 36. c6 Nc4 37. Qf7+ Kh6 38. Qxf6+ Kh7 39. c7 Nb6 40. Qxb6 Kg7 41. c8=Q Kf7 42. Qd7+ Kf8 43. Qbd8# $18)
                ({21:+20.29}  34. ... Nxe7 35. Re6 Nf5 36. Ne4 Kg8 37. c6 Kf7 38. Ng5+ Kf8 39. c7 Ne7 40. Nh7+ Kf7 41. Rxe7+ Kxe7 42. c8=Q h3 43. Qf8+ Kd7 44. Qxg7+ Kd6 45. Qh6+ Ke7 46. Qxh3 Kf7 47. Qd7+ Kg6 48. Qd3+ Kg7 $18)
 35.    e8=Q     Ne5
 36.      c6      a5
 37.    bxa5
                ({11:+30.34}  37. bxa5 Nxc6 38. Qxc6 Kg6 39. a6 h3 40. a7 hxg2 41. a8=Q Kf7 42. Qae8+ Kg7 $18)
                ({11:Mat06}  37. c7 Kh6 38. c8=Q Kg5 39. Qg8+ Kh6 40. Qf5 Nf3+ 41. gxf3 axb4 42. Qh8# $18)

 37.     ...    Nxc6
 38.    Qxc6     Kh6
 39.   Qxf6+     Kh7
 40.     Ne4      h3
 41.    gxh3
                ({5:+23.89}  41. gxh3 Kg8 42. Qd8+ Kh7 43. Nf6+ Kg6 44. Ng8 $18)
                ({5:Mat03}  41. Ng5+ Kg8 42. Qf7+ Kh8 43. Qf8# $18)

 41.     ...     Kg8
 42.     Nd6     Kh7
 43.     Nf5     Kg8
 44.    Qg7#
       1-0 

Both programs are free and highly recommended.

My first crude DCPU-16 simulator…

A few days ago, I mentioned that @notch, the creator of Minecraft, had a new idea for a space game that he was beginning to work on. One of the features of this game is that your spaceship would be controlled by a simulated computer that you could program. He released a preliminary specification for the 16 bit machine called DCPU-16. I like writing things like this, so I spent a couple of hours and hacked the simple core of one together. It doesn’t yet properly count cycles, but it does implement the basic instruction set, and executes the sample program that he provided in the notes. As yet, he hasn’t specified how things like I/O will work (I suspect some of the type 0 reserved opcodes will be used), so it’s not of much use, but it might serve as the basis for others to explores.

Addendum: The example program implements a simple loop with the target :loop, but I suspect the bottom of the loop should be an IFE rather than an IFN instruction, otherwise, the loop simple exits on the first iteration.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

/*
 * An implementation of Notch's DCPU-16 specification, version 1.1
 * Written by Mark VandeWettering.
 */

/* this has to be 16 bits, because we aren't going to mask increments
 * and decrements.
 */
typedef unsigned short Word ;
#define MEMSIZE (65536)
Word M[MEMSIZE] ;
Word R[8] = {0, 0, 0, 0, 0, 0, 0, 0} ;
Word PC = 0 ;
Word SP = 0 ;
Word O = 0 ;
Word W = 0 ;
unsigned long cycles = 0L ;

#define OP(w)                   ((w)&(0xF))
#define FIELDA(w)               (((w)>>4)&(0x3F))
#define FIELDB(w)               (((w)>>10)&(0x3F))

unsigned char *Rn[] = { "A", "B", "C", "X", "Y", "Z", "I", "J"} ;

Word 
DecodeSRC(Word v)
{
    Word EA ;
    if (v < 0x8) {
        return R[v] ;
    } else if (v < 0x10) {
        return M[R[v&0x7]] ;
    } else if (v < 0x18) {
        EA = M[PC++] ;
        EA += R[v&0x7] ;
        return M[EA] ;
    } else if (v < 0x20) {
        switch (v) {
        case 0x18:
            return M[SP++] ;
        case 0x19:
            return M[SP] ;
        case 0x1a:
            return M[--SP] ;
        case 0x1b:
            return SP ;
        case 0x1c:
            return PC ;
        case 0x1d:
            return 0 ;
        case 0x1e:
            return M[M[PC++]] ;
        case 0x1f:
            return M[PC++] ;
        default:
            abort() ;
        }
    } else if (v < 0x40) {
        return v - 0x20 ;
    } 
    abort() ;
}

Word *
DecodeDST(Word v)
{
    Word EA ;
    Word *T ;
    if (v < 0x8) {
        return R+v ;
    } else if (v < 0x10) {
        return M+(v&0x7) ;
    } else if (v < 0x18) {
        EA = M[PC++] ;
        EA += R[v&0x7] ;
        return M + EA ;
    } else if (v < 0x1f) {
        switch (v) {
        case 0x18:
            return M+(SP++) ;
        case 0x19:
            return M+SP ;
        case 0x1a:
            return M+(--SP) ;
        case 0x1b:
            return &SP ;
        case 0x1c:
            return &PC ;
        case 0x1d:
            return &W ;
        case 0x1e:
            return M+PC++ ;
        case 0x1f:
            return &W ;
        default:
            abort() ;
        }
    } else if (v < 0x40) {
        return &W ;
    } 
    abort() ;
}

int
SkipArg(Word arg)
{
    if (arg >= 0x10 && arg < 0x18)
        return 1 ;
    if (arg == 0x1e)
        return 1 ;
    if (arg == 0x1f)
        return 1 ;
    return 0 ;
}

void
Skip() 
{
    Word I = M[PC++] ;
    Word A = FIELDA(I) ;
    Word B = FIELDB(I) ;
    PC += SkipArg(A) ;
    PC += SkipArg(B) ;
}

#define DEBUGPRINTF(x)          

void
execute()
{
    Word I ;
    Word T ;
    Word B ;
    Word * A ;
    uint32_t a, b ;

    I = M[PC] ;
    PC ++ ;

    if (OP(I) != 0)
        A = DecodeDST((I>>4)&0x3f) ;
    B = DecodeSRC((I>>10)&0x3f) ;
 
    switch (OP(I)) {
    case 0x0:
        switch (((I)>>4)&0x3F) {
        case 0x01:
            /* JSR */
            DEBUGPRINTF("... JSR") ;
            /* Push the PC on the stack */
            M[--SP] = PC ;
            PC = B ;
            break ;
        default:
            abort() ;
        }
        break ;
    case 0x1:   
        /* SET */
        DEBUGPRINTF("... SET\n") ;
        *A = B ;
        break ;
    case 0x2:   
        /* ADD */
        DEBUGPRINTF("... ADD\n") ;
        a = *A ;
        b = B ;
        *A = (a + b) ;
        O = (a + b) >> 16 ;
        break ;
    case 0x3:
        /* SUB */
        DEBUGPRINTF("... SUB\n") ;
        a = *A ;
        b = B ;
        *A = (a - b) ;
        O = (a - b) >> 16 ;
        break ;
    case 0x4:
        /* MUL */
        DEBUGPRINTF("... MUL\n") ;
        a = *A ;
        b = B ;
        *A = (a * b) ;
        O = ((a * b)>>16) ;
        break ;
    case 0x5:
        /* DIV */
        DEBUGPRINTF("... DIV\n") ;
        a = *A ;
        b = B ;
        if (b == 0) {
            *A = O = 0 ;
        } else {
            *A = a / b ;
            O = ((a<<16)/b) ;
        } 
        break ;
    case 0x6:
        /* MOD */
        DEBUGPRINTF("... MOD\n") ;
        a = *A ;
        b = B ;
        if (b == 0)
            *A = 0 ;
        else
            *A = a % b ;
        break ;
    case 0x7:
        /* SHL */
        DEBUGPRINTF("... SHL\n") ;
        a = *A ;
        b = B ;
        *A = a << b ;
        O = (a << b) >> 16 ;
        break ;
    case 0x8:
        /* SHR */
        DEBUGPRINTF("... SHR\n") ;
        a = *A ;
        b = B ;
        *A = a >> b ;
        O = (a << 16) >> b ;
    case 0x9:
        /* AND */
        DEBUGPRINTF("... AND\n") ;
        *A &= B ;
        break ;
    case 0xa:
        /* BOR */
        DEBUGPRINTF("... BOR\n") ;
        *A |= B ;
        break ;
    case 0xb:
        /* XOR */
        DEBUGPRINTF("... XOR\n") ;
        *A ^= B ;
        break ;
    case 0xc:
        /* IFE */
        DEBUGPRINTF("... IFE\n") ;
        if (*A == B) Skip() ;
        break ;
    case 0xd:
        /* IFN */
        DEBUGPRINTF("... IFN\n") ;
        if (*A != B) Skip() ;
        break ;
    case 0xe:
        /* IFG */
        DEBUGPRINTF("... IFG\n") ;
        if (*A > B) Skip() ;
        break ;
    case 0xf:
        /* IFB */
        DEBUGPRINTF("... IFB\n") ;
        if ((*A & B) != 0) Skip() ;
        break ;
    }
    DEBUGPRINTF("\n") ;
}

Word prog0[] = {
    /* 0000 */ 0x7c01, 0x0030, 0x7de1, 0x1000, 0x0020, 0x7803, 0x1000, 0xc00d,
    /* 0008 */ 0x7dc1, 0x001a, 0xa861, 0x7c01, 0x2000, 0x2161, 0x2000, 0x8463,
    /* 0010 */ 0x806d, 0x7dc1, 0x000d, 0x9031, 0x7c10, 0x0018, 0x7dc1, 0x001a,
    /* 0018 */ 0x9037, 0x61c1, 0x7dc1, 0x001a, 0x0000, 0x0000, 0x0000, 0x0000,
} ;
        
void
dumpregs()
{
    int i ;
    printf("... PC=0x%04X SP=0x%04X ", PC, SP) ;
    for (i=0; i<8; i++)
        printf("%s=0x%04X ", Rn[i], R[i]) ;
    printf("O=0x%04X\n", O) ;
}
        

main()
{
    printf("... DCPU-16 simulator.\n") ;
    printf("... version 1.0, written by Mark VandeWettering\n") ;
    printf("... loading %d words of program ...", sizeof(prog0)/sizeof(prog0[0])) ;

    int i ;
    for (i=0; i<sizeof(prog0)/sizeof(prog0[0]); i++) {
        M[i] = prog0[i] ;
    }
    printf("done.\n\n") ;

    for (i=0; i<20; i++) {
        execute() ;
    }
}

Why I am not going to play Skyrim any more…

Okay, a diversion from my regular topics.

And that’s what computer games are for me: a diversion. I play them because I like to be diverted from my work and from even my normal bits of hackery and play. I tend to play games with a strong story component, like the Zelda games on Nintendo, and more recently Mass Effect/Mass Effect 2 on the Xbox. Because I have a job and a regular life, I really only play about one of these games a year, usually in the span of my Christmas break. This year, my wife got me Elder Scrolls V: Skyrim. And after playing it for more hours than I care to admit, I’ve come to this conclusion.

I hate it, and I’m not going to play it anymore.

It’s not a question of graphics. It’s got some great graphics, with a huge rich world presents an everchanging landscape.

Some people have dinged it for having an unimaginative plot line. I disagree: I think the breadth of the game is pretty incredible, and there is lots of stuff that you can do and follow that I found engaging.

Given my particular requirements, I am actually tempted to complain that the game is too big. It’s got so much to do, it simply demands too much in the way of time to really be completely enjoyable. It’s like seeing a good movie, but having to leave in the middle because you are getting bedsores from just sitting there for so long. But that’s not my real problem with the game.

The real problem is bugs. Bugs. BUGS!

To my way of thinking, there is one sin in game development. It’s not being boring, or repetitive, or derivative. It’s releasing software that contains bugs that affect game play. Bugs like getting wedged in a wall, and being unable to extricate yourself (yep, happened to me in Skyrim). But minor bugs like this are usually not too bad: you simply reload from the last save point and try again. For simple bugs like this, it means that you’ve lost a few minutes of playing (since your last save point). That’s annoying, but I could understand a certain number of them.

But Skyrim goes beyond these simple venial sins, and elevates them to mortal sins. It has bugs which basically prevent the completion of quests, and which you usually discover only well after you somehow encountered the bug. My current save situation has no less than five active bugs of this nature:

  • I can’t complete the Waking Nightmare quest, since Erandur apparently entered the Nightcaller Temple ahead of me, and is inexplicably not there.
  • I can’t get any companions to join me, because the game apparently thinks I have a follower. Yes, I’ve tried waiting for him to catch up. No dice. Scanned back to find where it glitched. Apparently somewhere about five hours of gameplay ago, although I have no idea why/where.
  • I can’t complete College of Winterhold. Reasons unknown.
  • I can’t find anyone to identify Unusual Gems. Reasons unknown.
  • Can’t intimidate Xander. Walk right up to him, he says I shouldn’t be there. Apparently it’s buggy for lots of people.

Bethesda game director Todd Brown thinks we have a right to be pissed off. Well Todd, I am pissed off. It is a pity that you haven’t taken the opportunity to actually offer any remedy to those players who have been robbed of enjoying your games because of these bugs. At least on the PC version of the game, you can activate a console and find some secret command that can ameliorate the problems (sure, it completely breaks the game experience to have to go out and twiddle hex digits, but at least it keeps you from completely wasting your time).

Have some pride, and fix your damn game, Bethesda.