1 ----------------------------------------------------------------------
2 Bonanza Feliz 0.0 - Executable Source Code
3 Kunihito Hoki, 1 Apr 2010
4 ----------------------------------------------------------------------
10 Bonanza is a state-of-the art computer shogi engine which runs on
11 Windows and Linux machines, and this directory contains a
12 platform-independent source code.
14 This source code is distributed with a hope that it will be useful in
15 addition to the main part of the shogi engine. This program includes
16 many useful functions such as manipulating a shogi board, reading and
17 writing a CSA record file, speaking of a CSA protocol with a socket
18 communication, and controlling time, and etc.. I believe this program
19 can be a good starting point if you are interested in making shogi
22 One main feature of this program is that it employs a brute-force
23 search method together with bitboard techniques as many chess programs
24 do. Another notable feature is a machine learning of shogi evaluation
25 functions. The details of the learning algorithm (aka Bonanza method)
26 were already presented [1], and this source code provides an example
27 of implementation of the learning method.
29 I admit that some parts of the source code are cryptic, e.g. codes in
30 "mate1ply.c". I hope that I will have some time to make a quality
31 documentation and comments on the program code, or someone else could
32 decrypt my program and provide a documentation.
34 Any comments or suggestions are welcome [2].
36 [1] K. Hoki, "Optimal control of minimax search results to learn
37 positional evaluation", Game Programming Workshop, Hakone, Japan
40 [2] Contact to "bonanza_query [at] hotmail.com".
46 This program is protected by copyright. Without a specific
47 permission, any means of commercial applications are prohibited.
48 Furthermore, this program is distributed without any warranty.
49 Within these limits, you can use, redistribute, and/or modify it.
57 - Some results from Y. Sato's experiments with Bonanza inspired me
58 to use the history table in LMR in Shogi, as Fruit did in chess. By
59 doing so, some improvement in performance of the tree search is
62 - From private communications with Yaneurao, it turned out that the
63 3-ply-mate detections in 'mate3.c' can search game trees more
64 efficiently by using several heuristic pruning techniques. Now
65 'mate3.c' adopts some of these techniques.
67 - E. Ito kindly reported two bugs in the source codes. One is in
68 hash_store(), and the other is in ehash_probe() and
69 ehash_store(). Now these are fixed.
71 - The structure of history table is modified from 'square-to' and
72 'square-from' method to an exact match method by using the perfect
73 hash technique. The hash function of moves in 'phash.c' is generated
74 by codes at http://burtleburtle.net/bob/hash/perfect.html.
76 - A command 'mnj' is added to connect to the cluster-computing server
79 - In client_next_game(), the way of dealing with REJECT message from a
80 CSA Shogi server is revised. Now Bonanza connects to the server again
81 when the game is rejected by an opponent.
85 - The owner of 'LS3600 Blog Webpage' pointed out that there were two
86 serious bugs. Thank you very much! According to his indication,
87 is_hand_eq_supe() in 'utility.c' and read_CSA_line() in 'csa.c' are
89 - In MPV code in 'searchr.c', a test of 'root_abort' flag had been
90 forgotten. Now the flag is tested after every call of search().
91 - 'lan.txt' is added to 'src/executable/' directory. This is an
92 example of an input sequence to connect to CSA Shogi server.
93 - 'book.bin' now has smaller moves and positions than previous one does.
94 Also, 'book_anti.csa' is added to 'src/executable/' directory. This
95 is an example of bad moves which apear in records of human experts.
96 - 'Legal Notices' in this document is corrected.
99 - In 'Makefile' and 'Makefile.vs', targets which require profile-guided
100 optimization are removed. Furthermore, an option, which controls
101 optimization, has been reverted from the aggressive flag, -O3, to a
102 moderate one, '-O2'. These modifications were necessary for avoiding
103 abnormal terminations of the program.
104 - In 'ini.c', the attribute of POSIX thread in a global-variable
105 'pthread_attr' is set to 'detach-state'. Because threads will never
106 join with any other threads in this program, the thread should be
107 created in the detached state to free system resources.
108 - In 'ini.c', the default size of the transposition table is lifted
109 from 12MByte to 48MByte.
110 - In 'iterate.c", probing the opening book is avoided when the move
111 history of a current game has repetitions.
112 - In 'shogi.h', the margins of futility pruning are increased in
113 accord with new positional evaluation of the feature vector in
115 - The quality of an opening book, 'winbin/book.bin', has been improved
116 at the expense of quantity.
118 Version 4.1.0 and 4.1.1 (26 Apr 2009)
119 - In 'Makefile' and 'Makefile.vs', some options of Intel C compiler
120 are modified. Here, agressive optimization '-O3' is substituted for
121 the default '-O2', pthreads support '-pthread' is substituted for
122 '-lpthread', and an obsolete '-static-libcxx' is removed.
123 - In 'Makefile', the conformance of GNU C and Intel C compilers are
124 set to GNU extensions of ISO C99 by setting '-std=gnu99' because a
125 POSIX function 'strtok_r()' is not in the C99 standard library.
126 - In 'Makefile', targets for GNU C with gprof and profile-guided
127 optimization of GNU C are removed.
128 - In 'shogi.h', inline assemblies and intrinsics are used on x86-64 as
129 well as x86. To detect the targets, pre-defined macros '__i386__'
130 and '__x86_64__' are examined.
131 - In 'evaluate.c', the evaluation function looks up the table
132 'stand_pat[ply]' to see if the position have been evaluated since
133 the previous move is made by 'make_move_[bw]()' functions. Also, the
134 evaluation function probes the hash table 'ehash_tbl[]' to avoid
135 re-evaluation of the same position.
136 - In 'io.c', an immediate value 0 is substituted for 'fileno(stdin)'
137 because the POSIX function 'fileno()' is not part of ANSI C. POSIX
138 requires that the file descriptor associated with 'stdin' be 0.
139 - In 'iterate.c', a criterion for aging of transposition-table, i.e.,
140 increment of a global variable 'trans_table_age', is lifted from 7%
141 to 9% of saturation ratio of the table.
142 - In 'learn1.c', the macro 'SEARCH_DEPTH' is set to 2. The macro
143 specifies the depth threashold of searches for finding all of
144 principle variations of positions in a set of games.
145 - In 'learn1.c', a step size of increment/decrement of feature vectors
146 is fixed to 1 in 'learn_parse2()' function.
147 - In 'hash.c', when a node can be pruned by using a hash value based on
148 futility pruning, a return value of the node is set to beta.
149 - In 'rand.c', some codes of initialization of PRNG variables are
150 moved to 'ini_genrand()' from 'ini()' function.
151 - In 'sckt.c', a function 'send_crlf()' is removed.
152 - In 'search.c', now 'search()' calls 'search_quies()' and returns if
153 a search depth reaches a threashold. So that we can call 'search()'
154 function anytime, and this makes source codes simple.
155 - In 'search.c', the static evaluation value is evaluated and used to
156 see if the late-move reduction is applicable or not. The evaluation
157 value is also used by the futility pruning.
158 - In 'search.c', the futility pruning is not applied if the node is in
159 check or the move is a check.
160 - In 'search.c', now Bonanza sends the keep-alive command '0x0a' to
161 the server in 'detect_signals()'.
162 - In 'time.c', 'set_seach_limit_time()' is simplified.
163 - In 'time.c', the second argument of 'gettimeofday()' is set to 'NULL'.
165 Version 4.0.4 (2 Feb 2009)
166 - An error of GCC inline assembly for spinlock in "thread.c" is fixed.
167 - In Windows OS, Bonanza now opens all streams with file sharing by
168 using "_SH_DENYNO" constant in "io.c".
169 - GCC built-in functions are substituted for GCC inline assemblies for
170 bit-scan operations in "bitop.h". Furthermore, "bitop.h" is removed,
171 and some of macros in the header are integrated into "shogi.h".
173 Version 4.0.3 (Jan 2008)
179 Here is a list of files you can find in this directory.
182 - param.h piece values
183 - shogi.h main header
186 - main.c main function of C program
187 - data.c definition of global variables
188 - ini.c initializations
189 - rand.c pseudo random number generator
190 - time.c time functions
191 - bitop.c bit operation
192 - utility.c misc. functions
195 - proce.c input procedure
196 - csa.c csa file format I/O
199 - sckt.c TCP/IP client of CSA SHOGI protocol
201 bitboard manipulations
202 - attack.c piece attacks
203 - genchk.c move generation (checks)
204 - genevasn.c move generation (evasions)
205 - gendrop.c move generation (drops)
206 - gennocap.c move generation (non-captures)
207 - gencap.c move generation (captures)
208 - movgenex.c move generation (inferior moves)
209 - makemove.c make moves
210 - unmake.c unmake move
211 - mate1ply.c 1-ply mate detection
212 - debug.c examine bitboard validity
215 - iterate.c iterative deepning search at root node
216 - searchr.c alpha-beta search at root node
217 - search.c alpha-beta search
218 - next.c obtains next move
219 - quiesrch.c quiescence search
220 - evaluate.c static eveluation function
221 - evaldiff.c easy and fast evaluation function
222 - swap.c static exchange evaluation
223 - hash.c transposition table
224 - thread.c thread-level parallelization
225 - root.c root move genelation and shallow min-max search
226 - mate3.c 3-ply mate detection
228 - book.c creates and probes opening book
229 - problem.c auto problem solver
230 - valid.c examine move validity
232 optimal control of min-max search
233 - learn1.c main functions
234 - learn2.c feture vector manipuration
237 - bonanza.txt which now you are looking at
238 - Makefile makefile for gnu make.exe
239 - Makefile.vs makefile for Microsoft nmake.exe
240 - bonanza.ico icon file for windows
241 - bonanza.rc resource-definition file for windows
242 - lan.txt example of input sequence to connect CSA Shogi server
243 - book_anti.csa example of a set of bad moves which apear in records
244 of human exparts. This is used by 'book create' command.
246 4. How to build Bonanza
247 -----------------------
249 You can build Bonanza by means of GNU Make on Linux or Microsoft NMAKE
250 on Windows. Here is some examples:
253 > make -f Makefile gcc
255 - Intel C++ Compiler on Linux
256 > make -f Makefile icc
258 - Microsoft C/C++ Compiler on Windows
259 > nmake -f Makefile.vs cl
261 - Intel C++ Compiler on Windows
262 > nmake -f Makefile.vs icl
264 The C source codes are written by using ANSI C plus a small number of
265 new features in ISO C99. Therefore, I think this can be easily built
266 in many platforms without much effort.
268 It may be necessary to define some macros in Makefile or
269 Makefile.vs. The macros are:
271 - NDEBUG (DEBUG) builds release (debug) version of Bonanza
273 - MINIMUM disables some auxiliary functions that are not
274 necessary to play a game, e.g., book composition
275 and optimization of evaluation functions
277 - TLP enables thread-level parallel search
279 - MPV enables multi-PV search
281 - CSA_LAN enables Bonanza to communicate by CSA Shogi TCP/IP
284 - DEKUNOBOU enables dekunobou interface (available only for
287 - CSASHOGI builds an engine for CSA Shogi (available only for
290 - NO_LOGGING suppresses dumping log files
292 Bonanza is an application that does not provide graphical user
293 interface. If you could build "bonanza.exe" properly without CSASHOGI
294 macro, it shows a prompt "Black 1>" when you execute it at a computer
297 Bonanza uses three binary files: a feature vector of static evaluation
298 function "fv.bin", an opening book "book.bin", and a
299 position-learning database "hash.bin". You can find these in "winbin/"
300 directory. Without the NO_LOGGING option, Bonanza must find "log/"
301 directory to dump log files.
309 These commands enable (on) or disable (off) a beep when Bonanza
310 makes a move. The default is on.
314 These commands enable (on) or disable (off) to probe the opening
315 book, "./book.bin". The default is on.
319 When the command with "narrow" is used, Bonanza selects a book
320 move from a small set of opening moves. The default is "wide". The
321 narrowing of the opening moves is useful if you want Bonanza
322 choose a common opening line.
325 This command creates the opening book file, "./book.bin", by using
326 numerous experts' games in a single CSA record file, "./book.csa".
327 It also uses another CSA record file, "book_anti.csa", where you
328 can register bad moves that may appear in the experts' games at
329 the last moves in the record file. Here is the example:
331 ----------------------------------------
332 PI, +, +6978KI, %TORYO
334 PI, +, +6978KI, -8384FU, %TORYO
336 PI, +, +7776FU, -4132KI, %TORYO
338 PI, +, +7776FU, -4132KI, +2726FU, %TORYO
339 ----------------------------------------
341 This command becomes effective when MINIMUM macro is not defined
344 - connect 'addr' 'port' 'id' 'passwd' ['ngame']
345 This command connects Bonanza to a shogi server by using the CSA
346 protocol. The first four arguments specify the network address,
347 port number, user ID, and password, respectively. The last
348 argument limits a number of games that will be played by Bonanza.
349 This command becomes effective when CSA_LAN macro is defined in
352 - dekunobou 'addr' 'port-dekunobou' 'port-bonanza'
353 This command connects Bonanza to Dekunobou.
356 This command prints the shogi board. If you want to flip the
357 board, set 'num' to 2. If not, set it to 1.
360 Bonanza makes a prompt reply while thinking as soon as this
364 This command is used to initialize the transposition table and
365 set the size of the table to 2^'num'.
368 This command is used to make a zero-filled position-lerning
369 database, "hash.bin". This command becomes effective when MINIMUM
370 macro is not defined in the Makefile.
374 These commands enable (on) or disable (off) the position learning.
377 - learn 'str' 'steps' ['games' ['iterations' ['num1' ['num2']]]]
378 This command optimizes a feature vector of the static evaluation
379 function by using numorous experts' games in a single CSA record
380 file, "./records.csa". If you want to use a zero-filled vector as
381 an initial guess of the optimization procedure, set 'str' to
382 "ini". If not, set it to "no-ini". The third argument 'games' is a
383 number of games to be read from the record file. If the third
384 argument is negative or omitted, all games are read from the file.
386 The learning method iterates a set of procedures, and the number
387 of iteration can be limited by the fourth argument. It continues
388 as long as the argument is negative. The procedures consist of two
389 parts. The first part reads the record file and creates principal
390 variations by using 'num1' threads. The default value of 'num1' is
391 1. The second part renews the feature vector 'steps' times by using
392 'num2' threads in accord with the principal variations. The default
393 value of 'steps' and 'num2' is 1. Note that each thread in the
394 second procedure uses about 500MByte of the main memory. The two
395 arguments 'num1' and 'num2' become effective when TLP macro is
396 defined in the Makefile. After the procedures, the optimized
397 vector is saved in "./fv.bin". This command become effective when
398 MINIMUM macro is not defined in the Makefile.
401 This command is used to specify a depth, 'num', at which Bonanza
402 ends the iterative deepening search.
405 When this command is used, Bonanza stops thinking after searched
406 nodes reach to 'num'.
408 - limit time 'minute' 'second' ['depth']
409 This command limits thinking time of Bonanza. It tries to make
410 each move by consuming the time 'minute'. When the time is spent
411 all, it makes each move in 'second'. The last argument 'depth' can
412 be used if you want Bonanza to stop thinking after the iterative
413 deepening searches reach sufficient depth.
415 - limit time extendable
417 The command, "limit time extendable", allows Bonanza to think
418 longer than the time limited by the previous command if it wishes
419 to. The default is "strict".
421 - mnj 'sd' 'seed' 'addr' 'port' 'id'
422 This command connects Bonanza to the council server in
423 src/cluster/. The first two integers specify the standard
424 deviation and initial seed of pseudo-random numbers which are
425 added to the static evaluation function. Experiments suggested
426 that an appropriate value for the standard deviation is 50. Note
427 that all clients should use different seeds. The last three
428 arguments are network address, port number, user ID,
429 respectively. This command becomes effective when MNJ_LAN macro is
430 defined in the Makefile.
433 Bonanza makes a move of 'str'. If the argument is omitted, Bonanza
434 thinks of its next move by itself.
437 - mpv width 'threshold'
438 These commands control the number of root moves, 'nroot', to
439 constitute principal variations. The default number is 1. A root
440 move that yields a smaller value than the best value by 'threshold'
441 is neglected. The default threshold is about 200. These commands
442 become effective when MPV macro is defined in the Makefile.
445 This command initializes the shogi board. The argument 'str'
446 controls an initial configuration of the board. If you want to
447 play a no-handicapped game, set 'str' to "PI" and this is the
448 default value. In a handicapped game, specify squares and pieces
449 to drop, e.g. "new PI82HI22KA" or "new PI19KY".
453 The command "peek on (off)" enables (disables) peeks at a buffer
454 of the standard input file while Bonanza is thinking. The default
455 is on. This command is useful when you want to process a set of
456 commands as "> ./bonanza.exe < infile".
459 Prompt Bonanza to print "pong".
463 The command "ponder on (off)" enables (disables) thinks on the
464 opponent's time. The default is on.
467 This command is used to solve problems in "./problem.csa". Here
468 is an example of the problem file.
470 -----------------------------
472 P1-KY-KE-OU-KI * * * * -KY
473 P2 * * * * * -KI * * *
474 P3 * * -FU-GI-FU * -KE * -KA
475 P4-FU * * -FU-GI-FU-HI * -FU
476 P5 * * * * * * * -FU+KY
477 P6+FU+KA+FU+FU+GI+FU+KI * *
478 P7 * +FU * * +FU * * * *
479 P8 * +OU+KI+GI * * +HI * *
480 P9+KY+KE * * * * * +KE *
485 $ANSWER:+0087KY:+0088KY
486 P1-OU-KE * * * * * +GI *
487 P2-KY-KI * * * * * * *
488 P3-FU-HI * -KI * * -GI * *
489 P4 * * -KE * * * * * -FU
490 P5 * +GI * -FU-FU-FU-FU-FU *
491 P6+FU+HI-FU * * * * * *
492 P7 * * * +FU * * * * +FU
493 P8 * * +OU+KI+KI * * * *
494 P9+KY+KE * * * * * +KE+KY
495 P+00KA00GI00KY00FU00FU
496 P-00KA00FU00FU00FU00FU00FU
498 -----------------------------
500 The argument 'num' specifies the number of problems to solve.
503 The quit command and EOF character will exit Bonanza.
505 - read 'filename' [(t|nil) ['num']]
506 This command is used to read a CSA record 'filename' up to 'num'
507 moves. Set the second argument to "nil" when you want to ignore
508 time information in the record. The default value is "t". Bonanza
509 reads all move sequence if the last argument is neglected. If
510 'filename' is ".", the command reads an ongoing game from the
514 Use this command when you resign a game.
517 This command specifies the threshold to resign. 'num' is a value
518 of the threshold. The default is around 1000.
522 When the command "stress on" is used, last-move shown in shogi
523 board is stressed. The default is on.
525 - time remain 'num1' 'num2'
526 This command tells Bonanza the remaining time. 'num1' ('num2') is
527 the remaining time of black (white) in seconds.
529 - time response 'num'
530 This command specifies a margin to control time. The time margin
531 saves Bonanza from time up due to TCP/IP communication to a server
532 program, sudden disc access, or imperfection of time control of
533 Bonanza. 'num' is the time margin in milli-second. The default
537 This command controls the number of threads to be created when
538 Bonana considers a move to make. The command becomes effective
539 when TLP macro is defined in the Makefile. 'num' is the number of
540 threads. The default value is 1.
543 A line beginning with # causes all characters on that line
547 A move command consists of four digits followed by two
548 capital alphabets, e.g. 7776FU. The first two digits
549 are a starting square and the last two are a target square. The
550 starting square is "OO" if the move is a dorp, e.g. 0087FU. The
551 following two alphabets specify a piece type as the following,
553 FU - pawn (Fuhyo) TO - promoted pawn (Tokin)
554 KY - lance (Kyousha) NY - promoted lance (Narikyo)
555 KE - knight (Keima) NK - promoted knight (Narikei)
556 GI - silver general (Ginsho) NG - promoted silver (Narigin)
557 KI - gold general (Kinsyo)
558 KA - Bishop (Kakugyo) UM - Dragon horse (Ryuma)
559 HI - Rook (Hisha) RY - Dragon king (Ryuo)
562 Here, words in parentheses are romanization of Japanese words.
projects / bonanza.git / blob