The contents of this page have been written by me around 2003. Since then, I have learned a lot, both technically and grammatically. As such I cannot guarantee that any of the techniques described in here are still accurate (odds are good that this can be done far easier nowadays).

GridLock

Once I made a tictactoe computer player for furcadia using only dragonspeak. Though it worked well it wasn't the most rewarding experience as it seemed such a trivial game. So this time I've made a computerplayer for a far less trivial game and it actually plays a decent game (though unfortunately it's not too hard to beat).

The game

The game itself plays on an 8x8 square with a random number from 0 to 10 in each square. The human player starts in a randomly select column and gets the choice to pick one number and add it to his score. The column then switches to a row (based on the position from which the furre picked the number) and the computer gets to choose a number. Then it switches to a column again and the player gets to choose a number. This continues this way until one of the two can't take a number anymore, at which point the one with the highest score wins.

The reason why this game seemed suited for conversion to a furcadia computerplayer was that, at all times, there are no more than 8 possible moves. If we make it so that each move is checkable in one second, then the computers turn will take at most 8 seconds. Second of all there is a simple routine that already produces a reasonably decent computerplayer.

The game mechanics

The game has 8 different states it can be in, numbered as follows (they're easy to find in the Dragonspeak file):

  1. reset all variables and restart the game.
  2. initialise the game by placing random numbers on all the squares.
  3. wait for a player to enter the game.
  4. prepare for a player move (and check whether the game has ended yet).
  5. accept a players move.
  6. prepare for the computers move (and check whether the game has ended yet).
  7. calculate the computers move.
  8. clean up and end the game.

These states pretty much speak for themselves and are documented in the DS, so I'll keep it at this and refer you to the download at the bottom for the dream and the actual dragonspeak.

The play routine

The easiest routine would be to just pick the highest number in the row. Finding the maximum of 8 numbers is relatively easy in furcadia, so this computerplayer would be fast as well. However, it doesn't look ahead at all and as such will make some very stupid mistakes along the way. So the routine we're going to consider is a bit more complex.

Instead of looking at only our own row, we're going to look at the columns as well and try to predict what the human player will choose. So now we use the 'highest number' routine on the columns to determine what the human player would do. Once more we're going to take a look at each square in the row, but now we're going to look at the gain we're going to get from it when we take the human move into account. So say we will win 8 points by choosing a certain square, but the human player will then be able to grab a 10, we'll have a gain of -2, which is not very desirable.

Performing this check for each square and selecting the one with the highest gain will result in a better computer player then, because it will anticipate the players actions. Ofcourse we could take this one level further and consider the players move, while taking the computers actions after that into account, but that would get too complex in furcadia.

I've also commented the dragonspeak for this bit, so make sure you take a look there and try to figure out how exactly it does the job. Keep in mind that the inner loop (the one checking the columns) has been unrolled and as such takes up quite a bit of (copy/paste) dragonspeak. Technically this wasn't necessary, but I thought 64 seconds of thinking time would be a bit too much.

Play the game yourself

Even if you're not the least bit interested in the rant above (I wouldn't blame you), you will probably want to play the game a bit. Just download the dream below, relink the patch and upload it.

GridLock (7.50 kB)

Enjoy!