Revision by Raisonance :

This archive is updated with a Ride project adapted to Primer2.

Introduction

5-in-A-Row, also known as GoMoku, is a traditional oriental game played with black and white stones on an 11x11 or 15x15 board.

How to play

The object of the game is to be the first in placing five pieces in a row in any direction. It is a simple game, which is very easy to play. But beginners take a hard time to defeat the computer due to my magic and funny searching strategies. You can modify difficulty level through press button on “Lv:x” button, ‘x’ will change value from 1 to 5 (default 2), 5 means most difficult (Primer will take more time to “thinking” also).

1    Press button when “play” on the top of screen is active.

2         Move the black chess on the chess board, tilt the primer, and choose the cross point which you like.  Pressing button once means one step.

3         Wait for Primer moving white chess. Sometimes it could be longer. Don’t worry, it is not dead.   

4    Go on... till you win or lose.

Design objective

1.        The project is to design a program in which Primer can decide how to reply to human player’s move.

2.        The computer uses the searching strategies such as Alpha-Beta algorithm to search for the best move.

3.        Since the board can have 11x11 lines, also can be extended to 15x15 lines, which introduces a much higher computational complexity, we can’t search the whole game space to find the best move. Instead, we need, as much as we can, to cut-off the search by pruning some branches to reduce the time.

4.        Also, the evaluation function is very important for a good performance since we could only search for up to 5 level depths due to the computational complexity.

Installation

1 Unzip the file. Run add_to_Circle.bat file or run “circle_mgr.exe XXXX.lib L S” in command line.

Or go following steps.

2 Run Raisonance tool> Rid7, Open the project.

3 build, debug and run.

Searching Strategies

The large size (15*15) of the board makes the searching a very tough job. Theoretically, the complexity of a Max-Min searching with a depth of n is O(225*224*...*(225-n+1))~=O(225ⁿ) when n is small. In the interactive game, the human player shouldn’t wait for a long time before the computer can make a decision where to put the chess. So we need to reduce the searching time to a reasonable one while searching as deep as the computer can. One way to do so is cut-off the searching tree by applying the Alpha-Beta algorithm.

Alpha-Beta Searching

A modified version of the Min-Max searching, Alpha-Beta searching is applied in the project to reduce the computational time. The algorithm is quite similar with the general Min-Max algorithm except it prunes the branches of the searching tree if the branch will not provide a "good" choice for Min or Max player in Min-Max algorithm. This algorithm can decrease the computational time substantially.

State Analysis

The states in the game are complicated and subtle. Some looks similar but turn out to have different effect after a few steps. A good program need distinguish these states and assign different importance accordingly.

Common basic states (the case for the white player is similar)

Versions

1.0               (CircleOS1.7)          Feb 14^th, 2008    First attempt.

1.1         Mar. 07, 2008     optimized algorithm, improved operatability and user interface, fixed a little bug in algorithm.

Later                                                      More features to be done.