Score Four!
As part of an engineering software design class (ECE 2036) focused on object oriented programming in C++, I introduce students to parallel computing in the context of a simple and fun multithreaded application of combinatorial game theory: the classic game of Score Four.
The rules of the game are simple. It is essentially a 3D version of tic-tac-toe played on a 4 x 4 x 4 grid with gravity turned on. Opponents take turns placing colored beads, one at a time, on any of the 16 pegs which at the time of their move contain less than 4 beads. Once a peg contains 4 beads, that peg is considered full. The first player to achieve 4 beads of his or her color in a row -- either horizontally, vertically or diagonally -- wins.
Once a bead is played, it may never be removed, and each player is subject to Zugzwang, i.e. players are compelled to place a bead on the board each turn. The game ends in a tie if the board is completely full without either player having achieved 4 beads in a row.
In this implementation, a single human player competes against the computer. To make a move, the player must indicate the peg on which he or she wishes to place a bead by entering the bead's coordinates through the keyboard. Rows of pegs are numbered 0 through 3, and columns of pegs are likewise numbered 0 through 3. At the heart of this program is a static board evaluator which assigns a point value to a specific cofiguration of beads on the board. The more positive the result, the more beneficial the board configuration is for the computer. The more negative the result, the more beneficial the board configuration is for the human opponent. At the beginning of the game, the human player may specify the computer's search depth, i.e. how many moves in advance the computer is permitted to "think". A search depth of 0 tells the computer to consider only the immediate benefit of the current move, but not of future moves. The selected move will be the one for which the static board evaluator returns the highest score among the up to 16 possible valid moves each turn. A larger search depth will allow the computer to recursively consider the benefit of all valid permutations of moves, limited only by the specified search depth, according to the minimax algorithm. To mitigate the computational burden, this implementation splits the task of finding the optimal move (among up to 16 options) over 4 cores. The C++ style threads spawned to each of these 4 cores operate independently of one another, and significantly reduce the time required for the computer to make a move, especially at large lookahead depth.
