A simple re-write system using a Markov variant.

Last week I found Jeremy Wertheimer's master thesis via a news:comp.lange.scheme posting about the Rete algorithm. Jeremy is now the President and CEO of ITA Software and on their career page I found the Word Numbers puzzle:

"If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?"

If you enjoy programming puzzles, there's even more in their puzzle archive.

I won't talk about the solution of the puzzle here (well, possibly parts of the solution, but not the tricky bits anyway) but rather take one piece of it out and show a minimal implementation to perform that particular task: to rewrite any given number (from 1 to 999,999,999) into it's text representation. In the long description of the puzzle they've added: "omitting spaces, 'and', and punctuation" which means that 1,709 translates to onethousandsevenhundrednine and 500,000,000 is written fivehundredmillion. It's easy to add 'and' and spaces, but fixing that is left as an exercise for the reader :-)

I've been looking into the Markov Algorithm quite a bit lately and have used this piece of code for various things the last weeks. The Markov Algorithm is really simple to implement but is not very fast, it's not necessarily very slow either but that depends on what you compare it with I guess.

There are a few differences from text-book Markov in my implementation. For example, there's no way to specify a terminal rule. Also, I'm using recursion to pass the result from one rule back into the system.

Let's have a look at some code (~30 lines of Python).

>>> import re
>>> def evaluate(fact):
...     print "evaluate(%s)" % (fact)
...     for lhs, rhs in rules:
...        match_obj = re.match(lhs, fact)
...        if match_obj is not None:
...            return "".join(fire(rhs, match_obj))

>>> def fire(rhs, match_obj):
...     print "fire(%s, %s)" % (rhs, match_obj.re.pattern)
...     if isinstance(rhs, str):
...         try:
...             return match_obj.group(rhs) # 1a) substitute (pattern match)
...         except IndexError:
...             return rhs                  # 1b) substitute (constant)
...     elif isinstance(rhs, tuple):
...         partial_results = [fire(action, match_obj) for action in rhs]
...         return "".join(partial_results) # 2) substitute and concatenate
...     elif isinstance(rhs, list):
...         partial_results = [fire(action, match_obj) for action in rhs]
...         return evaluate("".join(partial_results)) # 3) substitute, concatenate and eval

>>> def convert(n):
...    number = str(n)
...    return evaluate(number)

The fire method can handle three different types of actions: 1) substitute, 2) substitute and concatenate, 3) substitute, concatenate and continue evaluation. Substitution can be done in two different ways, either using a constant or part of a pattern match. For completeness, I really should add a way to perform a real evaluation/execution of Python code but that's for another blog post.

Ok, so far we've got the implementation. Now, all we need are some rules.

Let's start with the easiest ones (1-digit numbers):

>>> rules = [("1", "one"), ("2", "two"), ("3", "three"), ("4", "four"),
... ("5", "five"), ("6", "six"), ("7", "seven"), ("8", "eight"), ("9", "nine"), ]

Each rule is expressed as a tuple containing 2 parts. A Left Hand Side (LHS) and a Right Hand Side (RHS). The LHS is used as a regular expression pattern by the evaluate function and the RHS is interpreted as a constant. So now we can do:

>>> convert(2)
'two'

which is not very interesting. Let's add some more rules.

>>> rules = [("(?P[digit]\\d{1})0", (["digit"], "ty")),
... ("(?P[digit1]\\d{1})(?P[digit2]\\d{1})", (["digit1", "0"], ["digit2"])),] + rules

Now, that's a bit more complicated. But, stay with me here. The LHS is blue and the RHS is green. The first rule basically says: [a]0 should be transformed into [a]ty (for example, 40 becomes four-ty). The second rule says: [ab] means [a]ty[b] (for example, 43 means four-ty-three).

We're nearly done with the 2-digit numbers. the problem is that the current rule base cannot handle numbers like 37.

>>> convert(37)
'threetyseven'

It's kind of close but still wrong. We'll have to add a few more constants.

>>> rules = [("20", "twenty"), ("30", "thirty"), ("50", "fifty"),
... ("80", "eighty")] + rules
>>> convert(37)
'thirtyseven'

That's better, but we still can't handle 17.

>>> convert(17)
'onetyseven'
>>> rules = [('10', "ten"), ('11', "eleven"), ('12', "twelve"),
... ('13', "thirteen"), ('15', "fifteen"), ('18', "eighteen"),
... ("1(?P[digit]\\d{1})", (["digit"], "teen")),] + rules
>>> convert(17)
'seventeen'

That's actually all that's needed to handle the tricky numbers (between 1 and 99). All 3-digit numbers ([abc]) are really just: [a]hundred[bc]. Similarly all 4 to 6-digit numbers ([a{1,3}bcd]) are [a]thousand[bcd] and 7 to 9-digit numbers ([a{1,3}bcdefg]) are [a]million[bcdefg].

