Logic Programming

Assignment - Hex

Hex is a 2-player alternating move game played on an 11x11 hexagonally-connected board. See below. On each step, one of the players places a colored marker on an open hexagon. The goal of the game is for the a player to form a path of markers of its color connecting one side of the board to the other. The goal of the red player is connect the upper left to the lower right, while the goal of the black player is to connect the upper right to the lower left. The game has the feature that one of the two players must win; there is no possibility of a draw.

Your goal in this assignment is twofold - (1) you need to write a definition for the action of placing a marker on a cell and (2) you need to write a definition for termination (i.e. whether there is a connected line of markers of the same color from one side of the board to another). You should use a representation for board state in which each cell on the board has a unique row and column. (This is a a little tricky given the hexagonal geometry but it is doable.) You should assume that there is a unary relation control that specifies whose turn it is to play, e.g. control(red) means that it is red's turn to play and control(blue) means it is blue's turn to play. You should assume that the only action in the game is specified as an action term of the form place(m,n), where m and n are the row and column of some empty cell. You should assume that termination is represented as the 0-ary relation terminal. You may (and you will probably want to) include other information in your datasets describing states of the game. Your job is to give definitions for place and terminal that are correct and that allow the system to compute state updates and terminal effectively.

Note that, if your state consists of just the placement of markers and control information, it is likely that the computation cost for terminal will become excessive as more markers are placed on the board. (Your definition might even lead to an infinite loops if you are not careful.) The trick to solving this problem is to maintain additional information in your state description. Hint: Minimal spanning trees.