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.
308 Starts to ponder on the current position, until a command is
309 received. After a 'move' or 'undo' command pondering will continue
310 in the new position. To get out of this mode without side effects,
311 you can use the 'exit' command.
315 These commands enable (on) or disable (off) a beep when Bonanza
316 makes a move. The default is on.
320 These commands enable (on) or disable (off) to probe the opening
321 book, "./book.bin". The default is on.
325 When the command with "narrow" is used, Bonanza selects a book
326 move from a small set of opening moves. The default is "wide". The
327 narrowing of the opening moves is useful if you want Bonanza
328 choose a common opening line.
331 This command creates the opening book file, "./book.bin", by using
332 numerous experts' games in a single CSA record file, "./book.csa".
333 It also uses another CSA record file, "book_anti.csa", where you
334 can register bad moves that may appear in the experts' games at
335 the last moves in the record file. Here is the example:
337 ----------------------------------------
338 PI, +, +6978KI, %TORYO
340 PI, +, +6978KI, -8384FU, %TORYO
342 PI, +, +7776FU, -4132KI, %TORYO
344 PI, +, +7776FU, -4132KI, +2726FU, %TORYO
345 ----------------------------------------
347 This command becomes effective when MINIMUM macro is not defined
350 - connect 'addr' 'port' 'id' 'passwd' ['ngame']
351 This command connects Bonanza to a shogi server by using the CSA
352 protocol. The first four arguments specify the network address,
353 port number, user ID, and password, respectively. The last
354 argument limits a number of games that will be played by Bonanza.
355 This command becomes effective when CSA_LAN macro is defined in
358 - dekunobou 'addr' 'port-dekunobou' 'port-bonanza'
359 This command connects Bonanza to Dekunobou.
362 This command prints the shogi board. If you want to flip the
363 board, set 'num' to 2. If not, set it to 1.
366 Bonanza makes a prompt reply while thinking as soon as this
370 This command is used to initialize the transposition table and
371 set the size of the table to 2^'num'.
374 This command is used to make a zero-filled position-lerning
375 database, "hash.bin". This command becomes effective when MINIMUM
376 macro is not defined in the Makefile.
380 These commands enable (on) or disable (off) the position learning.
383 - learn 'str' 'steps' ['games' ['iterations' ['num1' ['num2']]]]
384 This command optimizes a feature vector of the static evaluation
385 function by using numorous experts' games in a single CSA record
386 file, "./records.csa". If you want to use a zero-filled vector as
387 an initial guess of the optimization procedure, set 'str' to
388 "ini". If not, set it to "no-ini". The third argument 'games' is a
389 number of games to be read from the record file. If the third
390 argument is negative or omitted, all games are read from the file.
392 The learning method iterates a set of procedures, and the number
393 of iteration can be limited by the fourth argument. It continues
394 as long as the argument is negative. The procedures consist of two
395 parts. The first part reads the record file and creates principal
396 variations by using 'num1' threads. The default value of 'num1' is
397 1. The second part renews the feature vector 'steps' times by using
398 'num2' threads in accord with the principal variations. The default
399 value of 'steps' and 'num2' is 1. Note that each thread in the
400 second procedure uses about 500MByte of the main memory. The two
401 arguments 'num1' and 'num2' become effective when TLP macro is
402 defined in the Makefile. After the procedures, the optimized
403 vector is saved in "./fv.bin". This command become effective when
404 MINIMUM macro is not defined in the Makefile.
407 This command is used to specify a depth, 'num', at which Bonanza
408 ends the iterative deepening search.
411 When this command is used, Bonanza stops thinking after searched
412 nodes reach to 'num'.
414 - limit time 'minute' 'second' ['depth']
415 This command limits thinking time of Bonanza. It tries to make
416 each move by consuming the time 'minute'. When the time is spent
417 all, it makes each move in 'second'. The last argument 'depth' can
418 be used if you want Bonanza to stop thinking after the iterative
419 deepening searches reach sufficient depth.
421 - limit time extendable
423 The command, "limit time extendable", allows Bonanza to think
424 longer than the time limited by the previous command if it wishes
425 to. The default is "strict".
427 - mnj 'sd' 'seed' 'addr' 'port' 'id'
428 This command connects Bonanza to the council server in
429 src/cluster/. The first two integers specify the standard
430 deviation and initial seed of pseudo-random numbers which are
431 added to the static evaluation function. Experiments suggested
432 that an appropriate value for the standard deviation is 50. Note
433 that all clients should use different seeds. The last three
434 arguments are network address, port number, user ID,
435 respectively. This command becomes effective when MNJ_LAN macro is
436 defined in the Makefile.
439 Bonanza makes a move of 'str'. If the argument is omitted, Bonanza
440 thinks of its next move by itself.
443 - mpv width 'threshold'
444 These commands control the number of root moves, 'nroot', to
445 constitute principal variations. The default number is 1. A root
446 move that yields a smaller value than the best value by 'threshold'
447 is neglected. The default threshold is about 200. These commands
448 become effective when MPV macro is defined in the Makefile.
451 This command initializes the shogi board. The argument 'str'
452 controls an initial configuration of the board. If you want to
453 play a no-handicapped game, set 'str' to "PI" and this is the
454 default value. In a handicapped game, specify squares and pieces
455 to drop, e.g. "new PI82HI22KA" or "new PI19KY".
459 The command "peek on (off)" enables (disables) peeks at a buffer
460 of the standard input file while Bonanza is thinking. The default
461 is on. This command is useful when you want to process a set of
462 commands as "> ./bonanza.exe < infile".
465 Prompt Bonanza to print "pong".
469 The command "ponder on (off)" enables (disables) thinks on the
470 opponent's time. The default is on.
473 This command is used to solve problems in "./problem.csa". Here
474 is an example of the problem file.
476 -----------------------------
478 P1-KY-KE-OU-KI * * * * -KY
479 P2 * * * * * -KI * * *
480 P3 * * -FU-GI-FU * -KE * -KA
481 P4-FU * * -FU-GI-FU-HI * -FU
482 P5 * * * * * * * -FU+KY
483 P6+FU+KA+FU+FU+GI+FU+KI * *
484 P7 * +FU * * +FU * * * *
485 P8 * +OU+KI+GI * * +HI * *
486 P9+KY+KE * * * * * +KE *
491 $ANSWER:+0087KY:+0088KY
492 P1-OU-KE * * * * * +GI *
493 P2-KY-KI * * * * * * *
494 P3-FU-HI * -KI * * -GI * *
495 P4 * * -KE * * * * * -FU
496 P5 * +GI * -FU-FU-FU-FU-FU *
497 P6+FU+HI-FU * * * * * *
498 P7 * * * +FU * * * * +FU
499 P8 * * +OU+KI+KI * * * *
500 P9+KY+KE * * * * * +KE+KY
501 P+00KA00GI00KY00FU00FU
502 P-00KA00FU00FU00FU00FU00FU
504 -----------------------------
506 The argument 'num' specifies the number of problems to solve.
509 The quit command and EOF character will exit Bonanza.
511 - read 'filename' [(t|nil) ['num']]
512 This command is used to read a CSA record 'filename' up to 'num'
513 moves. Set the second argument to "nil" when you want to ignore
514 time information in the record. The default value is "t". Bonanza
515 reads all move sequence if the last argument is neglected. If
516 'filename' is ".", the command reads an ongoing game from the
520 Use this command when you resign a game.
523 This command specifies the threshold to resign. 'num' is a value
524 of the threshold. The default is around 1000.
528 When the command "stress on" is used, last-move shown in shogi
529 board is stressed. The default is on.
531 - time remain 'num1' 'num2'
532 This command tells Bonanza the remaining time. 'num1' ('num2') is
533 the remaining time of black (white) in seconds.
535 - time response 'num'
536 This command specifies a margin to control time. The time margin
537 saves Bonanza from time up due to TCP/IP communication to a server
538 program, sudden disc access, or imperfection of time control of
539 Bonanza. 'num' is the time margin in milli-second. The default
543 This command controls the number of threads to be created when
544 Bonana considers a move to make. The command becomes effective
545 when TLP macro is defined in the Makefile. 'num' is the number of
546 threads. The default value is 1.
549 This command causes the latest move to be taken back.
552 A line beginning with # causes all characters on that line
556 A move command consists of four digits followed by two
557 capital alphabets, e.g. 7776FU. The first two digits
558 are a starting square and the last two are a target square. The
559 starting square is "OO" if the move is a dorp, e.g. 0087FU. The
560 following two alphabets specify a piece type as the following,
562 FU - pawn (Fuhyo) TO - promoted pawn (Tokin)
563 KY - lance (Kyousha) NY - promoted lance (Narikyo)
564 KE - knight (Keima) NK - promoted knight (Narikei)
565 GI - silver general (Ginsho) NG - promoted silver (Narigin)
566 KI - gold general (Kinsyo)
567 KA - Bishop (Kakugyo) UM - Dragon horse (Ryuma)
568 HI - Rook (Hisha) RY - Dragon king (Ryuo)
571 Here, words in parentheses are romanization of Japanese words.
projects / bonanza.git / blob