CSCI 324 Project #3

Fortress: Minimax and Alpha-Beta Pruning

Date Due: 25 October 2013

Fortress is a turn-based strategy game played on a 6x6 board. Players take turns making move with the white player moving first. The game ends after 21 moves, and the player who controls the most territory wins. Moves are made by either placing a castle on an unoccupied square, or by reinforcing a previously placed castle. Each castle may be reinforced up to twice. A castle initially flies one flag; each time it is reinforced it adds another flag.

Castles “influence” the four squares to their immediate left, right, top, and bottom. The amount of influence on each square is determined by the number of flags the castle is flying. If the castle is flying one flag, it has one influence unit on the surrounding squares; if two flags, it has two units of influence, and so on. To determine who controls a square, the influence from the four adjacent squares it totaled. White castles contribute positive influence, while black castles contribute negative influence. If the total influence on the square is positive, white controls it, but if it is negative, then black controls it.

A castle may be destroyed if the square it is resting on is influenced more by the opponent’s castles than its own. If a castle is resting on a square where the total influence is zero, it is under siege (and in the graphical version, closes its door to indicate this).

At the end of the game after all the moves have been made, the winner is determined by which player has the most squares under its control. This includes squares which contain castles, and squares adjoining castles that are under the influence of that player.

Here are some examples of the rules. Here, negative numbers represent black castles and indicate the number of flags being flown at each one, while positive numbers indicate white castles and their corresponding flags.

	A	B	C	D
Z			-1
Y		-3		3
X	-1	2	1
W			-3

	A	B	C	D
Z	-	Black	Black	White
Y	Black	Black	-	White
X	Destroyed By White	Destroyed By Black	Seige	White
W	Black	Black	Black	Black

For each of the sixteen squares shown above, the influence computations follow:

SQUARE INFLUENCE (square plus adjoining squares, from bottom, counterclockwise)

ZA 0+0+0=0

ZB 0-3-1+0=-4

ZC -1+0+0+0=-1

ZD 0+3-1=2

YA 0-1-3+0=-4

YB -3+2+0+0+0=-1

YC 0+1+3-1-3=0

YD 3+0+0+0=3

XA -1+0+2+0=1

XB 2+0+1-3-1=-1

XC 1-3+0+0+2=0

XD 0+0+3+1=4

WA 0+0-1=-1

WB 0-3+2+0=-1

WC -3+0+1+0=-2

WD 0+0-3=-3

After the two castles are destroyed, Black influences or controls 9 squares, White controls 4 squares, one square is under siege and two others are controlled by neither, so Black would win 9 to 4 if this were the final board position.

The Assignment:

You are to write a program to play Fortress with the computer playing as one of the players. Your program should read a configuration file named fortress.config, which will reside in the same directory as your executable. The config file will contain a single W on the first line if the computer is to play as white, and a single B on the first like if the computer is to play as black. The second line of the config file will contain an integer number that specifies how deep to search the game tree before generating a move. The third line contains a real number that specifies the maximum amount of time in seconds your program may use to determine its move—after that amount of time has passed, it should output the best move it has found so far. Your program should output its moves to standard out using a coordinate scheme, where the upper left square is named A1, with succeeding columns labeled 2 through 6, while following rows are named B through F (thus, the square on the bottom right would be F6). The square specified is the one upon which the computer wants to build a castle or upgrade an already existing castle. After specifying its move, the computer should then read a location from the standard input as the opponent’s move, and upgrade the board accordingly.

Your program should check for incorrect moves (moving to a square already occupied by the opponent, trying to upgrade a castle beyond three flags, etc), and if one is detected, should print an error message to stderr describing the error and then exit. Other informational messages may be printed to standard error as desired. At the end of the game, your program should print out a status message indicating who one (eg, “the computer (Black) wins, 25-7”) and then exit.

Your program should implement the minimax algorithm to search the game tree for the best move, using an evaluation function of your own design. For extra credit, you may add alpha-beta pruning to your search in order to search more efficiently in the allotted time. (Check the book for further details of the minimax algorithm and alpha-beta pruning, or see the Wikipedia article.

Correctly implemented programs will be entered in a single elimination tournament in which each program plays each opponent once as black and once as white. In case this results in a 1-1 draw, a third game will be played where black and white are determined randomly, and the winner of that third game advances to the next round. The winner of the tournament, in addition to bragging rights and accolades from his/her peers, will also receive an additional 10 points on their program grade.

This is an advanced CS course so your program is expected to be written following good style guidelines, and using all the best practices you have learned from your previous courses. For additional credit, ONCE you have the basic functionality implemented, you may also implement a GUI and graphical display IN ADDITION to the text interface described above. Have fun, and good luck!