This is the archived CodeCup 2004 website.
Click here to go to the new CodeCup website.
logo  

CodeCup 2004

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.