I finally broke the 500 barrier in Scrabble! Getting 3 words using all my tiles in the first 6 goes was certainly a good start (amorous, annealer and torrents). And the combined total was 933 – not too shabby.

Filed under: Frivolity, Games, Mathematics, Programming, python | Tags: Countdown, countdown numbers game, countdown numbers game solver

One of the things about being ill is that you have to spend a lot of time in bed with nothing much to do. Having watched the whole first series of the Sopranos, I had to find something else. So here’s the result. I revisited an old program I wrote many years ago to solve the Countdown numbers game.

In this game, you’re given six numbers between 1 and 100 and a target number between 100 and 999. You’re given 30 seconds to try to make the target using the six numbers and the operations plus, minus, times and divide.

I originally wrote a program to solve this many years ago (when I was about 14 I think), but the algorithm I used was pretty horrible. I worked out by hand all the possible arrangements of brackets you could have for six numbers, and then tried each operator and number in each appropriate slot. It worked, but it was ugly programming.

Recently I’ve been learning Python for an academic project, and so I thought I may as well try rewriting it in Python. I think the solution I’ve come up with is nicer than any of the solutions I’ve found on the internet (mostly written in Java or C), although having written it I found this paper which uses a very similar solution to mine (but in Haskell rather than Python).

Python programmers might get something from the minimal code below (all comments and docs stripped out), or you can take a look at the full source code here, including detailed comments and docs explaining the code and algorithm.

My ideal (as always with Python) was to write a program you could just look at and understand the source code without comments, but I don’t think I achieved that. I’d be interested if a more experienced Python programmer could do so. Let me know.

This version is incomplete, from the slower version, and is supposed to be understandable without explanations (takes about 40 seconds to find all solutions, too slow for Countdown):

def ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0): for value, i in zip(sources,range(len(sources))): yield TerminalExpression(value=value, remaining_sources=sources[:i]+sources[i+1:]) if len(sources)>=2+minimal_remaining_sources: for lhs in ValidExpressions(sources,operators,minimal_remaining_sources+1): for rhs in ValidExpressions(lhs.remaining_sources, operators, minimal_remaining_sources): for f in operators: try: yield BranchedExpression(operator=f, lhs=lhs, rhs=rhs, remaining_sources=rhs.remaining_sources) except InvalidExpressionError: pass def TargetExpressions(target,sources,operators=standard_operators): for expression in ValidExpressions(sources,operators): if expression.value==target: yield expression

This version is actually complete, from the faster version which needs the comments to explain (takes about 15 seconds to run, good enough to win Countdown):

sub = lambda x,y: x-y def add(x,y): if x<=y: return x+y raise ValueError def mul(x,y): if x=2+minremsources: for e1, rs1, v1 in expressions(sources,ops,minremsources+1): for e2, rs2, v2 in expressions(rs1,ops,minremsources): for o in ops: try: yield ([o,e1,e2],rs2,o(v1,v2)) except ValueError: pass def findfirsttarget(target,sources,ops=standard_ops): for e,s,v in expressions(sources,ops): if v==target: return e return []

Filed under: Frivolity, Games, Scrabble | Tags: azahar, creamcheesewhizzing, forester, Games, record, Scrabble, sheading, wiselier

A new personal record: **539 points**, thanks to using all seven letters three times during the game, and twice over a triple word score. Incidentally, that’s a 264 point lead – what does that make it on azahar’s scale? Category 6, a creamcheesewhizzing? See more of our matches here.

Filed under: Academia, Epistemology, Games, Mathematics, Neuroscience, Philosophy | Tags: Checkers, Chess, draughts

I’ve been reading some interesting things about games, computers and mathematical proof recently. A couple of months ago, it was announced that the game of checkers (or draughts) had been “solved”: if both players play perfectly then the game ends in a draw. That’s sort of what you’d expect, but it’s not entirely obvious. It might have been the case that getting to go either first or second was a big enough advantage that with perfect play either the first or second player would win. So for example in Connect Four, if both players play perfectly then the first player will always win.

Checkers is the most complicated game to have been solved to date. The number of possible legal positions in checkers is 10^{20} (that is a one followed by twenty zeroes). By comparison, tic-tac-toe has 765 different positions, connect four has about 10^{14}, chess about 10^{40} and Go about 10^{170} (some of these are only estimates).

There’s a strange thing about the terminology used. A game being “solved” doesn’t mean that there’s a computer program that can play the game perfectly. All it means is that they know that if the players did play perfectly, then the game would end in a certain way. So for example with checkers, it might be the case that you could beat the computer program Chinook (which was used to prove that perfect play ends in a draw). Counterintuitively, the way to do this would be the play a move that wasn’t perfect. The number of possible positions for checkers is too large for them to have computed what the best move is in every single one. They limited the number of computations they had to perform by using mathematical arguments to show that certain moves weren’t perfect without actually having to play through them. So, by playing a move that you knew wasn’t perfect (which means that if you played it against a perfect opponent you would certainly lose), you would force the computer into a position it hadn’t analysed completely, and then you might be able to beat it.

