The winning algorithm

We asked Emil Kraaikamp, the winner of the CodeCup 2004, to give a brief description of his LuckyWords program "DynprogV2b".

DynprogV2b

First of all I'd like to say that I enjoyed writing a program for this codecup competion. I will try to explain how my program works and how it won the competition.

Fixed GameBoard and Dynamic Words

Dynprog uses a fixed gameboard (FGB), and it looks like this:

  XXXXXXX
1 XX.....
2 XX.....
  XXXXXXX
3 XX.....
4 XX.....
5 XX.....

These FGBs use the idea that I get to choose at least 24 letters. As you can see, I already made four seven-letter words (2 horizontally and 2 vertically) , so I have already 4x13 = 52 points. I have 26 different versions of these FGBs, for every starting letter one. I tried to find the most difficult FGBs. That means that they consist of low-frequency letters (like Q,J,Z.... etc).
You can see that I numbered some lines in the picture above. Those lines are dynamic words (DW). A DW consists of a list of words (seven letters only) that can still be made. It also consists of a number that represents the chance to finish the word (to get 13 points). When a new letter is put at a certain position in a DW the list and the number will be updated.

Here's an example of an FGB for the starting letter Z:

  ARCHWAY
1 CO.....
2 AM.....
  JAZZILY
3 OU.....
4 UN.....
5 ST.....

And these are the words that can still be made from the starting letters CO:

  COACHED
  COACHER
  COACHES
  COACTED
  COADMIT
  .
  .
  .
  COZENER
  COZIEST

Gameplay

When my program starts it gets the starting letter, and then it picks a FGB. This FGB is now called the goal gameboard (GGB).

My turn
When it's my turn to pick a letter I first check if I can pick a letter from the GGB, and if I can, I will pick the most difficult (low-frequent) letter. I do that to make it hard for the opponent to get points (you can't make a lot of good words with difficult letters). If I already achieved my GGB, I try to pick a letter in any of the five DWs. One rule: try to make the chance as high as possible to finish the words later on in the game. When the game is almost finished (when 40 moves have been made), I try to finish the DWs as soon as possible to get the maximum result; otherwise I could have a lot of almost seven-letter words, and they don't give me enough points.

Not my turn
I first check if I can use his letter in my GGB, if that's not possible I pick a position in any of the DWs (same way as when it's my turn).

ps. Too bad I couldn't win 250 euros.