>>> rules = [("(?P[digit]\\d{1})00", (["digit"], "hundred")),
...  ("(?P[digit1]\\d{1})(?P[rest]\\d{2})", (["digit1", "00"], ["rest"]))] + rules
>>> convert(373)
'threehundredseventythree'
>>> convert(303)
Traceback (most recent call last):
 ...
TypeError: sequence item 0: expected string, NoneType found

Weren't we done? The missing piece is a rule (with the highest priority) that tells the implementation to ignore leading zeros. It's required because we re-write and call the evaluate function on a partial result. Let's look at the call trace:

evaluate(303)
fire((['digit1', '00'], ['rest']), (?P[digit1]\d{1})(?P[rest]\d{2}))
fire(['digit1', '00'], (?P[digit1]\d{1})(?P[rest]\d{2}))
fire(digit1, (?P[digit1]\d{1})(?P[rest]\d{2}))
fire(00, (?P[digit1]\d{1})(?P[rest]\d{2}))
evaluate(300)
fire((['digit'], 'hundred'), (?P[digit]\d{1})00)
fire(['digit'], (?P[digit]\d{1})00)
fire(digit, (?P[digit]\d{1})00)
evaluate(3)
fire(three, 3)
fire(hundred, (?P[digit]\d{1})00)
fire(['rest'], (?P[digit1]\d{1})(?P[rest]\d{2}))
fire(rest, (?P[digit1]\d{1})(?P[rest]\d{2}))
evaluate(03)
fire((['digit1', '0'], ['digit2']), (?P[digit1]\d{1})(?P[digit2]\d{1}))
fire(['digit1', '0'], (?P[digit1]\d{1})(?P[digit2]\d{1}))
fire(digit1, (?P[digit1]\d{1})(?P[digit2]\d{1}))
fire(0, (?P[digit1]\d{1})(?P[digit2]\d{1}))
evaluate(00)
fire((['digit'], 'ty'), (?P[digit]\d{1})0)
fire(['digit'], (?P[digit]\d{1})0)
fire(digit, (?P[digit]\d{1})0)
evaluate(0)
fire(ty, (?P[digit]\d{1})0)

There's no rule to handle something like '03'. We could of course add ("0", "zero") to the rule base but that would be wrong (we'd get 'threehundredzerotythree'). The right thing to do is (and we're also adding the rules for thousand and million):

>>> rules = [("0+(?P[number]\\d+)", ["number"]),
...  ("(?P[number]\\d{1,3})000000", (["number"], "million")),
...  ("(?P[number]\\d{1,3})(?P[rest]\\d{6})", (["number", "000000"], ["rest"])),
...  ("(?P[number]\\d{1,3})000", (["number"], "thousand")),
...  ("(?P[number]\\d{1,3})(?P[rest]\\d{3})", (["number", "000"], ["rest"])), ] + rules
>>> convert(303)
'threehundredthree'
>>> convert(911610034)
'ninehundredelevenmillionsixhundredtenthousandthirtyfour'
>>> convert(5000000)
'fivehundredmillion'
>>> convert(1709)
'onethousandsevenhundrednine'

The funny thing is that solving it this way feels more natural to me than any other way. I think I've become damaged ;-)

Constructing an AI player for Pentago

I wrote my first AI player for Pentago a year and a half ago. It is a simple player which uses board patterns to decide where to place the next marble and which block to turn. I had no idea at the time that what I'd done was basically a very limited and modified implementation of the Markov Algorithm.

The player is simple but the implementation isn't trivial. Each pattern is expressed as a function returning either None or a tuple specifying where to place the next marble and optionally which block to turn.

Here is the function for placing the next marble:

>>> def placeMarker(self):
...   for method in [  self.winIfPossible,
...                    self.avoidImmediateLoss,
...                    self.blockThreeInARow,
...                    self.captureCenterPositions,
...                    self.blockFourInASquare,
...                    self.positionFourInASquare,
...                    self.positionThreeInARow,
...                    self.positionTwoInARow,
...                    self.any, ]:
...     p = method(self.game.getBoard())
...     if p is not None:
...       return p % 6, p / 6

There is also a method called rotateSquare performing similar work.

This player isn't very good but it isn't very bad either. It's remarkable how few patterns you actually need to get a "decent" player.

The problem with this implementation is that it takes a lot of effort to add a pattern. Once I learned about the Markov Algorithm I was able to re-structure the code such that adding a pattern is as easy as adding (for example) "???$*AA$???" to the Rules repository (I know that the example, and the whole pattern language, is a bit cryptic but I'll post about that some other time).

"???$*AA$???" can actually be used for both blockThreeInARow and positionTwoInARow (it all depends on who's turn it is). Using the Markov Algorithm requires *more* patterns to be described but since they're simpler it's a net win (in lines of code). To describe the winIfPossible pattern I need to specify it as three different patterns (because you can win horizontally, vertically and diagonally).

Of course, this type of player can never play better than I can (since I have to feed it patterns in order for it to improve). So my next move is to implement a Minimax player.