I have almost finished a new game for the touch table. The game is based on the board game “Keesdrow” and is similar enough that I am not going to be selling this game. “Keesdrow” is a word finding game somewhat similar to Boggle, but the board is much bigger and each letter can only be used three times. The first time a letter is used it scores its base value, the second time it scores double and the third time it scores triple. This makes it very important to find words that have repeated letters and use letters that have already been used once or twice.
The most interesting part of this project was the AI. I expected it to play significantly better than it does.
The board is variable size, but can go up to a 16×16 grid of letters. Finding all the available words is a very similar problem to what I already solved for Writter’s Block. I was worried that the significantly larger board would increase the calculation time too much. But it is still only takes a second or two to find all the available words. Fortunately, the Writter’s Block code was already setup to perform the calculation in a thread.
The AI in Writter’s Block was so overwhelming that it only had to play a small percent of the words that it found to beat any human. That is not really the case in Keesdrow. Humans are actually pretty good at finding words that are near the maximum possible score.
I didn’t want there to be too much of an advantage or disadvantage to sitting to the left of a computer player, so the computer needs to be careful not to leave a lot double and triple point tiles available for the next player. And, like Writter’s Block, I didn’t want the computer to use a lot of obscure words that the human players have never heard of. So the final word scoring algorithm applies penalties to words that score too many or too few points (based on the difficulty setting), leaves doubles/triples and are uncommon.
In Writter’s Block, I had used the word definitions from Wiktionary to determine the ‘commonness’ of a word. For this project, I decided to improve the word counts by using the text from Wikipedia instead. Wikipedia is huge (27 GB of text) and I upgraded to Visual Studio 2012 so that I could build a 64 bit application and use the 64 bit version of fseek and fstream. Parsing Wikipedia was a bit of a pain because of the size of the file, the size of individual lines (>500K) and the sometimes odd wiki style formatting.
Overall the project was pretty easy. I spent more time on the Wikipedia/Wiktionary parsing than I did making the game.