----------------------------------------------------------------------
Bonanza Feliz 0.0 - Executable Source Code
Kunihito Hoki, 1 Apr 2010
----------------------------------------------------------------------
1. Introduction
----------------
Bonanza is a state-of-the art computer shogi engine which runs on
Windows and Linux machines, and this directory contains a
platform-independent source code.
This source code is distributed with a hope that it will be useful in
addition to the main part of the shogi engine. This program includes
many useful functions such as manipulating a shogi board, reading and
writing a CSA record file, speaking of a CSA protocol with a socket
communication, and controlling time, and etc.. I believe this program
can be a good starting point if you are interested in making shogi
programs.
One main feature of this program is that it employs a brute-force
search method together with bitboard techniques as many chess programs
do. Another notable feature is a machine learning of shogi evaluation
functions. The details of the learning algorithm (aka Bonanza method)
were already presented [1], and this source code provides an example
of implementation of the learning method.
I admit that some parts of the source code are cryptic, e.g. codes in
"mate1ply.c". I hope that I will have some time to make a quality
documentation and comments on the program code, or someone else could
decrypt my program and provide a documentation.
Any comments or suggestions are welcome [2].
[1] K. Hoki, "Optimal control of minimax search results to learn
positional evaluation", Game Programming Workshop, Hakone, Japan
2008.
[2] Contact to "bonanza_query [at] hotmail.com".
2. Legal Notices
-----------------
This program is protected by copyright. Without a specific
permission, any means of commercial applications are prohibited.
Furthermore, this program is distributed without any warranty.
Within these limits, you can use, redistribute, and/or modify it.
3. Change Logs
---------------
Feliz 0.0
- Some results from Y. Sato's experiments with Bonanza inspired me
to use the history table in LMR in Shogi, as Fruit did in chess. By
doing so, some improvement in performance of the tree search is
made.
- From private communications with Yaneurao, it turned out that the
3-ply-mate detections in 'mate3.c' can search game trees more
efficiently by using several heuristic pruning techniques. Now
'mate3.c' adopts some of these techniques.
- E. Ito kindly reported two bugs in the source codes. One is in
hash_store(), and the other is in ehash_probe() and
ehash_store(). Now these are fixed.
- The structure of history table is modified from 'square-to' and
'square-from' method to an exact match method by using the perfect
hash technique. The hash function of moves in 'phash.c' is generated
by codes at http://burtleburtle.net/bob/hash/perfect.html.
- A command 'mnj' is added to connect to the cluster-computing server
in src/cluster/.
- In client_next_game(), the way of dealing with REJECT message from a
CSA Shogi server is revised. Now Bonanza connects to the server again
when the game is rejected by an opponent.
Version 4.1.3
- The owner of 'LS3600 Blog Webpage' pointed out that there were two
serious bugs. Thank you very much! According to his indication,
is_hand_eq_supe() in 'utility.c' and read_CSA_line() in 'csa.c' are
revised.
- In MPV code in 'searchr.c', a test of 'root_abort' flag had been
forgotten. Now the flag is tested after every call of search().
- 'lan.txt' is added to 'src/executable/' directory. This is an
example of an input sequence to connect to CSA Shogi server.
- 'book.bin' now has smaller moves and positions than previous one does.
Also, 'book_anti.csa' is added to 'src/executable/' directory. This
is an example of bad moves which apear in records of human experts.
- 'Legal Notices' in this document is corrected.
Version 4.1.2
- In 'Makefile' and 'Makefile.vs', targets which require profile-guided
optimization are removed. Furthermore, an option, which controls
optimization, has been reverted from the aggressive flag, -O3, to a
moderate one, '-O2'. These modifications were necessary for avoiding
abnormal terminations of the program.
- In 'ini.c', the attribute of POSIX thread in a global-variable
'pthread_attr' is set to 'detach-state'. Because threads will never
join with any other threads in this program, the thread should be
created in the detached state to free system resources.
- In 'ini.c', the default size of the transposition table is lifted
from 12MByte to 48MByte.
- In 'iterate.c", probing the opening book is avoided when the move
history of a current game has repetitions.
- In 'shogi.h', the margins of futility pruning are increased in
accord with new positional evaluation of the feature vector in
'fv.bin'.
- The quality of an opening book, 'winbin/book.bin', has been improved
at the expense of quantity.
Version 4.1.0 and 4.1.1 (26 Apr 2009)
- In 'Makefile' and 'Makefile.vs', some options of Intel C compiler
are modified. Here, agressive optimization '-O3' is substituted for
the default '-O2', pthreads support '-pthread' is substituted for
'-lpthread', and an obsolete '-static-libcxx' is removed.
- In 'Makefile', the conformance of GNU C and Intel C compilers are
set to GNU extensions of ISO C99 by setting '-std=gnu99' because a
POSIX function 'strtok_r()' is not in the C99 standard library.
- In 'Makefile', targets for GNU C with gprof and profile-guided
optimization of GNU C are removed.
- In 'shogi.h', inline assemblies and intrinsics are used on x86-64 as
well as x86. To detect the targets, pre-defined macros '__i386__'
and '__x86_64__' are examined.
- In 'evaluate.c', the evaluation function looks up the table
'stand_pat[ply]' to see if the position have been evaluated since
the previous move is made by 'make_move_[bw]()' functions. Also, the
evaluation function probes the hash table 'ehash_tbl[]' to avoid
re-evaluation of the same position.
- In 'io.c', an immediate value 0 is substituted for 'fileno(stdin)'
because the POSIX function 'fileno()' is not part of ANSI C. POSIX
requires that the file descriptor associated with 'stdin' be 0.
- In 'iterate.c', a criterion for aging of transposition-table, i.e.,
increment of a global variable 'trans_table_age', is lifted from 7%
to 9% of saturation ratio of the table.
- In 'learn1.c', the macro 'SEARCH_DEPTH' is set to 2. The macro
specifies the depth threashold of searches for finding all of
principle variations of positions in a set of games.
- In 'learn1.c', a step size of increment/decrement of feature vectors
is fixed to 1 in 'learn_parse2()' function.
- In 'hash.c', when a node can be pruned by using a hash value based on
futility pruning, a return value of the node is set to beta.
- In 'rand.c', some codes of initialization of PRNG variables are
moved to 'ini_genrand()' from 'ini()' function.
- In 'sckt.c', a function 'send_crlf()' is removed.
- In 'search.c', now 'search()' calls 'search_quies()' and returns if
a search depth reaches a threashold. So that we can call 'search()'
function anytime, and this makes source codes simple.
- In 'search.c', the static evaluation value is evaluated and used to
see if the late-move reduction is applicable or not. The evaluation
value is also used by the futility pruning.
- In 'search.c', the futility pruning is not applied if the node is in
check or the move is a check.
- In 'search.c', now Bonanza sends the keep-alive command '0x0a' to
the server in 'detect_signals()'.
- In 'time.c', 'set_seach_limit_time()' is simplified.
- In 'time.c', the second argument of 'gettimeofday()' is set to 'NULL'.
Version 4.0.4 (2 Feb 2009)
- An error of GCC inline assembly for spinlock in "thread.c" is fixed.
- In Windows OS, Bonanza now opens all streams with file sharing by
using "_SH_DENYNO" constant in "io.c".
- GCC built-in functions are substituted for GCC inline assemblies for
bit-scan operations in "bitop.h". Furthermore, "bitop.h" is removed,
and some of macros in the header are integrated into "shogi.h".
Version 4.0.3 (Jan 2008)
4. Files
---------
Here is a list of files you can find in this directory.
C headers
- param.h piece values
- shogi.h main header
basic C functions
- main.c main function of C program
- data.c definition of global variables
- ini.c initializations
- rand.c pseudo random number generator
- time.c time functions
- bitop.c bit operation
- utility.c misc. functions
I/O
- proce.c input procedure
- csa.c csa file format I/O
- io.c basic I/O
- dek.c dekunobou
- sckt.c TCP/IP client of CSA SHOGI protocol
bitboard manipulations
- attack.c piece attacks
- genchk.c move generation (checks)
- genevasn.c move generation (evasions)
- gendrop.c move generation (drops)
- gennocap.c move generation (non-captures)
- gencap.c move generation (captures)
- movgenex.c move generation (inferior moves)
- makemove.c make moves
- unmake.c unmake move
- mate1ply.c 1-ply mate detection
- debug.c examine bitboard validity
brute-force search
- iterate.c iterative deepning search at root node
- searchr.c alpha-beta search at root node
- search.c alpha-beta search
- next.c obtains next move
- quiesrch.c quiescence search
- evaluate.c static eveluation function
- evaldiff.c easy and fast evaluation function
- swap.c static exchange evaluation
- hash.c transposition table
- thread.c thread-level parallelization
- root.c root move genelation and shallow min-max search
- mate3.c 3-ply mate detection
- ponder.c pondering
- book.c creates and probes opening book
- problem.c auto problem solver
- valid.c examine move validity
optimal control of min-max search
- learn1.c main functions
- learn2.c feture vector manipuration
misc.
- bonanza.txt which now you are looking at
- Makefile makefile for gnu make.exe
- Makefile.vs makefile for Microsoft nmake.exe
- bonanza.ico icon file for windows
- bonanza.rc resource-definition file for windows
- lan.txt example of input sequence to connect CSA Shogi server
- book_anti.csa example of a set of bad moves which apear in records
of human exparts. This is used by 'book create' command.
4. How to build Bonanza
-----------------------
You can build Bonanza by means of GNU Make on Linux or Microsoft NMAKE
on Windows. Here is some examples:
- GCC on Linux
> make -f Makefile gcc
- Intel C++ Compiler on Linux
> make -f Makefile icc
- Microsoft C/C++ Compiler on Windows
> nmake -f Makefile.vs cl
- Intel C++ Compiler on Windows
> nmake -f Makefile.vs icl
The C source codes are written by using ANSI C plus a small number of
new features in ISO C99. Therefore, I think this can be easily built
in many platforms without much effort.
It may be necessary to define some macros in Makefile or
Makefile.vs. The macros are:
- NDEBUG (DEBUG) builds release (debug) version of Bonanza
- MINIMUM disables some auxiliary functions that are not
necessary to play a game, e.g., book composition
and optimization of evaluation functions
- TLP enables thread-level parallel search
- MPV enables multi-PV search
- CSA_LAN enables Bonanza to communicate by CSA Shogi TCP/IP
protcol
- DEKUNOBOU enables dekunobou interface (available only for
Windows)
- CSASHOGI builds an engine for CSA Shogi (available only for
Windows)
- NO_LOGGING suppresses dumping log files
Bonanza is an application that does not provide graphical user
interface. If you could build "bonanza.exe" properly without CSASHOGI
macro, it shows a prompt "Black 1>" when you execute it at a computer
console.
Bonanza uses three binary files: a feature vector of static evaluation
function "fv.bin", an opening book "book.bin", and a
position-learning database "hash.bin". You can find these in "winbin/"
directory. Without the NO_LOGGING option, Bonanza must find "log/"
directory to dump log files.
5. Command List
---------------
- analyze
Starts to ponder on the current position, until a command is
received. After a 'move' or 'undo' command pondering will continue
in the new position. To get out of this mode without side effects,
you can use the 'exit' command.
- beep on
- beep off
These commands enable (on) or disable (off) a beep when Bonanza
makes a move. The default is on.
- book on
- book off
These commands enable (on) or disable (off) to probe the opening
book, "./book.bin". The default is on.
- book narrow
- book wide
When the command with "narrow" is used, Bonanza selects a book
move from a small set of opening moves. The default is "wide". The
narrowing of the opening moves is useful if you want Bonanza
choose a common opening line.
- book create
This command creates the opening book file, "./book.bin", by using
numerous experts' games in a single CSA record file, "./book.csa".
It also uses another CSA record file, "book_anti.csa", where you
can register bad moves that may appear in the experts' games at
the last moves in the record file. Here is the example:
----------------------------------------
PI, +, +6978KI, %TORYO
/
PI, +, +6978KI, -8384FU, %TORYO
/
PI, +, +7776FU, -4132KI, %TORYO
/
PI, +, +7776FU, -4132KI, +2726FU, %TORYO
----------------------------------------
This command becomes effective when MINIMUM macro is not defined
in the Makefile.
- connect 'addr' 'port' 'id' 'passwd' ['ngame']
This command connects Bonanza to a shogi server by using the CSA
protocol. The first four arguments specify the network address,
port number, user ID, and password, respectively. The last
argument limits a number of games that will be played by Bonanza.
This command becomes effective when CSA_LAN macro is defined in
the Makefile.
- dekunobou 'addr' 'port-dekunobou' 'port-bonanza'
This command connects Bonanza to Dekunobou.
- display ['num']
This command prints the shogi board. If you want to flip the
board, set 'num' to 2. If not, set it to 1.
- s
Bonanza makes a prompt reply while thinking as soon as this
command is used.
- hash 'num'
This command is used to initialize the transposition table and
set the size of the table to 2^'num'.
- hash learn create
This command is used to make a zero-filled position-lerning
database, "hash.bin". This command becomes effective when MINIMUM
macro is not defined in the Makefile.
- hash learn on
- hash learn off
These commands enable (on) or disable (off) the position learning.
The default is on.
- learn 'str' 'steps' ['games' ['iterations' ['num1' ['num2']]]]
This command optimizes a feature vector of the static evaluation
function by using numorous experts' games in a single CSA record
file, "./records.csa". If you want to use a zero-filled vector as
an initial guess of the optimization procedure, set 'str' to
"ini". If not, set it to "no-ini". The third argument 'games' is a
number of games to be read from the record file. If the third
argument is negative or omitted, all games are read from the file.
The learning method iterates a set of procedures, and the number
of iteration can be limited by the fourth argument. It continues
as long as the argument is negative. The procedures consist of two
parts. The first part reads the record file and creates principal
variations by using 'num1' threads. The default value of 'num1' is
1. The second part renews the feature vector 'steps' times by using
'num2' threads in accord with the principal variations. The default
value of 'steps' and 'num2' is 1. Note that each thread in the
second procedure uses about 500MByte of the main memory. The two
arguments 'num1' and 'num2' become effective when TLP macro is
defined in the Makefile. After the procedures, the optimized
vector is saved in "./fv.bin". This command become effective when
MINIMUM macro is not defined in the Makefile.
- limit depth 'num'
This command is used to specify a depth, 'num', at which Bonanza
ends the iterative deepening search.
- limit nodes 'num'
When this command is used, Bonanza stops thinking after searched
nodes reach to 'num'.
- limit time 'minute' 'second' ['depth']
This command limits thinking time of Bonanza. It tries to make
each move by consuming the time 'minute'. When the time is spent
all, it makes each move in 'second'. The last argument 'depth' can
be used if you want Bonanza to stop thinking after the iterative
deepening searches reach sufficient depth.
- limit time extendable
- limit time strict
The command, "limit time extendable", allows Bonanza to think
longer than the time limited by the previous command if it wishes
to. The default is "strict".
- mnj 'sd' 'seed' 'addr' 'port' 'id'
This command connects Bonanza to the council server in
src/cluster/. The first two integers specify the standard
deviation and initial seed of pseudo-random numbers which are
added to the static evaluation function. Experiments suggested
that an appropriate value for the standard deviation is 50. Note
that all clients should use different seeds. The last three
arguments are network address, port number, user ID,
respectively. This command becomes effective when MNJ_LAN macro is
defined in the Makefile.
- move ['str']
Bonanza makes a move of 'str'. If the argument is omitted, Bonanza
thinks of its next move by itself.
- mpv num 'nroot'
- mpv width 'threshold'
These commands control the number of root moves, 'nroot', to
constitute principal variations. The default number is 1. A root
move that yields a smaller value than the best value by 'threshold'
is neglected. The default threshold is about 200. These commands
become effective when MPV macro is defined in the Makefile.
- new ['str']
This command initializes the shogi board. The argument 'str'
controls an initial configuration of the board. If you want to
play a no-handicapped game, set 'str' to "PI" and this is the
default value. In a handicapped game, specify squares and pieces
to drop, e.g. "new PI82HI22KA" or "new PI19KY".
- peek on
- peek off
The command "peek on (off)" enables (disables) peeks at a buffer
of the standard input file while Bonanza is thinking. The default
is on. This command is useful when you want to process a set of
commands as "> ./bonanza.exe < infile".
- ping
Prompt Bonanza to print "pong".
- ponder on
- ponder off
The command "ponder on (off)" enables (disables) thinks on the
opponent's time. The default is on.
- problem ['num']
This command is used to solve problems in "./problem.csa". Here
is an example of the problem file.
-----------------------------
$ANSWER:+0024FU
P1-KY-KE-OU-KI * * * * -KY
P2 * * * * * -KI * * *
P3 * * -FU-GI-FU * -KE * -KA
P4-FU * * -FU-GI-FU-HI * -FU
P5 * * * * * * * -FU+KY
P6+FU+KA+FU+FU+GI+FU+KI * *
P7 * +FU * * +FU * * * *
P8 * +OU+KI+GI * * +HI * *
P9+KY+KE * * * * * +KE *
P+00FU00FU
P-00FU00FU00FU
+
/
$ANSWER:+0087KY:+0088KY
P1-OU-KE * * * * * +GI *
P2-KY-KI * * * * * * *
P3-FU-HI * -KI * * -GI * *
P4 * * -KE * * * * * -FU
P5 * +GI * -FU-FU-FU-FU-FU *
P6+FU+HI-FU * * * * * *
P7 * * * +FU * * * * +FU
P8 * * +OU+KI+KI * * * *
P9+KY+KE * * * * * +KE+KY
P+00KA00GI00KY00FU00FU
P-00KA00FU00FU00FU00FU00FU
+
-----------------------------
The argument 'num' specifies the number of problems to solve.
- quit
The quit command and EOF character will exit Bonanza.
- read 'filename' [(t|nil) ['num']]
This command is used to read a CSA record 'filename' up to 'num'
moves. Set the second argument to "nil" when you want to ignore
time information in the record. The default value is "t". Bonanza
reads all move sequence if the last argument is neglected. If
'filename' is ".", the command reads an ongoing game from the
initial position.
- resign
Use this command when you resign a game.
- resign 'num'
This command specifies the threshold to resign. 'num' is a value
of the threshold. The default is around 1000.
- stress on
- stress off
When the command "stress on" is used, last-move shown in shogi
board is stressed. The default is on.
- time remain 'num1' 'num2'
This command tells Bonanza the remaining time. 'num1' ('num2') is
the remaining time of black (white) in seconds.
- time response 'num'
This command specifies a margin to control time. The time margin
saves Bonanza from time up due to TCP/IP communication to a server
program, sudden disc access, or imperfection of time control of
Bonanza. 'num' is the time margin in milli-second. The default
value is 200.
- tlp 'num'
This command controls the number of threads to be created when
Bonana considers a move to make. The command becomes effective
when TLP macro is defined in the Makefile. 'num' is the number of
threads. The default value is 1.
- undo
This command causes the latest move to be taken back.
- #
A line beginning with # causes all characters on that line
to be ignored.
- [move command]
A move command consists of four digits followed by two
capital alphabets, e.g. 7776FU. The first two digits
are a starting square and the last two are a target square. The
starting square is "OO" if the move is a dorp, e.g. 0087FU. The
following two alphabets specify a piece type as the following,
FU - pawn (Fuhyo) TO - promoted pawn (Tokin)
KY - lance (Kyousha) NY - promoted lance (Narikyo)
KE - knight (Keima) NK - promoted knight (Narikei)
GI - silver general (Ginsho) NG - promoted silver (Narigin)
KI - gold general (Kinsyo)
KA - Bishop (Kakugyo) UM - Dragon horse (Ryuma)
HI - Rook (Hisha) RY - Dragon king (Ryuo)
OU - King (Osho)
Here, words in parentheses are romanization of Japanese words.