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