HCSW Technical Blog

HCSW Technical Blog

by

Doug Hoyte


through
Viewing entries 32 through 32.
Most Recent Blog Entries
RSS Feed

32. DVONN!
Mon, Nov 19 2007

I just released an HCSW project I created a couple years ago but forgot about until recently: A text interface and AI for the board game DVONN. This game is, like all good games, easy to explain and learn but makes for very rich, complicated, strategy-filled matches. The AI hasn't been tuned much but is still quite good. To play you will need a Common Lisp environment and our program dvonn.tar.gz. This code is licensed under the GNU GPL. Here is a more detailed description of the game and our AI along with a "screenshot":

DVONN is played on a board of hexagons using 23 white, 23 black, and 3 red pieces. The board has 49 pegs for the pieces. Initially, players take turns placing the red pieces, called the DVONN pieces, and then their own pieces onto the pegs at any locations they desire without stacking. The program also has a mode to place them randomly in case you wish to skip this step.

After the pieces are placed, white (the human player in our program) gets the first move. Any piece that isn't completely surrounded by other pieces (on all of its six sides) can be moved to another stack (but not an empty peg). Every stack moves corresponding to its height, so stacks of height one can move one square, of height two can move two squares, etc. The colour of the top piece on the stack dictates who has control of the stack and only this player can move it. When no more moves can be made the game is over and the heights of the stacks are added up. Whoever has control of the most pieces is the winner.

One final catch: the red pieces are important because if at any time one or more pieces becomes disconnected from a red piece (there is no path of pieces from it to a red piece) then they are removed from the board. This is especially interesting because checking for this condition requires an algorithm very similar to a mark-sweep garbage collector that attempts to tell if there are any references pointing to a chunk of memory or not. If not, the memory can be recollected, just like our disconnected pieces in DVONN are.

Anyways, here is a "screenshot" of the AI kicking my ass maybe 1/3rd the way through the game:

Thinking...

; Evaluation took:
;   5.46 seconds of real time
;   5.144321 seconds of user run time
;   0.204012 seconds of system run time
;   9,255,734,528 CPU cycles
;   [Run times include 0.18 seconds GC run time]
;   0 page faults and
;   79,436,016 bytes consed.
;
-----------------------------------------------------------------
WHITE: 15 points (13 stacks)  <--- TURN
BLACK: 31 points (17 stacks)
-----------------------------------------------------------------
         0     1     2     3     4     5     6     7     8

      9    10    11    12    13    14    15    16    17    18

  19    20    21    22    23    24    25    26    27    28    29

     30    31    32    33    34    35    36    37    38    39

        40    41    42    43    44    45    46    47    48
-----------------------------------------------------------------
-----------------------------------------------------------------
         w2    *     *     b1   r1r    w1    *     *     *

      *     b4    b2    b1    w1    b1    w2    b4    b3    *

   *     b1    w1    b1    w1    b1    w1    b3    b1    *     *

      *     w1    w1    w1    w1    w1   r1r    *     b3    *

         b1    w1    b1    b1   r1r    b2    *     *     *
-----------------------------------------------------------------
WHAT IS WHITE'S MOVE?

The AI is straightforward: An n-ply alpha-beta search with an obvious static evaluation function based on the number of pegs controlled by each player and the height of their stacks. Even though the AI is very simple (Look at it! It is in the file ai.lisp), it is still good enough to play a decent game of DVONN. It almost always beats me. Whether this says more about the power of alpha-beta or about how much I suck at DVONN is uncertain. In any case, it seems alpha-beta works well for this game because there are often very significant yet hard-to-see outcomes only a few turns away. Sometimes half the board can unexpectedly be wiped out because it became disconnected from the DVONN pieces where you weren't watching! Humans often miss outcomes but alpha-beta doesn't.

Anyways, download the game here: dvonn.tar.gz and happy DVONNing!

λ
All material is (C) Doug Hoyte and/or hcsw.org unless otherwise noted or implied. All rights reserved.