The game Connect Four is a pretty neat little game, which was solved back in 1988 by two different individuals: James Allen and Victor Allis. It makes a pretty nifty benchmark too, called Fhourstones. My modern desktop evaluates over 10 million positions per second, and can solve the entire game in about 3 minutes. Pretty cool.

The Fhourstones Benchmark

Jonathan Schaeffer used to have a page that contained the rules for Awari that are typically used in computer play. Through the miracle of the Internet Wayback Machine, you can look them up here:

Rules of Awari.

Previously I wrote a simple program to compute the number of positions that are legal in Checkers. I thought I might perform the same analysis for the game of Awari. The simplest approximation that you can get is by counting the number of ways that n undistinguished stones can be distributed in m distinguished pits. A few minutes scratching (or searching the web) will show you that n undistinguished balls can be distributed in m distinguished pits in comb(n+m-1, m-1) ways. Awari begins with 48 stones and 12 pits, so if we sum all the totals, we’ll get the total number of positions. Well, it is an overestimate. First of all, there are no legal positions in Awari with 47 stones, since the first capture either captures 2 or 3 stones. And, there are many positions in here which cannot occur in the game. For instance, in the real game, the non-moving player can never have stones in every pit (except the first move, of course) because he would have previously had to empty one pit to sow it, and that pit is always skipped when you sow. And these totals don’t include any kind of “reachability” analysis: many nodes can’t be achieved in play.

According to Romein and Bal’s work, there are 889,063,398,406 positions which are reachable in Awari. Writing up my naive totaller gives the following totals:

--------------------
 1                12
 2                78
 3               364
 4             1,365
 5             4,368
 6            12,376
 7            31,824
 8            75,582
 9           167,960
10           352,716
11           705,432
12         1,352,078
13         2,496,144
14         4,457,400
15         7,726,160
16        13,037,895
17        21,474,180
18        34,597,290
19        54,627,300
20        84,672,315
21       129,024,480
22       193,536,720
23       286,097,760
24       417,225,900
25       600,805,296
26       854,992,152
27     1,203,322,288
28     1,676,056,044
29     2,311,801,440
30     3,159,461,968
31     4,280,561,376
32     5,752,004,349
33     7,669,339,132
34    10,150,595,910
35    13,340,783,196
36    17,417,133,617
37    22,595,200,368
38    29,135,916,264
39    37,353,738,800
40    47,626,016,970
41    60,403,728,840
42    76,223,753,060
43    95,722,852,680
44   119,653,565,850
45   148,902,215,280
46   184,509,266,760
48   279,871,768,995
--------------------
   1,171,666,558,334

which indicates that approximately 1/4 of all the positions enumerated here are illegal or unreachable. Still, the ease of indexing using this naive idea may compensate for doing anything more compact but more confusing.

Checkers is driving me nuts. I thought maybe I should implement a different board game, just for variety. Chess and Othello seemed obvious, backgammon might be fun, but games from the Mancala family also seemed interesting. What’s more, you can even buy a cheap Chinese-made Mancala set at Target. Which I did. Apparently Awari has been solved completely, resulting in a complete 48 stone database which acts as an Oracle. I’m not sure that matters to me. Anyway, just thought I’d write this down, so when a year passes and I haven’t done anything, I’ll be nudged into thinking about it again.

Okay, I woke up this morning, and decided to code up a version of a MasterMind solver. About fifteen minutes later, I had this tremendously slow implementation, which nevertheless seems to solve patterns very pretty quickly (averaged just 4.71 guesses in the short run of 100 trials that I just ran. It’s tremendously slow though, for reasons which I should have guessed before I wrote it. Nevertheless, it does work fast enough that if you wanted to write a Mastermind solver, it would work just fine.

Here’s the idea. Start by simply trying to guess the code by picking one at random. Assuming that you didn’t win, you need to generate a new guess. Let’s generate one and pretend that it was the secret. If you evaluate it against all the previous guesses you make, it would need give the same results. If it doesn’t, it can’t be the secret, so don’t use it as your guess. Try a different one.

That’s it. Of course the reason it’s slow is that when you get to the end, very few of the random choices you’ll make will match all the previous results (there are 1296 possibilities in the 6,4 version of classic Mastermind), so you might have to try lots and lots and lots of guesses before you find the consistent one. The better way would be to use a list of all possible codes, and strike out the ones in each round that are inconsistent with the previous guesses. Then you can select among all consistent codes. I’ll write up that optimization shortly, which should speed up the code by several hundred times. But this one does work… check it out.

#!/usr/bin/env python
#
# A naive implementation of the game MasterMind, to test some ideas 
# that I learned in a brief scan of some of the known literature.
#

import random
from sets import Set

# traditional Mastermind uses six different colors, not exactly certain
# what they were, so I chose Red/Yellow/Blue/Orange/Green/Purple...

colors = ['R', 'Y', 'B', 'O', 'G', 'P']


# generate a random secret code (or guess)

def randomcode():
        return ''.join([random.choice(colors) for i in range(4)])

def evaluate(guess, secret):
        b, w = 0, 0
        gs, ss = Set([]), Set([])
        for i in range(4):
            if guess[i] == secret[i]:
                b = b + 1 
            else:
                gs.add(guess[i])
                ss.add(secret[i])
        return b, len(gs.intersection(ss))

def solve(secret):
        history = []
        guess = randomcode()
        nguesses = 1
        while True:
                b, w = evaluate(guess, secret)
                history.append((guess, b, w))
                print guess, b, w
                if b == 4:
                        break   # we solved it...
                # generate a new random guess, consistent with
                # all the previous guesses.
                nguesses = nguesses + 1 
                while True:
                        guess = randomcode()
                        consistent = True
                        for g, b, w in history:
                                nb, nw = evaluate(guess, g)
                                if nb != b or nw != w:
                                        # nope, not consistent
                                        consistent=False
                                        break
                        if consistent:
                                break
        print
        return nguesses

ROUNDS = 100
totalguesses = 0

for x in range(ROUNDS):
        totalguesses = totalguesses + solve(randomcode())

print "average number of guesses was %.2f" % (float(totalguesses)/ROUNDS)

Addendum: I coded up the optimization that I mentioned above, and it seemed not to help that much. Run time dropped from 21 seconds to 17 or so. Not very good. Perhaps I don’t know what’s going on here. Then again, I still haven’t had any caffeine this morning, so perhaps my puzzler isn’t quite up to speed yet.

Over at the Programming Praxis blog, the task of the day is to write a program to solve the game Mastermind. Mastermind is actually a fairly interesting game mathematically speaking, and has a fairly rich set of mathematics behind it, and yet it’s actually small enough to analyze easily using modern computing power. I might try to use this as a test program to try out the new Go programming language from Google. In the mean time, here are some links:

Investigations into the Master Mind Board Game

Here’s a link to computer science luminary Don Knuth’s paper The Computer As Master Mind

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.

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.