1 ----------------------------------------------------------------------
2 Bonanza 6.0 - Client Source Code
3 Kunihito Hoki, May 2011
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 Search() function is modified to ignore moves which receive negative
58 values from Static Exchange Evaluation (SEE) at frontier and
59 pre-frontier nodes. Self-play experiments showed that this modification
60 makes Bonanza slightly stronger. Similar results were also observed in
61 experiments using a shogi program YSS,
62 http://www32.ocn.ne.jp/~yss/horizon.txt. Moreover, the branch cut by
63 means of SEE at frontier nodes can also be found in a chess program,
66 Now Bonanza does Late Move Reduction (LMR) at root nodes, and recursive
67 iterative deepening more often. Self-play experiments showed that these
68 modifications make Bonanza slightly stronger.
70 DFPN searcher is added to the set of Bonanza source codes (dfpn.c,
71 dfpn.h, and dfpnhash.c). You can use the searcher by using 'dfpn'
72 command with a compile option -DDFPN turned on. To make use of the DFPN
73 searcher in ordinary search, use 'dfpn_client' command with a compile
74 option -DDFPN_CLIENT turned on. To provide a proper service to the DFPN
75 client, you also need to use a server script 'src/server/dfpn_server.pl'
76 with one or more DFPN worker(s) connected with 'dfpn connect' command.
77 I am thankful to Dr. A. Nagai for his kind and fruitful advice.
79 Now Bonanza can be a client of parallel searches using cluster computing
80 environment with mnj command. 'src/server/parallel_server.pl' is a
81 server script of root-node parallelizations, and the server can be a
82 client of majority voting cluster computation.
84 Some techniques which increase computational efficiency of Bonanza are
85 reported by E. Ito, http://aleag.cocolog-nifty.com/. In his website,
86 two ideas are shown, i.e., (i) speed up of the computation of the static
87 evaluation function, and (2) use of SSE instructions of Intel processors
88 for bitboard operations. By adopting his ideas to Bonanza, NPS value
89 nearly doubled. This is amazing. To use SSE instructions, specify -DSSE2
90 or -DSSE4 compiler option. I am thankful to Mr. E. Ito for his kind and
93 -DINANIWA_SHIFT compilation flag is supplied to enable an Inaniwa-strategy detection
95 There are many other modifications and bug fixes.
100 - Some results from Y. Sato's experiments with Bonanza inspired me
101 to use the history table in LMR in Shogi, as Fruit did in chess. By
102 doing so, some improvement in performance of the tree search is
105 - From private communications with Yaneurao, it turned out that the
106 3-ply-mate detections in 'mate3.c' can search game trees more
107 efficiently by using several heuristic pruning techniques. Now
108 'mate3.c' adopts some of these techniques.
110 - E. Ito kindly reported two bugs in the source codes. One is in
111 hash_store(), and the other is in ehash_probe() and
112 ehash_store(). Now these are fixed.
114 - The structure of history table is modified from 'square-to' and
115 'square-from' method to an exact match method by using the perfect
116 hash technique. The hash function of moves in 'phash.c' is generated
117 by codes at http://burtleburtle.net/bob/hash/perfect.html.
119 - A command 'mnj' is added to connect to the cluster-computing server
122 - In client_next_game(), the way of dealing with REJECT message from a
123 CSA Shogi server is revised. Now Bonanza connects to the server again
124 when the game is rejected by an opponent.
128 - The owner of 'LS3600 Blog Webpage' pointed out that there were two
129 serious bugs. Thank you very much! According to his indication,
130 is_hand_eq_supe() in 'utility.c' and read_CSA_line() in 'csa.c' are
132 - In MPV code in 'searchr.c', a test of 'root_abort' flag had been
133 forgotten. Now the flag is tested after every call of search().
134 - 'lan.txt' is added to 'src/executable/' directory. This is an
135 example of an input sequence to connect to CSA Shogi server.
136 - 'book.bin' now has smaller moves and positions than previous one does.
137 Also, 'book_anti.csa' is added to 'src/executable/' directory. This
138 is an example of bad moves which apear in records of human experts.
139 - 'Legal Notices' in this document is corrected.
142 - In 'Makefile' and 'Makefile.vs', targets which require profile-guided
143 optimization are removed. Furthermore, an option, which controls
144 optimization, has been reverted from the aggressive flag, -O3, to a
145 moderate one, '-O2'. These modifications were necessary for avoiding
146 abnormal terminations of the program.
147 - In 'ini.c', the attribute of POSIX thread in a global-variable
148 'pthread_attr' is set to 'detach-state'. Because threads will never
149 join with any other threads in this program, the thread should be
150 created in the detached state to free system resources.
151 - In 'ini.c', the default size of the transposition table is lifted
152 from 12MByte to 48MByte.
153 - In 'iterate.c", probing the opening book is avoided when the move
154 history of a current game has repetitions.
155 - In 'shogi.h', the margins of futility pruning are increased in
156 accord with new positional evaluation of the feature vector in
158 - The quality of an opening book, 'winbin/book.bin', has been improved
159 at the expense of quantity.
161 Version 4.1.0 and 4.1.1 (26 Apr 2009)
162 - In 'Makefile' and 'Makefile.vs', some options of Intel C compiler
163 are modified. Here, agressive optimization '-O3' is substituted for
164 the default '-O2', pthreads support '-pthread' is substituted for
165 '-lpthread', and an obsolete '-static-libcxx' is removed.
166 - In 'Makefile', the conformance of GNU C and Intel C compilers are
167 set to GNU extensions of ISO C99 by setting '-std=gnu99' because a
168 POSIX function 'strtok_r()' is not in the C99 standard library.
169 - In 'Makefile', targets for GNU C with gprof and profile-guided
170 optimization of GNU C are removed.
171 - In 'shogi.h', inline assemblies and intrinsics are used on x86-64 as
172 well as x86. To detect the targets, pre-defined macros '__i386__'
173 and '__x86_64__' are examined.
174 - In 'evaluate.c', the evaluation function looks up the table
175 'stand_pat[ply]' to see if the position have been evaluated since
176 the previous move is made by 'make_move_[bw]()' functions. Also, the
177 evaluation function probes the hash table 'ehash_tbl[]' to avoid
178 re-evaluation of the same position.
179 - In 'io.c', an immediate value 0 is substituted for 'fileno(stdin)'
180 because the POSIX function 'fileno()' is not part of ANSI C. POSIX
181 requires that the file descriptor associated with 'stdin' be 0.
182 - In 'iterate.c', a criterion for aging of transposition-table, i.e.,
183 increment of a global variable 'trans_table_age', is lifted from 7%
184 to 9% of saturation ratio of the table.
185 - In 'learn1.c', the macro 'SEARCH_DEPTH' is set to 2. The macro
186 specifies the depth threashold of searches for finding all of
187 principle variations of positions in a set of games.
188 - In 'learn1.c', a step size of increment/decrement of feature vectors
189 is fixed to 1 in 'learn_parse2()' function.
190 - In 'hash.c', when a node can be pruned by using a hash value based on
191 futility pruning, a return value of the node is set to beta.
192 - In 'rand.c', some codes of initialization of PRNG variables are
193 moved to 'ini_genrand()' from 'ini()' function.
194 - In 'sckt.c', a function 'send_crlf()' is removed.
195 - In 'search.c', now 'search()' calls 'search_quies()' and returns if
196 a search depth reaches a threashold. So that we can call 'search()'
197 function anytime, and this makes source codes simple.
198 - In 'search.c', the static evaluation value is evaluated and used to
199 see if the late-move reduction is applicable or not. The evaluation
200 value is also used by the futility pruning.
201 - In 'search.c', the futility pruning is not applied if the node is in
202 check or the move is a check.
203 - In 'search.c', now Bonanza sends the keep-alive command '0x0a' to
204 the server in 'detect_signals()'.
205 - In 'time.c', 'set_seach_limit_time()' is simplified.
206 - In 'time.c', the second argument of 'gettimeofday()' is set to 'NULL'.
208 Version 4.0.4 (2 Feb 2009)
209 - An error of GCC inline assembly for spinlock in "thread.c" is fixed.
210 - In Windows OS, Bonanza now opens all streams with file sharing by
211 using "_SH_DENYNO" constant in "io.c".
212 - GCC built-in functions are substituted for GCC inline assemblies for
213 bit-scan operations in "bitop.h". Furthermore, "bitop.h" is removed,
214 and some of macros in the header are integrated into "shogi.h".
216 Version 4.0.3 (Jan 2008)
222 Here is a list of files you can find in this directory.
225 - param.h piece values
226 - shogi.h main header
227 - bitop.h bit operations
228 - dfpn.h header of DFPN codes
231 - main.c main function of C program
232 - data.c definition of global variables
233 - ini.c initializations
234 - rand.c pseudo random number generator
235 - time.c time functions
236 - bitop.c bit operations
237 - utility.c misc. functions
240 - proce.c input procedures
241 - csa.c csa file format I/O
243 - sckt.c Socket communications
245 bitboard manipulations
246 - attack.c piece attacks
247 - genchk.c move generation (checks)
248 - genevasn.c move generation (evasions)
249 - gendrop.c move generation (drops)
250 - gennocap.c move generation (non-captures)
251 - gencap.c move generation (captures)
252 - movgenex.c move generation (inferior moves)
253 - makemove.c make moves
254 - unmake.c unmake move
255 - mate1ply.c 1-ply mate detection
256 - debug.c examine bitboard validity
259 - iterate.c iterative deepning search at root node
260 - searchr.c alpha-beta search at root node
261 - search.c alpha-beta search
262 - next.c obtains next move
263 - quiesrch.c quiescence search
264 - evaluate.c static eveluation function
265 - evaldiff.c easy and fast evaluation function
266 - swap.c static exchange evaluation
267 - hash.c transposition table
268 - phash.c perfect hash function of moves
269 - thread.c thread-level parallelization
270 - root.c root move genelation and shallow min-max search
271 - mate3.c 3-ply mate detection
273 - book.c creates and probes opening book
274 - problem.c auto problem solver
275 - valid.c examine move validity
279 - dfpnhash.c Hashing for DFPN search
281 optimal control of min-max search
282 - learn1.c main functions
283 - learn2.c feture vector manipuration
286 - bonanza.txt which now you are looking at
287 - Makefile makefile for gnu make.exe
288 - Makefile.vs makefile for Microsoft nmake.exe
289 - bonanza.ico icon file for windows
290 - bonanza.rc resource-definition file for windows
291 - lan.txt example of input sequence to connect CSA Shogi server
292 - book_anti.csa example of a set of bad moves which apear in records
293 of human exparts. This is used by 'book create' command.
295 4. How to build Bonanza
296 -----------------------
298 You can build Bonanza by means of GNU Make on Linux or Microsoft NMAKE
299 on Windows. Here is some examples:
302 > make -f Makefile gcc
304 - Intel C++ Compiler on Linux
305 > make -f Makefile icc
307 - Microsoft C/C++ Compiler on Windows
308 > nmake -f Makefile.vs cl
310 - Intel C++ Compiler on Windows
311 > nmake -f Makefile.vs icl
313 The C source codes are written by using ANSI C plus a small number of
314 new features in ISO C99. Therefore, I think this can be easily built
315 in many platforms without much effort.
317 It may be necessary to define some macros in Makefile or
318 Makefile.vs. The macros are:
320 - NDEBUG (DEBUG) builds release (debug) version of Bonanza
322 - MINIMUM disables some auxiliary functions that are not
323 necessary to play a game, e.g., book composition
324 and optimization of evaluation functions
326 - TLP enables thread-level parallel search
328 - MPV enables multi-PV search
330 - CSA_LAN enables Bonanza to communicate by CSA Shogi TCP/IP
333 - DEKUNOBOU enables dekunobou interface (available only for
336 - CSASHOGI builds an engine for CSA Shogi (available only for
339 - NO_LOGGING suppresses dumping log files
341 - HAVE_SSE2 use SSE2 instructions for speed
343 - HAVE_SSE4 use SSE2 and SSE4.1 instructions for speed
345 - MNJ_LAN enables a client-mode of cluster searches
347 - INANIWA_SHIFT enables an Inaniwa strategy detection
349 - DFPN build the DFPN worker of mate-problems server
351 - DFPN_CLIENT enables the client-mode of mate-problem server
354 Bonanza is an application that does not provide graphical user
355 interface. If you could build "bonanza.exe" properly without CSASHOGI
356 macro, it shows a prompt "Black 1>" when you execute it at a computer
359 Bonanza uses three binary files: a feature vector of static evaluation
360 function "fv.bin", an opening book "book.bin", and a
361 position-learning database "hash.bin". You can find these in "winbin/"
362 directory. Without the NO_LOGGING option, Bonanza must find "log/"
363 directory to dump log files.
370 Starts to ponder on the current position, until a command is
371 received. After a 'move', 'undo' command pondering will continue
372 in the new position, while 'excdude', 'include' and 'mpv' will
373 continue analysis of the same position in the new mode. To get out
374 of this mode without side effects, you can use the 'exit' command.
378 These commands enable (on) or disable (off) a beep when Bonanza
379 makes a move. The default is on.
383 These commands enable (on) or disable (off) to probe the opening
384 book, "./book.bin". The default is on.
388 When the command with "narrow" is used, Bonanza selects a book
389 move from a small set of opening moves. The default is "wide". The
390 narrowing of the opening moves is useful if you want Bonanza
391 choose a common opening line.
394 This command creates the opening book file, "./book.bin", by using
395 numerous experts' games in a single CSA record file, "./book.csa".
396 It also uses another CSA record file, "book_anti.csa", where you
397 can register bad moves that may appear in the experts' games at
398 the last moves in the record file. Here is the example:
400 ----------------------------------------
401 PI, +, +6978KI, %TORYO
403 PI, +, +6978KI, -8384FU, %TORYO
405 PI, +, +7776FU, -4132KI, %TORYO
407 PI, +, +7776FU, -4132KI, +2726FU, %TORYO
408 ----------------------------------------
410 This command becomes effective when MINIMUM macro is not defined
413 - connect 'addr' 'port' 'id' 'passwd' ['ngame']
414 This command connects Bonanza to a shogi server by using the CSA
415 protocol. The first four arguments specify the network address,
416 port number, user ID, and password, respectively. The last
417 argument limits a number of games that will be played by Bonanza.
418 This command becomes effective when CSA_LAN macro is defined in
422 Bonanza does DFPN search at a current position.
425 This command is used to initialize the transposition table of
426 DFPN search and set the size of the table to 2^'num'. This
427 command becomes effective when DFPN macro is defined in the
430 - dfpn connect 'hostname' 'port#' 'ID'
431 This command is used to connect to the server script
432 dfpn_server.pl as a worker. This command becomes effective when
433 DFPN macro is defined in the Makefile.
435 - dfpn_client 'hostname' 'port#'
436 This command is used to connect to the server script
437 dfpn_server.pl as a client. With this, a root and its child
438 posittions are examined by the DFPN worker(s). This command
439 becomes effective when DFPN_CLIENT macro is defined in the
444 The move 'str' will be excluded from search in the current
445 position, or included again. The list of excluded move will
446 be cleared as soon as we alter the position by the move, undo,
450 This command prints the shogi board. If you want to flip the
451 board, set 'num' to 2. If not, set it to 1.
454 Bonanza makes a prompt reply while thinking as soon as this
458 This command is used to initialize the transposition table and
459 set the size of the table to 2^'num'.
462 This command is used to make a zero-filled position-lerning
463 database, "hash.bin". This command becomes effective when MINIMUM
464 macro is not defined in the Makefile.
468 These commands enable (on) or disable (off) the position learning.
471 - learn 'str' 'steps' ['games' ['iterations' ['num1' ['num2']]]]
472 This command optimizes a feature vector of the static evaluation
473 function by using numorous experts' games in a single CSA record
474 file, "./records.csa". If you want to use a zero-filled vector as
475 an initial guess of the optimization procedure, set 'str' to
476 "ini". If not, set it to "no-ini". The third argument 'games' is a
477 number of games to be read from the record file. If the third
478 argument is negative or omitted, all games are read from the file.
480 The learning method iterates a set of procedures, and the number
481 of iteration can be limited by the fourth argument. It continues
482 as long as the argument is negative. The procedures consist of two
483 parts. The first part reads the record file and creates principal
484 variations by using 'num1' threads. The default value of 'num1' is
485 1. The second part renews the feature vector 'steps' times by using
486 'num2' threads in accord with the principal variations. The default
487 value of 'steps' and 'num2' is 1. Note that each thread in the
488 second procedure uses about 500MByte of the main memory. The two
489 arguments 'num1' and 'num2' become effective when TLP macro is
490 defined in the Makefile. After the procedures, the optimized
491 vector is saved in "./fv.bin". This command become effective when
492 MINIMUM macro is not defined in the Makefile.
495 This command is used to specify a depth, 'num', at which Bonanza
496 ends the iterative deepening search.
499 When this command is used, Bonanza stops thinking after searched
500 nodes reach to 'num'.
502 - limit time 'minute' 'second' ['depth']
503 This command limits thinking time of Bonanza. It tries to make
504 each move by consuming the time 'minute'. When the time is spent
505 all, it makes each move in 'second'. The last argument 'depth' can
506 be used if you want Bonanza to stop thinking after the iterative
507 deepening searches reach sufficient depth.
509 - limit time extendable
511 The command, "limit time extendable", allows Bonanza to think
512 longer than the time limited by the previous command if it wishes
513 to. The default is "strict".
515 - mnj 'sd' 'seed' 'addr' 'port' 'id' 'factor' 'stable_depth'
516 This command connects Bonanza to the majority or parallel server in
517 src/server/. The first two integers specify the standard
518 deviation and initial seed of pseudo-random numbers which are
519 added to the static evaluation function. Experiments suggested
520 that an appropriate value for the standard deviation is 15. Note
521 that all clients should use different seeds. The following three
522 arguments are network address, port number, user ID,
523 respectively. You can specify factor as a voting weight. Also
524 stable_depth is useful to detect opening positions. Here, when
525 Bonanza reaches the specified depth, then this is reported to the
526 server to reduce thinking time. This command becomes effective
527 when MNJ_LAN macro is defined in the Makefile.
530 Bonanza makes a move of 'str'. If the argument is omitted, Bonanza
531 thinks of its next move by itself.
534 - mpv width 'threshold'
535 These commands control the number of root moves, 'nroot', to
536 constitute principal variations. The default number is 1. A root
537 move that yields a smaller value than the best value by 'threshold'
538 is neglected. The default threshold is about 200. These commands
539 become effective when MPV macro is defined in the Makefile.
542 This command initializes the shogi board. The argument 'str'
543 controls an initial configuration of the board. If you want to
544 play a no-handicapped game, set 'str' to "PI" and this is the
545 default value. In a handicapped game, specify squares and pieces
546 to drop, e.g. "new PI82HI22KA" or "new PI19KY".
550 The command "peek on (off)" enables (disables) peeks at a buffer
551 of the standard input file while Bonanza is thinking. The default
552 is on. This command is useful when you want to process a set of
553 commands as "> ./bonanza.exe < infile".
556 Prompt Bonanza to print "pong".
560 The command "ponder on (off)" enables (disables) thinks on the
561 opponent's time. The default is on.
564 This command is used to solve problems in "./problem.csa". Here
565 is an example of the problem file.
567 -----------------------------
569 P1-KY-KE-OU-KI * * * * -KY
570 P2 * * * * * -KI * * *
571 P3 * * -FU-GI-FU * -KE * -KA
572 P4-FU * * -FU-GI-FU-HI * -FU
573 P5 * * * * * * * -FU+KY
574 P6+FU+KA+FU+FU+GI+FU+KI * *
575 P7 * +FU * * +FU * * * *
576 P8 * +OU+KI+GI * * +HI * *
577 P9+KY+KE * * * * * +KE *
582 $ANSWER:+0087KY:+0088KY
583 P1-OU-KE * * * * * +GI *
584 P2-KY-KI * * * * * * *
585 P3-FU-HI * -KI * * -GI * *
586 P4 * * -KE * * * * * -FU
587 P5 * +GI * -FU-FU-FU-FU-FU *
588 P6+FU+HI-FU * * * * * *
589 P7 * * * +FU * * * * +FU
590 P8 * * +OU+KI+KI * * * *
591 P9+KY+KE * * * * * +KE+KY
592 P+00KA00GI00KY00FU00FU
593 P-00KA00FU00FU00FU00FU00FU
595 -----------------------------
597 The argument 'num' specifies the number of problems to solve.
600 The quit command and EOF character will exit Bonanza.
602 - read 'filename' [(t|nil) ['num']]
603 This command is used to read a CSA record 'filename' up to 'num'
604 moves. Set the second argument to "nil" when you want to ignore
605 time information in the record. The default value is "t". Bonanza
606 reads all move sequence if the last argument is neglected. If
607 'filename' is ".", the command reads an ongoing game from the
611 Use this command when you resign a game.
614 This command specifies the threshold to resign. 'num' is a value
615 of the threshold. The default is around 1000.
619 When the command "stress on" is used, last-move shown in shogi
620 board is stressed. The default is on.
622 - time remain 'num1' 'num2'
623 This command tells Bonanza the remaining time. 'num1' ('num2') is
624 the remaining time of black (white) in seconds.
626 - time response 'num'
627 This command specifies a margin to control time. The time margin
628 saves Bonanza from time up due to TCP/IP communication to a server
629 program, sudden disc access, or imperfection of time control of
630 Bonanza. 'num' is the time margin in milli-second. The default
634 This command controls the number of threads to be created when
635 Bonana considers a move to make. The command becomes effective
636 when TLP macro is defined in the Makefile. 'num' is the number of
637 threads. The default value is 1.
640 This command causes the latest move to be taken back.
643 A line beginning with # causes all characters on that line
647 A move command consists of four digits followed by two
648 capital alphabets, e.g. 7776FU. The first two digits
649 are a starting square and the last two are a target square. The
650 starting square is "OO" if the move is a dorp, e.g. 0087FU. The
651 following two alphabets specify a piece type as the following,
653 FU - pawn (Fuhyo) TO - promoted pawn (Tokin)
654 KY - lance (Kyousha) NY - promoted lance (Narikyo)
655 KE - knight (Keima) NK - promoted knight (Narikei)
656 GI - silver general (Ginsho) NG - promoted silver (Narigin)
657 KI - gold general (Kinsyo)
658 KA - Bishop (Kakugyo) UM - Dragon horse (Ryuma)
659 HI - Rook (Hisha) RY - Dragon king (Ryuo)
662 Here, words in parentheses are romanization of Japanese words.