Username:     
Password:     
             

Contest 2013/2014
Contest 2011
Contest 2009
Contest 2008
Gobang 1.1
 
Gobang, also known as 5-in-A-Row, or GoMoku, is a traditional game. 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 change difficulty level between 1 to 5 any time, 5 means most difficult (Primer will take more time to “thinking” also). Come on, please try to defeat this primer with artificial intelligence.

Code size:22K Author:syin
Source files included:yes Version:1.1
Use circleOS:yes (1.7) Creation date:2008-02-15 07:03:13
Hardware modification:no Modification date:2009-01-22 10:55:31
Based on the STM32 Primer:All
   
Downloads:2329 Views:28004
   
Vote:
Average ratings:3.05/5 (935 rates)

Download:    Gobang-1.1.zip (157 KB)

Description:

 

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(225n) 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)

Four

Live Four

image002

Rush Four

Consecutive Rush Four

image004

Jump Rush Four

image006
image008
image010
image012

Three

Live Three

Consecutive Live Three

image014

Jump Live Three

image016

Sleep Three

Consecutive Sleep Three

image018

Jump Sleep Three

image020
image022

Special Sleep Three

image024
image026
image028
image030

Fake Sleep Three

image032
image034

Double Sleep Three

image036
image038

Two

Live Two

Consecutive Live Two

image040

Jump Live Two I

image042

Jump Live Two II

image044

Sleep Two

Consecutive Sleep Two

image046

Jump Sleep Two I

image048

Jump Sleep Two II

image050

Special Sleep Two

image052

Fake Sleep Two

image054
image056

 

 

 



 

Versions

1.0               (CircleOS1.7)          Feb 14th, 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.