Monthly Archives: April 2008

Dusting off Milhouse…

It doesn’t get this one right…Since looking at Olithink a few days ago, I’ve been re-bitten by the “write your own game” bug, and dusted off milhouse, my Checkers program that I started a couple of years ago, but which I abandoned because I felt that it hid some obscure bug. Today, I tried adding some additional code to determine where the bug is hiding (optimistically assuming that there is only one, which frankly, is overly optimistic). In trying to figure it out, I tried it in a simple 2 king versus 1 king endgame. Black here can force a win by driving white into the black corner at 4. If White is allowed to doddle around in the double corner, there is no way for Black to force the win. So, in this situation, with Black to move, the proper move is 14-9 14-18. This forces white to retreat closer to the black corner (2-7) and you can eventually (although, to me, novice that I am, it’s still a bit tricky to work it all the way out) trap him in the corner. White cannot movr back with 2-6 (which loses instantly, so response with 2-7, to which Black response 18-15. Now, White is well and truly screwed. If he returns to 2, then Black responds with 15-11 and wins, or if White retreats to 3, the 15-11 pins him against the wall and White loses again. But stupidly, my program seems to love the 1-5 move, which frees white to move back to the double corner, and while white gains no safety, it doesn’t make any headway to capturing him.

Some bug is hiding in here, to be sure.

Addendum: if I’ve botched the analysis of this, then I am confessing that it is just as likely that bugs remain in my own understanding of the game, and that is as likely to hinder progress as bugs in my program.

Addendum2: The problem appears to lie with my transposition tables. When I disable them, it finds the appropriate moves. I’ll have to think really hard to figure out the bugs.

Addendum3: Here’s another example. It takes way too long to complete without transposition tables, but it does seem to find the right answer.

milhouse: puzzle 80
Puzzle SIMPLE TEST BUG loaded.
Color is set to white.
	+--------+
	| - - - -|
	|- - - - |
	| - - - -|
	|- - - - |
	| - - R -|
	|- - - - |
	| - R - -|
	|- - - W |
	+--------+

milhouse: playout
        1. ... 1-6
	2. 7-2
	2. ... 6-1
	3. 14-10
	3. ... 1-5
	4. 2-6
	4. ... 5-1
	5. 6-9
	5. ... 1-5
	6. 10-14
	6. ... 5-1
	7. 9-5
	7. ... 1-6
	8. 5-1
	8. ... 6-2
	9. 14-18
	9. ... 2-7
	10. 18-15
	10. ... 7-2
	11. 15-11
	11. ... 2-6
	12. 1x10
	+--------+
	| - - - -|
	|- - - - |
	| - - - -|
	|- - - - |
	| - - - -|
	|- R R - |
	| - - - -|
	|- - - - |
	+--------+


You’ll Own “Slaves” by 1965

Robots! (Picture from Zombies from the Stratosphere)When I was a very young kid, my dad had copies of the old Mechanix Illustrated lying around. I remembered as a kid reading an article called “You’ll Own Robot Slaves by 1965!” which I remember making me think “Heck, it’s 1970, where is my robot slave?” Okay, heck, I was six. But oddly enough, it stuck with me, all these years later. Imagine my surprise to see that very article show up on the modernmechanix.com blog:

You’ll Own “Slaves” by 1965

I just thought it was neat.


Three Kings vs. Two Kings

Three Kings vs. Two KingsWell, I dusted off my checkers program source code and compiled it on my Mac. It managed to actually solve this position: a rather common one that checkers novices can’t often convert into a win. Black to move and win. My program seems to find the winning line, but only using a search significantly deeper than I think should be necessary to find it (the forced capture is 15 ply out from the start position). I’ll investigate more.


Checkerboard…

In reading up about Olithink, I recalled my own not-too-good Checkers program that I called “milhouse”. It doesn’t really work very well, despite all my attempts to make it work. I dusted it off, and was reminded about its many shortcomings. Perhaps some day I’ll fix it. But I did dust off a checkers font I found, and made a nice looking checkerboard image anyway…

The Board.

Addendum: Got the font from here.

Olithink: a small, competent chess program

I don’t know if any of you have noticed that you can see some of the things that I’ve posted on the current day in previous years on the left. I find it nice to recycle topics which I might have talked about in previous years and bring them back to the top of my consciousness. Back in 2004, I linked to two bits of sofware: the first, a fledgling internet telephone project called Skype (you may have heard of it since), but the second was Oliver Brausch’s 1600 line chess program called Olithink. In revisiting his chess page, I see he’s trimmed the size to 1424 lines, and he claims it now to be competitive with Crafty, even though Olithink doesn’t have an opening book or endgame databases. I fired it up against Crafty using Xboard, and with this single game, Crafty did beat Olithink, but I must admit that it held its own fairly well until making a mistake at move 48.

Here’s the pgn:

[Event "Computer chess game"]
[Site "mark-vandewetterings-macbook.local"]
[Date "2008.04.08"]
[Round "-"]
[White "Crafty-20.14"]
[Black "OliThink 5.1.2"]
[Result "1-0"]
[TimeControl "40/300"]

1. e4 e5 2. f4 exf4 3. Nf3 g5 4. h4 g4 5. Ne5 Qe7 6. d4 d6 7. Nxg4 Qxe4+ 8.
Qe2 Qe7 9. Qxe7+ Bxe7 10. Nf2 Nh6 11. Nc3 Nc6 12. Bxf4 Nf5 13. Nd5 Bd8 14.
O-O-O Nfxd4 15. Ne4 Be6 16. Nef6+ Bxf6 17. Nxf6+ Ke7 18. Bg5 h6 19. Ng8+
Kf8 20. Nxh6 Re8 21. c3 Nf5 22. Nxf5 Bxf5 23. Bb5 a6 24. Ba4 Re2 25. Rd2
Rxd2 26. Kxd2 Be4 27. Rg1 b5 28. Bd1 Ne5 29. b3 Kg7 30. Rf1 Re8 31. Bf6+
Kf8 32. g3 Re6 33. Rf4 Ng6 34. Rf2 Ne5 35. Be2 Nf3+ 36. Bxf3 Rxf6 37. Ke2
Re6 38. Bxe4 Rxe4+ 39. Kf3 Re1 40. Rc2 d5 41. h5 Kg7 42. g4 c6 43. Kf4 Re4+
44. Kf3 Kh6 45. Re2 Rxe2 46. Kxe2 f5 47. Kf3 Kg5 48. gxf5 c5 49. f6 Kxf6
50. Kf4 a5 51. a3 Ke6 52. b4 axb4 53. axb4 cxb4 54. cxb4 Kf6 55. Ke3 Ke5
56. Kd3 Kf6 57. Kd4 Kg5 58. Kxd5 Kxh5 59. Kc6 Kg6 60. Kxb5 Kf6 61. Kc6 Ke7
62. Kc7 Ke6 63. b5 Kd5 64. b6 Kd4 65. b7 Ke3 66. b8=Q Kd3 67. Qe8 Kc2 68.
Kb6 Kd3 69. Kc5 Kc2 70. Qe3 Kb2 71. Kc4 Kc2 72. Qf2+ Kb1 73. Kb3 Ka1 74.
Qb2#
{White mates} 1-0

The better move would appear to be 48. … Kxf5.

Anyway, it’s a very neatly written program. Check it out.

Addendum: I left Crafty analyzing the above position for five minutes. Kxf5 does appear to be better, but it appears that Olithink is already almost two pawns down, even with that move. Crafty ranks the move that Olithink chose as being down by 4 pawns.

Efficient FFT Algorithm and Programming Tricks

I do like programming “for fun”, and this includes writing programs that, well, have been written hundreds of times before, but which I never have bothered doing. Often, this is just an exercise: freely available libraries often exist for many tasks which are considerably better than anything that I write. Nevertheless, I don’t consider it pointless. There are situations where having simple, self-contained code that is free from any particular licensing issues.

For instance, I’ve never really bothered coding up an FFT implementation. (Actually, this isn’t entirely true: I helped work on an i860 based assembly language version twenty years ago when I was at Princeton, but I must admit that I didn’t do much of the heavy lifting.) When forced to use one, I typically just fire up FFTW and use it. It’s a fast, relatively simple and flexible FFT library, and well worth using. But there are some circumstances where it seems like overkill. So, I sat down and implemented a basic radix-2 in-place FFT in C using the algorithm from Crandall and Pomerance’s Prime Numbers. Running it on my MacBook, for an 8192 length complex forward transform, I get a time of about 3.95 ms per transform. The same size transform running with FFTW is almost a factor of ten faster: about .413ms per transform. Of course, my code is a big stomping 43 comfortable, loafing lines long.

But this got me thinking about how it might be possible to speed it up. I have a couple of books on my shelf at work that will probably useful (I looted them from people who were more knowledgeable than me at DSP who, for some reason, decided to give them away, but I haven’t read them). Even doubling the speed of this “naive” implementation would make it significantly more useful. And, it seems like it could be a reasonably fun thing to tinker with.

It’s too late today to make any significant progress, but I did dig up a useful link.

Efficient FFT Algorithm and Programming Tricks

Addendum: Updating the so-called “twiddle factors” in the inner loop was being done in a stupid way in my code before. It really only requires a complex multiply in the inner loop, which speeds it up considerably. Now, my 8192 element FFT takes a mere 1.16ms on my MacBook, a speedup of nearly 4x, and now it’s within a factor of 3 of the speed of FFTW. I don’t like the way it really looks yet, but it’s better than most. I’ll tidy it up soon and archive it here for future consumption.

Addendum: Now that it’s basically working, I’m left wondering about numerical accuracy. Accuracy of the discrete Fourier transform and the fast Fourier transform would appear to be relevent. It appears that my choice of recurrence relationship for the twiddle factors probably results in rather significant errors (although I also suspect that it’s more than entirely adequate for the normal audio tasks which I use these things for typically).

Tinkering with baseball scripts…

Today, I realized that I had written some scripts to dig out information on the web and present it to me in a nice, concise format a couple of years ago, but that they had not been updated. I tinkered them back into fighting form, and then worked on a new one: one that would scrape all the standings information for the major leagues.

And… here’s what the results look like. Not bad. 

------------------------------------------------------------------------
                    MAJOR LEAGUE BASEBALL STANDINGS
------------------------------------------------------------------------

                            AMERICAN LEAGUE
          WEST                  CENTRAL                   EAST
    TEX   1-1    -          KC    2-0    -          BOS   3-1    -
    SEA   1-1    -          CLE   1-0   0.5         TB    1-0   0.5
    ANA   1-1    -          MIN   1-1   1.0         NYY   1-0   0.5
    OAK   1-3   1.0         CWS   0-1   1.5         TOR   0-1   1.5
                            DET   0-2   2.0         BAL   0-1   1.5

                            NATIONAL LEAGUE
          WEST                  CENTRAL                   EAST
    SD    2-0    -          MIL   2-0    -          WAS   2-0    -
    LA    2-0    -          PIT   1-0   0.5         NYM   1-1   1.0
    COL   1-0   0.5         STL   0-1   1.5         FLA   1-1   1.0
    ARI   1-0   0.5         CIN   0-1   1.5         PHI   0-1   1.5
    SF    0-2   2.0         HOU   0-2   2.0         ATL   0-2   2.0
                            CHC   0-2   2.0

------------------------------------------------------------------------