brainwagon

Work on my checkers program milhouse has stalled a bit: I have a problem in the transposition tables that is fighting against my endgame database attempt, and it’s subtle enough that I haven’t had time to work it out. I’ve been relaxing by reading some more about other board games, and have begun to read a bit about attempts at games with very high branching factor like Go and Hex. I frankly don’t have the brain power for Go, so I thought I might think about hex a bit more. It’s just about as simple a game as you can get, and yet has deep strategy that seems more intuitive to me. Some useful information is stored on the HexWiki.

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.

Here’s a page that answered some of my questions about Sudoku. Sudoku enumeration

Now, if only it could answer the most pressing question I have: why am I so slow at them?

[tags]Puzzles,Recreational Math,Sudoku[/tags]

According to digg, pong is celebrating its 34th anniversary today. Feh. I’m older than that.

Sniffle.

Bonus links: Wikipedia has some nice info, including a link to William Higinbotham’s Tennis for Two game developed at Brookhaven National Labs.

Oh, and the animated gif on the right? Screendumps from the CHIP-8 emulator I wrote a few years back.

Ben Fry has some cool graphics which visualize the code in several old Atari 2600 video games. Basically, he disassembles code and marks all possible branches with arcs between the lines of code, and changes all data tables to graphical representations of the bit patterns, revealing many sprites and other data tables. I dunno how useful it is, but it’s kind of neat.

Zome is a nerd toy that allows you create all sorts of amazing polyhedral models. Some people are more serious about them than others.

Addendum: A couple of days ago, I picked up one of those generic “ball bearing and magnet” sets that allow you to build similar structures at Walgreens. It was $9.99 for a 250 piece set, which seemed pretty good. I assembled a stellated icosahedron, but I don’t really recommend the set: the magnets are incredibly weak, and it’s almost impossible to move the model without destroying it.

Wow. Very cool to take this step back in time and see what young hackers in 1913 were doing. A lot of lame stuff, but some gems, like a line harmonograph, a “key card” for writing secret codes on post cards, handcutting gears and racks for models, a miniature “Pepper’s Ghost”, and a homemade water wheel. And that’s just in the first hundred pages, there are almost six hundred! Be sure to check out the PDF file.

A classic of puzzles (most of which I would call only marginally mathematical) Amusements In Mathematics, by Henry Ernest Dudeney. has been made available via Project Gutenberg. Lots of puzzles having to do with geometric dissection, board games, and a host of other topics. Very nice.

May you be touched by his noodly appendage.

Hint: use the shadow to determine if you are over your converts.

My best was 681 930 982 feet.

Does playing this make me a bad person?

I was in Fry’s last weekend, and was just browsing the cheap video game aisle’s with my wife, when I noticed that the quirky Japanese title Katamari Damacy was only $19.99. I think it was Tom who first told me about this rather odd little game, and when I explained what it was to my wife, she shocked me by tossing it into the basket along with all the other crap we were buying.

There is no mistaking this game is a Japanese import. It has a very quirky style, with very odd English titles which undoubtably are a bad translation from some equally quirky Japanese. The backdrop: the King of the Cosmos has destroyed all the stars, and they need replacing. You are the Prince, a strange little green guy who gets to push around a magnetic ball called the Katamari. When the Katamari rolls up against a small object, it will stick to it, and the ball gets bigger. The bigger the ball gets, the more stuff will stick to it. At first, you can only pick up tacks and dice. As the game progresses you can pick up dogs, humans, boulders, giant octopuses and supertankers. Upon completing each level, the Katamari is converted into stars.

It is very quirky.

And fun. The graphics are fairly simple, but incredibly varied. There are all sorts of things going on in the house, town and city in which you work. The sheer variety is very compelling. It reminds me vaguely of the experience I had when I played Zelda: Ocarina of Time for the first time: the town was the first town in a game that felt like people lived there. Similarly, there are all sorts of things going on in this town: dogs barking, elephants, schools, bears, sumo wrestlers, cranes, and a billion other objects. It’s really pretty staggering. And fun.

Did I mention it was fun?

If you are looking for a cute game, with unusually innovative game play, simple, non-violent, try checking out Katamari Damacy.

Half shadow puppet theater, half first person shooter: Deanimator.

Link courtesy of Dan.

Where your host expounds about his largely academic interest in games of chance.

Links:

::amazon(”0394703103″, “Beat the Dealer, by Ed Thorp”)::

The classic, pick up a copy and read on the flight to Vegas. You can and should read his Mathematics of Gambling as well, especially since it’s available online for free.

::amazon(”0929712137″, “The Theory of Blackjack by Peter Griffin”)::

Want to understand the mathematics behind card counting? This is the book to have, terrific for those of us with a largely academic interest in blackjack.

::amazon(”0743249992″, “Bringing Down the House by Ben Mezrich:”)::

The story of how a group of MIT students used team play to win millions from Vegas. I found it to be a pretty interesting look into a world that is probably best viewed from the outside.

::amazon(”1880685000″, “The Theory of Poker by Skylansky”)::

I was hoping for a book as good as Griffin’s is on blackjack. The book is good, but really doesn’t ground you in the mathematics you might think you need. It does teach you how to think about poker (and to some extent gambling), but I would almost take those as gimmes.

While watching the World Poker Tour today, I saw Mike Madusow survive going all in against a pair of aces, and surviving by hitting three kings on the river. During the break, they had this question as a quiz:

Which hand has the best odds going up against A♦ A♣ in the hole?

• K♦ K♠
• 10♦ 9♦
• Q♣ J♦

It seems obvious that the third is right out, but what might be a teensy bit surprising is that you have a better shot with 10 ♦ 9♦ against a pair of aces than you do with the pair of kings. Apparently the additional chances to hit straights and flushes outweigh the additional rank which is mostly useless against the aces. You can use the GNU poker eval program to verify this:

[fishtank] % ./hcmp2 AD AC KH KS
1712304 boards
  cards      win  %win       loss  %lose       tie  %tie      EV
  Ac Ad  1388072  81.06    317694  18.55      6538   0.38     0.813
  Ks Kh   317694  18.55   1388072  81.06      6538   0.38     0.187
[fishtank] % ./hcmp2 AD AC TD 9D
1712304 boards
  cards      win  %win       loss  %lose       tie  %tie      EV
  Ac Ad  1338249  78.15    367143  21.44      6912   0.40     0.784
  Td 9d   367143  21.44   1338249  78.15      6912   0.40     0.216
[fishtank] % ./hcmp2 AD AC QC JH
1712304 boards
  cards      win  %win       loss  %lose       tie  %tie      EV
  Ac Ad  1450987  84.74    254763  14.88      6554   0.38     0.849
  Qc Jh   254763  14.88   1450987  84.74      6554   0.38     0.151

I thought it was cool.

Gamespy talks about Will Wright’s newest game Spore. It sounds fascinating on many levels.