This is a bit like in chess, where a very good player can beat a good computer program by playing a strategy that exploits the way the computer program works. Chess programs work by looking as many moves ahead as possible and considering what the player might do and what the computer could do in response, etc. However, the combinatorial complexity of the game means that even the fastest computers can only look so many moves ahead. By using a strategy which is very conservative and gives you an advantage only after a large number of moves, you can conceal what you’re doing from the computer which has no intuitive understanding of the game: it doesn’t see the advantage you’re working towards because it comes so many moves in the future.

So at the moment, there is no perfect player for either chess or checkers, but the top computer programs can beat essentially any opponent (in chess this is true most of the time but possibly not every time). This raises the question: how would you know if you had a computer program that played perfectly? For games like chess and checkers, the number of possible positions and games that could be played is so enormous that even storing them all in a database might take more space than any possible computer could have (for instance the number of possible positions might be more than the number of atoms in the universe). Quantum computation might be one answer to this if it ever becomes a reality, but an interesting suggestion was recently put forward in a discussion on the foundations of mathematics mailing list.

The idea is to test the strength of an opponent by allowing a strong human player to backtrack. The human player can take back any number of moves he likes. So for example, you might play a move thinking it was very clever and forced your opponent to play a losing game, but then your opponent plays something you didn’t think of and you can see that actually your move wasn’t so great after all. You take back your move and try something different. It has been suggested that a good chess player can easily beat most of the grand master level chess programs if they are allowed to use backtracking. The suggestion is that if a grand master chess or checkers player was unable to beat the computer even using backtracking, then the computer is very likely perfect. It’s not a mathematical proof by any means, but the claim is that it would be very convincing evidence because the nature of backtracking means that any weaknesses there are in the computer program become very highly amplified, and any strengths it has become much weakened. If it could still beat a top player every time, then with very high probability there are no weaknesses to exploit in it and consequently it plays perfectly. (NB: My discussion in this paragraph oversimplifies the discussion on the FOM list for the sake of simplicity and brevity, but take a look at the original thread if you’re interested in more.)

This leads to all sorts of interesting questions about the nature of knowledge. At the one end, we have human knowledge based on our perceptions of the world and our intuitive understanding of things. Such knowledge is obviously very fallible. On the other end, we have fully rigorous mathematical proof (which is not what mathematicians do yet, but that’s another story). In between, there is scientific knowledge which is inherently fallible but forms part of a self-correcting process. Scientific knowledge always get better, but is always potentially wrong. More recently, we have probabilistic knowledge, where we know that something is mathematically true with a very high probability. Interactive proof systems are an example of this.

The argument above about backtracking in chess suggests a new sort of knowledge based on the interaction between human intuition and computational and mathematical knowledge. These newer forms of knowledge and the arguments based on them are very much in accord with my view of the pragmatic nature of knowledge. My feeling is that interactions such as this between computational, non-intuitive knowledge, and human intuitive understanding will be very important in the medium term, between now and when artificial intelligence that is superior to our own both computationally and intuitively becomes a reality (which is I feel only a matter of time, but might not be in my lifetime). At the moment, these new forms of knowledge are really only being explored by mathematicians and computer scientists because the human side is not yet well enough understood. It will be interesting to see how this interaction between human and computational/mathematical understanding will develop as our understanding of how the human brain works improves.

If you found this entry was interesting, you might also be interested in two unfinished essays I have on epistemology without truth and the philosophy of mathematics.

So azahar introduced me to Scrabulous. The first match was a win for her, but a double rematch is happening now.

The game started well for az with *rootier* (hah!). Nice to get a blank tile on your first go. I fought back valiantly to gain a 10 point lead when suddenly – whammo! – I was hit with *quin* for 70 points. I knew az had the Q, but I was holding the last U. Rather foolishly, I forgot about the second blank that was still unplayed. *Fiat*, *jib* and *upo* (wtf?) weren’t enough to get me close especially with *hied* on a triple word score and I ended 41 points down, 400 to 359. Not even a creaming!

I’ve been quite impressed by the abilities of my shiny new phone, especially the sort of games and programs you can run on it. I downloaded software to calculate poker odds, translate words between 15 different languages, connect to Google maps, and tell me all sorts of political statistics from the CIA World Factbook (which surprisingly I’ve already used in one argument I got into with someone!).

So I wondered if I too could write some fantastic software for my phone. What I really wanted to do was to write a program to crack the Enigma code on my phone, thus proving the claim that is sometimes made that modern phones have as much computing power as the whole computing effort of WW2. That seemed too much like hard work though. So instead, I set myself the more modest task of beating Dictionary Corner in Countdown.

For those who don’t know, Countdown is a gameshow in the UK. One of the games is to find the best word you can make with 9 randomly chosen letters in 30 seconds. After the contestants have said what their best words are, Dictionary Corner tell them what they could have got. Obviously they use a computer to do it, but until now we the viewers have been at a disadvantage unless we were willing to have our laptops out while we watched the show. No longer!

I present the mobile phone Countdown letters game solver (click to go to the download page, for Java enabled phones). It will find the five best words you can make in only 10 seconds (or less on a newer phone than mine). Here it is in action on a Countdown conundrum:

Sadly, even the awesome power of the mobile phone is not enough to beat Countdown legend Conor Travers (14) who managed to get this one in under two seconds.

Do please download it and have a go with it. It works on my phone but I’d like to have feedback to find out if it works for other people’s phones. For the technically minded, it requires J2ME, including MIDP2.0 and CLDC1.0, or better.