LetterPress is a mobile turn-based word game on the App Store. Two adversaries compete by forming words from a 5x5 grid of letters. All tiles start with a background color of white. A tile becomes blue when you use it in your word, and it will become red when your opponent uses it. A blue tile surrounded on all sides by other blue tiles will become "locked" and cannot change colors, and vice-versa for red tiles. The opponent may still use locked tiles, but they will remain blue. Locked tiles appear dark blue or dark red. Once all tiles have been used at least once, no white tiles remain. At this point, whoever has more tiles their color wins!
To be clear, I didn't create LetterPress. I wrote a program that's good at playing LetterPress. It's a stand-alone Java app. The user inputs the state of the board by typing in the 25 characters and colors. My program presents the user with a list of the best possible moves via a simple GUI.
The main challenge for this project was crafting an effective evaluation function. Such a function accepts any valid game state as input and returns a single real value indicating how desirable that state would be. The game itself doesn't have a single score that the user tries to maximize. One could naively maximize the number of blue tiles, but this turns out to be a poor strategy. Defining a good evaluation function is not obvious!
I had played the game myself many times before creating the AI. That experience allowed me to discover some powerful strategies. For example, vowels are more valuable than consonants, and duplicate letters are less valuable than unique letters. My AI assigns a single value to each individual tile according to the following algorithm:
An entire board is scored by summing the values of all the blue tiles and subtracting the values of all the red tiles. This has the effect of maximizing your lead. For a given turn, the program simulates playing every playable word and scores the resulting boards. The highest scoring boards are presented to the user along with the words that produce such boards.
This algorithm is brute force in the sense that it simulates all possible moves. It is greedy in the sense that it only thinks one move ahead. There's no long-term planning.
An interesting phenomenon occurs from having duplicate letters. A single word can be constructed from different tiles. Suppose the board has two 'B's, one red and one blue. If the user wants to play 'BURRITO', it's smart to use the red 'B' instead of its blue counterpart. My AI accounts for this and considers both candidates.
Conversely, two different words can result in identical game states. The words don't need to be anagrams, either. This is a consequence of "locked" tiles. As a convenience, I aggregate such words when displaying potential boards.
There's no guarantee that this evaluation function gives rise to optimal play. In fact, it almost certainly doesn't. However, I'd be very impressed if a human could beat it.
P.S. I don't actually use this program when I play LetterPress. :)