I’ve been thinking about how a Letterpress-playing algorithm might work. If programming to play and/or analyze Letterpress games aren’t of interest to you, you can safely skip the rest of this post!
For the record, I think that it’s fair game to use a spellchecker if you can’t remember how to spell something …
bivuacs bivoacs bivuoacs oh yeah, bivouacs … and fair to try an “un-” prefix or “-ly” suffix or whatever just in case … and certainly fair to use all those scrabble words I’ve learned over the years even if I have no idea what many of them mean. But using an algorithm without the opponent knowing that you’re doing it is going too far, IMO. Also, I’m no expert on game AI by any means, but it’s a long-time interest. So here goes …
I’m assuming that the algorithm would use alpha/beta pruning (http://en.wikipedia.org/wiki/Alpha-beta_pruning). One thing that makes me think this approach could solve most boards perfectly is that for most games, the depth of the tree never has to get very large. Most games seem to be less than twenty moves, i.e., ten per player, and the kind of situation where a game can go a lot longer is, as far as I can see, only the situation in which a few unclaimed tiles are left and the players are jockeying to get the last move.
Also, in any given position, my intuition is that of all the possible moves some are clearly much stronger than others in ways that could be fairly well recognized heuristically. The number of defended tiles is an obvious heuristic. Add a bonus for a defended edge tile (more for a corner), and a bonus for adjacent defended tiles. A tile that is going to be in high demand, such as the only “E” on a board with few vowels, should carry an additional bonus.
All of those things being equal, it should prefer positions where the score differential is higher. And positions where the number of unclaimed letters is lower, to give it a bias for trying to finish off a game when it can.
Even if some boards would be hard to solve perfectly, a fairly simple algorithm should be far stronger than almost any human player. It’s a much easier game to solve than Scrabble, for example.