- make clean && make -j2 ARCH=x86-64 optimize=no debug=yes build && ../tests/signature.sh $benchref
- make clean && make -j2 ARCH=x86-32 optimize=no debug=yes build && ../tests/signature.sh $benchref
- make clean && make -j2 ARCH=x86-32 build && ../tests/signature.sh $benchref
+
+ # Verify bench number is ONE_PLY independent by doubling its value
+ - sed -i'.bak' 's/.*\(ONE_PLY = [0-9]*\),.*/\1 * 2,/g' types.h
- make clean && make -j2 ARCH=x86-64 build && ../tests/signature.sh $benchref
#
# Check perft and reproducible search
#
# Valgrind
#
- - export CXXFLAGS=-O1
+ - export CXXFLAGS="-O1 -fno-inline"
- if [ -x "$(command -v valgrind )" ]; then make clean && make -j2 ARCH=x86-64 debug=yes optimize=no build > /dev/null && ../tests/instrumented.sh --valgrind; fi
- if [ -x "$(command -v valgrind )" ]; then ../tests/instrumented.sh --valgrind-thread; fi
#
Gary Linscott (glinscott)
Aditya (absimaldata)
+Adrian Petrescu (apetresc)
Ajith Chandy Jose (ajithcj)
Alain Savard (Rocky640)
+alayan-stk-2
Alexander Kure
Ali AlZhrani (Cooffe)
Andrew Grant (AndyGrant)
Daylen Yang (daylen)
DiscanX
Eelco de Groot
+Elvin Liu (solarlight2)
erbsenzaehler
Ernesto Gatti
Fabian Beuke (madnight)
-### Overview
+## Overview
[](https://travis-ci.org/official-stockfish/Stockfish)
[](https://ci.appveyor.com/project/mcostalba/stockfish)
-Stockfish is a free UCI chess engine derived from Glaurung 2.1. It is
-not a complete chess program and requires some UCI-compatible GUI
-(e.g. XBoard with PolyGlot, eboard, Arena, Sigma Chess, Shredder, Chess
-Partner or Fritz) in order to be used comfortably. Read the
-documentation for your GUI of choice for information about how to use
+[Stockfish](https://stockfishchess.org) is a free, powerful UCI chess engine
+derived from Glaurung 2.1. It is not a complete chess program and requires a
+UCI-compatible GUI (e.g. XBoard with PolyGlot, Scid, Cute Chess, eboard, Arena,
+Sigma Chess, Shredder, Chess Partner or Fritz) in order to be used comfortably.
+Read the documentation for your GUI of choice for information about how to use
Stockfish with it.
-This version of Stockfish supports up to 512 cores. The engine defaults
-to one search thread, so it is therefore recommended to inspect the value of
-the *Threads* UCI parameter, and to make sure it equals the number of CPU
-cores on your computer.
-This version of Stockfish has support for Syzygybases.
-
-
-### Files
+## Files
This distribution of Stockfish consists of the following files:
* Readme.md, the file you are currently reading.
- * Copying.txt, a text file containing the GNU General Public License.
+ * Copying.txt, a text file containing the GNU General Public License version 3.
* src, a subdirectory containing the full source code, including a Makefile
that can be used to compile Stockfish on Unix-like systems.
-### Syzygybases
+## UCI parameters
+
+Currently, Stockfish has the following UCI options:
+
+ * #### Debug Log File
+ Write all communication to and from the engine into a text file.
+
+ * #### Contempt
+ A positive value for contempt favors middle game positions and avoids draws.
+
+ * #### Analysis Contempt
+ By default, contempt is set to prefer the side to move. Set this option to "White"
+ or "Black" to analyse with contempt for that side, or "Off" to disable contempt.
+
+ * #### Threads
+ The number of CPU threads used for searching a position. For best performance, set
+ this equal to the number of CPU cores available.
+
+ * #### Hash
+ The size of the hash table in MB.
+
+ * #### Clear Hash
+ Clear the hash table.
+
+ * #### Ponder
+ Let Stockfish ponder its next move while the opponent is thinking.
+
+ * #### MultiPV
+ Output the N best lines (principal variations, PVs) when searching.
+ Leave at 1 for best performance.
+
+ * #### Skill Level
+ Lower the Skill Level in order to make Stockfish play weaker.
-**Configuration**
+ * #### Move Overhead
+ Assume a time delay of x ms due to network and GUI overheads. This is useful to
+ avoid losses on time in those cases.
-Syzygybases are configured using the UCI options "SyzygyPath",
-"SyzygyProbeDepth", "Syzygy50MoveRule" and "SyzygyProbeLimit".
+ * #### Minimum Thinking Time
+ Search for at least x ms per move.
-The option "SyzygyPath" should be set to the directory or directories that
-contain the .rtbw and .rtbz files. Multiple directories should be
-separated by ";" on Windows and by ":" on Unix-based operating systems.
-**Do not use spaces around the ";" or ":".**
+ * #### Slow Mover
+ Lower values will make Stockfish take less time in games, higher values will
+ make it think longer.
-Example: `C:\tablebases\wdl345;C:\tablebases\wdl6;D:\tablebases\dtz345;D:\tablebases\dtz6`
+ * #### nodestime
+ Tells the engine to use nodes searched instead of wall time to account for
+ elapsed time. Useful for engine testing.
-It is recommended to store .rtbw files on an SSD. There is no loss in
-storing the .rtbz files on a regular HD.
+ * #### UCI_Chess960
+ An option handled by your GUI. If true, Stockfish will play Chess960.
-Increasing the "SyzygyProbeDepth" option lets the engine probe less
-aggressively. Set this option to a higher value if you experience too much
-slowdown (in terms of nps) due to TB probing.
+ * #### UCI_AnalyseMode
+ An option handled by your GUI.
-Set the "Syzygy50MoveRule" option to false if you want tablebase positions
-that are drawn by the 50-move rule to count as win or loss. This may be useful
-for correspondence games (because of tablebase adjudication).
+ * #### SyzygyPath
+ Path to the folders/directories storing the Syzygy tablebase files. Multiple
+ directories are to be separated by ";" on Windows and by ":" on Unix-based
+ operating systems. Do not use spaces around the ";" or ":".
+
+ Example: `C:\tablebases\wdl345;C:\tablebases\wdl6;D:\tablebases\dtz345;D:\tablebases\dtz6`
+
+ It is recommended to store .rtbw files on an SSD. There is no loss in storing
+ the .rtbz files on a regular HD. It is recommended to verify all md5 checksums
+ of the downloaded tablebase files (`md5sum -c checksum.md5`) as corruption will
+ lead to engine crashes.
-The "SyzygyProbeLimit" option should normally be left at its default value.
+ * #### SyzygyProbeDepth
+ Minimum remaining search depth for which a position is probed. Set this option
+ to a higher value to probe less agressively if you experience too much slowdown
+ (in terms of nps) due to TB probing.
+
+ * #### Syzygy50MoveRule
+ Disable to let fifty-move rule draws detected by Syzygy tablebase probes count
+ as wins or losses. This is useful for ICCF correspondence games.
+
+ * #### SyzygyProbeLimit
+ Limit Syzygy tablebase probing to positions with at most this many pieces left
+ (including kings and pawns).
+
+
+## What to expect from Syzygybases?
-**What to expect**
If the engine is searching a position that is not in the tablebases (e.g.
a position with 8 pieces), it will access the tablebases during the search.
-If the engine reports a very large score (typically 123.xx), this means
+If the engine reports a very large score (typically 153.xx), this means
that it has found a winning line into a tablebase position.
If the engine is given a position to search that is in the tablebases, it
immediately**, unless there is only a single good move. **The engine likely
will not report a mate score even if the position is known to be won.**
-It is therefore clear that behaviour is not identical to what one might
+It is therefore clear that this behaviour is not identical to what one might
be used to with Nalimov tablebases. There are technical reasons for this
difference, the main technical reason being that Nalimov tablebases use the
DTM metric (distance-to-mate), while Syzygybases use a variation of the
the 50-move rule.
-### Compiling it yourself
+## Compiling Stockfish yourself from the sources
On Unix-like systems, it should be possible to compile Stockfish
directly from the source code with the included Makefile.
set/unset some switches in the compiler command line; see file *types.h*
for a quick reference.
-### Resource For Understanding the Code Base
-* [Chess Programming Wiki](https://www.chessprogramming.org/Main_Page)
-has good overall chess engines explanations
-(techniques used here are well explained like hash maps etc), it was
-also recommended by the [support team at stockfish.](http://support.stockfishchess.org/discussions/questions/1132-how-to-understand-stockfish-sources)
+## Understanding the code base and participating in the project
+
+Stockfish's improvement over the last couple of years has been a great
+community effort. There are a few ways to help contribute to its growth.
+
+### Donating hardware
+
+Improving Stockfish requires a massive amount of testing. You can donate
+your hardware resources by installing the [Fishtest Worker](https://github.com/glinscott/fishtest/wiki/Running-the-worker)
+and view the current tests on [Fishtest](http://tests.stockfishchess.org/tests).
+
+### Improving the code
+
+If you want to help improve the code, there are several valuable ressources:
+
+* [In this wiki,](https://www.chessprogramming.org) many techniques used in
+Stockfish are explained with a lot of background information.
+
+* [The section on Stockfish](https://www.chessprogramming.org/Stockfish)
+describes many features and techniques used by Stockfish. However, it is
+generic rather than being focused on Stockfish's precise implementation.
+Nevertheless, a helpful resource.
-* [Here](https://www.chessprogramming.org/Stockfish) you can find a set
-of features and techniques used by Stockfish and each of them is explained
-at the wiki, however, it's a generic way rather than focusing on Stockfish's
-own implementation, but it will still help you.
+* The latest source can always be found on [GitHub](https://github.com/official-stockfish/Stockfish).
+Discussions about Stockfish take place in the [FishCooking](https://groups.google.com/forum/#!forum/fishcooking)
+group and engine testing is done on [Fishtest](http://tests.stockfishchess.org/tests).
+If you want to help improve Stockfish, please read this [guideline](https://github.com/glinscott/fishtest/wiki/Creating-my-first-test)
+first, where the basics of Stockfish development are explained.
-### Terms of use
+## Terms of use
-Stockfish is free, and distributed under the **GNU General Public License**
-(GPL). Essentially, this means that you are free to do almost exactly
+Stockfish is free, and distributed under the **GNU General Public License version 3**
+(GPL v3). Essentially, this means that you are free to do almost exactly
what you want with the program, including distributing it among your
friends, making it available for download from your web site, selling
it (either by itself or as part of some bigger software package), or
to where the source code can be found. If you make any changes to the
source code, these changes must also be made available under the GPL.
-For full details, read the copy of the GPL found in the file named
+For full details, read the copy of the GPL v3 found in the file named
*Copying.txt*.
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
+#include <bitset>
#include <algorithm>
#include "bitboard.h"
#include "misc.h"
uint8_t PopCnt16[1 << 16];
-int SquareDistance[SQUARE_NB][SQUARE_NB];
+uint8_t SquareDistance[SQUARE_NB][SQUARE_NB];
-Bitboard SquareBB[SQUARE_NB];
-Bitboard FileBB[FILE_NB];
-Bitboard RankBB[RANK_NB];
-Bitboard AdjacentFilesBB[FILE_NB];
-Bitboard ForwardRanksBB[COLOR_NB][RANK_NB];
-Bitboard BetweenBB[SQUARE_NB][SQUARE_NB];
Bitboard LineBB[SQUARE_NB][SQUARE_NB];
Bitboard DistanceRingBB[SQUARE_NB][8];
-Bitboard ForwardFileBB[COLOR_NB][SQUARE_NB];
-Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB];
-Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB];
Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB];
Bitboard PawnAttacks[COLOR_NB][SQUARE_NB];
+Bitboard SquareBB[SQUARE_NB];
+
+Bitboard KingFlank[FILE_NB] = {
+ QueenSide ^ FileDBB, QueenSide, QueenSide,
+ CenterFiles, CenterFiles,
+ KingSide, KingSide, KingSide ^ FileEBB
+};
Magic RookMagics[SQUARE_NB];
Magic BishopMagics[SQUARE_NB];
Bitboard BishopTable[0x1480]; // To store bishop attacks
void init_magics(Bitboard table[], Magic magics[], Direction directions[]);
-
- // popcount16() counts the non-zero bits using SWAR-Popcount algorithm
-
- unsigned popcount16(unsigned u) {
- u -= (u >> 1) & 0x5555U;
- u = ((u >> 2) & 0x3333U) + (u & 0x3333U);
- u = ((u >> 4) + u) & 0x0F0FU;
- return (u * 0x0101U) >> 8;
- }
}
void Bitboards::init() {
for (unsigned i = 0; i < (1 << 16); ++i)
- PopCnt16[i] = (uint8_t) popcount16(i);
+ PopCnt16[i] = std::bitset<16>(i).count();
for (Square s = SQ_A1; s <= SQ_H8; ++s)
SquareBB[s] = (1ULL << s);
- for (File f = FILE_A; f <= FILE_H; ++f)
- FileBB[f] = f > FILE_A ? FileBB[f - 1] << 1 : FileABB;
-
- for (Rank r = RANK_1; r <= RANK_8; ++r)
- RankBB[r] = r > RANK_1 ? RankBB[r - 1] << 8 : Rank1BB;
-
- for (File f = FILE_A; f <= FILE_H; ++f)
- AdjacentFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
-
- for (Rank r = RANK_1; r < RANK_8; ++r)
- ForwardRanksBB[WHITE][r] = ~(ForwardRanksBB[BLACK][r + 1] = ForwardRanksBB[BLACK][r] | RankBB[r]);
-
- for (Color c = WHITE; c <= BLACK; ++c)
- for (Square s = SQ_A1; s <= SQ_H8; ++s)
- {
- ForwardFileBB [c][s] = ForwardRanksBB[c][rank_of(s)] & FileBB[file_of(s)];
- PawnAttackSpan[c][s] = ForwardRanksBB[c][rank_of(s)] & AdjacentFilesBB[file_of(s)];
- PassedPawnMask[c][s] = ForwardFileBB [c][s] | PawnAttackSpan[c][s];
- }
-
for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
- if (s1 != s2)
{
SquareDistance[s1][s2] = std::max(distance<File>(s1, s2), distance<Rank>(s1, s2));
DistanceRingBB[s1][SquareDistance[s1][s2]] |= s2;
for (PieceType pt : { BISHOP, ROOK })
for (Square s2 = SQ_A1; s2 <= SQ_H8; ++s2)
- {
- if (!(PseudoAttacks[pt][s1] & s2))
- continue;
-
- LineBB[s1][s2] = (attacks_bb(pt, s1, 0) & attacks_bb(pt, s2, 0)) | s1 | s2;
- BetweenBB[s1][s2] = attacks_bb(pt, s1, SquareBB[s2]) & attacks_bb(pt, s2, SquareBB[s1]);
- }
+ if (PseudoAttacks[pt][s1] & s2)
+ LineBB[s1][s2] = (attacks_bb(pt, s1, 0) & attacks_bb(pt, s2, 0)) | s1 | s2;
}
}
// init_magics() computes all rook and bishop attacks at startup. Magic
// bitboards are used to look up attacks of sliding pieces. As a reference see
- // chessprogramming.wikispaces.com/Magic+Bitboards. In particular, here we
- // use the so called "fancy" approach.
+ // www.chessprogramming.org/Magic_Bitboards. In particular, here we use the so
+ // called "fancy" approach.
void init_magics(Bitboard table[], Magic magics[], Direction directions[]) {
constexpr Bitboard Rank7BB = Rank1BB << (8 * 6);
constexpr Bitboard Rank8BB = Rank1BB << (8 * 7);
-extern int SquareDistance[SQUARE_NB][SQUARE_NB];
+constexpr Bitboard QueenSide = FileABB | FileBBB | FileCBB | FileDBB;
+constexpr Bitboard CenterFiles = FileCBB | FileDBB | FileEBB | FileFBB;
+constexpr Bitboard KingSide = FileEBB | FileFBB | FileGBB | FileHBB;
+constexpr Bitboard Center = (FileDBB | FileEBB) & (Rank4BB | Rank5BB);
+
+extern uint8_t PopCnt16[1 << 16];
+extern uint8_t SquareDistance[SQUARE_NB][SQUARE_NB];
-extern Bitboard SquareBB[SQUARE_NB];
-extern Bitboard FileBB[FILE_NB];
-extern Bitboard RankBB[RANK_NB];
-extern Bitboard AdjacentFilesBB[FILE_NB];
-extern Bitboard ForwardRanksBB[COLOR_NB][RANK_NB];
-extern Bitboard BetweenBB[SQUARE_NB][SQUARE_NB];
extern Bitboard LineBB[SQUARE_NB][SQUARE_NB];
extern Bitboard DistanceRingBB[SQUARE_NB][8];
-extern Bitboard ForwardFileBB[COLOR_NB][SQUARE_NB];
-extern Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB];
-extern Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB];
extern Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB];
extern Bitboard PawnAttacks[COLOR_NB][SQUARE_NB];
+extern Bitboard KingFlank[FILE_NB];
+extern Bitboard SquareBB[SQUARE_NB];
/// Magic holds all magic bitboards relevant data for a single square
extern Magic RookMagics[SQUARE_NB];
extern Magic BishopMagics[SQUARE_NB];
-
-/// Overloads of bitwise operators between a Bitboard and a Square for testing
-/// whether a given bit is set in a bitboard, and for setting and clearing bits.
-
-inline Bitboard operator&(Bitboard b, Square s) {
- assert(s >= SQ_A1 && s <= SQ_H8);
- return b & SquareBB[s];
-}
-
-inline Bitboard operator|(Bitboard b, Square s) {
+inline Bitboard square_bb(Square s) {
assert(s >= SQ_A1 && s <= SQ_H8);
- return b | SquareBB[s];
+ return SquareBB[s];
}
-inline Bitboard operator^(Bitboard b, Square s) {
- assert(s >= SQ_A1 && s <= SQ_H8);
- return b ^ SquareBB[s];
-}
+/// Overloads of bitwise operators between a Bitboard and a Square for testing
+/// whether a given bit is set in a bitboard, and for setting and clearing bits.
-inline Bitboard& operator|=(Bitboard& b, Square s) {
- assert(s >= SQ_A1 && s <= SQ_H8);
- return b |= SquareBB[s];
-}
-
-inline Bitboard& operator^=(Bitboard& b, Square s) {
- assert(s >= SQ_A1 && s <= SQ_H8);
- return b ^= SquareBB[s];
-}
+inline Bitboard operator&( Bitboard b, Square s) { return b & square_bb(s); }
+inline Bitboard operator|( Bitboard b, Square s) { return b | square_bb(s); }
+inline Bitboard operator^( Bitboard b, Square s) { return b ^ square_bb(s); }
+inline Bitboard& operator|=(Bitboard& b, Square s) { return b |= square_bb(s); }
+inline Bitboard& operator^=(Bitboard& b, Square s) { return b ^= square_bb(s); }
constexpr bool more_than_one(Bitboard b) {
return b & (b - 1);
return bool(DarkSquares & s1) != bool(DarkSquares & s2);
}
+
/// rank_bb() and file_bb() return a bitboard representing all the squares on
/// the given file or rank.
inline Bitboard rank_bb(Rank r) {
- return RankBB[r];
+ return Rank1BB << (8 * r);
}
inline Bitboard rank_bb(Square s) {
- return RankBB[rank_of(s)];
+ return rank_bb(rank_of(s));
}
inline Bitboard file_bb(File f) {
- return FileBB[f];
+ return FileABB << f;
}
inline Bitboard file_bb(Square s) {
- return FileBB[file_of(s)];
+ return file_bb(file_of(s));
}
-/// shift() moves a bitboard one step along direction D (mainly for pawns)
+/// shift() moves a bitboard one step along direction D
template<Direction D>
constexpr Bitboard shift(Bitboard b) {
}
-/// pawn_attacks_bb() returns the pawn attacks for the given color from the
-/// squares in the given bitboard.
+/// pawn_attacks_bb() returns the squares attacked by pawns of the given color
+/// from the squares in the given bitboard.
template<Color C>
constexpr Bitboard pawn_attacks_bb(Bitboard b) {
}
-/// double_pawn_attacks_bb() returns the pawn attacks for the given color
-/// from the squares in the given bitboard.
+/// pawn_double_attacks_bb() returns the squares doubly attacked by pawns of the
+/// given color from the squares in the given bitboard.
template<Color C>
-constexpr Bitboard double_pawn_attacks_bb(Bitboard b) {
+constexpr Bitboard pawn_double_attacks_bb(Bitboard b) {
return C == WHITE ? shift<NORTH_WEST>(b) & shift<NORTH_EAST>(b)
: shift<SOUTH_WEST>(b) & shift<SOUTH_EAST>(b);
}
/// adjacent files of the given one.
inline Bitboard adjacent_files_bb(File f) {
- return AdjacentFilesBB[f];
+ return shift<EAST>(file_bb(f)) | shift<WEST>(file_bb(f));
}
-/// between_bb() returns a bitboard representing all the squares between the two
-/// given ones. For instance, between_bb(SQ_C4, SQ_F7) returns a bitboard with
-/// the bits for square d5 and e6 set. If s1 and s2 are not on the same rank, file
-/// or diagonal, 0 is returned.
+/// between_bb() returns squares that are linearly between the given squares
+/// If the given squares are not on a same file/rank/diagonal, return 0.
inline Bitboard between_bb(Square s1, Square s2) {
- return BetweenBB[s1][s2];
+ return LineBB[s1][s2] & ( (AllSquares << (s1 + (s1 < s2)))
+ ^(AllSquares << (s2 + !(s1 < s2))));
}
-/// forward_ranks_bb() returns a bitboard representing the squares on all the ranks
+/// forward_ranks_bb() returns a bitboard representing the squares on the ranks
/// in front of the given one, from the point of view of the given color. For instance,
/// forward_ranks_bb(BLACK, SQ_D3) will return the 16 squares on ranks 1 and 2.
inline Bitboard forward_ranks_bb(Color c, Square s) {
- return ForwardRanksBB[c][rank_of(s)];
+ return c == WHITE ? ~Rank1BB << 8 * (rank_of(s) - RANK_1)
+ : ~Rank8BB >> 8 * (RANK_8 - rank_of(s));
}
-/// forward_file_bb() returns a bitboard representing all the squares along the line
-/// in front of the given one, from the point of view of the given color:
-/// ForwardFileBB[c][s] = forward_ranks_bb(c, s) & file_bb(s)
+/// forward_file_bb() returns a bitboard representing all the squares along the
+/// line in front of the given one, from the point of view of the given color.
inline Bitboard forward_file_bb(Color c, Square s) {
- return ForwardFileBB[c][s];
+ return forward_ranks_bb(c, s) & file_bb(s);
}
-/// pawn_attack_span() returns a bitboard representing all the squares that can be
-/// attacked by a pawn of the given color when it moves along its file, starting
-/// from the given square:
-/// PawnAttackSpan[c][s] = forward_ranks_bb(c, s) & adjacent_files_bb(file_of(s));
+/// pawn_attack_span() returns a bitboard representing all the squares that can
+/// be attacked by a pawn of the given color when it moves along its file,
+/// starting from the given square.
inline Bitboard pawn_attack_span(Color c, Square s) {
- return PawnAttackSpan[c][s];
+ return forward_ranks_bb(c, s) & adjacent_files_bb(file_of(s));
}
-/// passed_pawn_mask() returns a bitboard mask which can be used to test if a
-/// pawn of the given color and on the given square is a passed pawn:
-/// PassedPawnMask[c][s] = pawn_attack_span(c, s) | forward_file_bb(c, s)
+/// passed_pawn_span() returns a bitboard which can be used to test if a pawn of
+/// the given color and on the given square is a passed pawn.
-inline Bitboard passed_pawn_mask(Color c, Square s) {
- return PassedPawnMask[c][s];
+inline Bitboard passed_pawn_span(Color c, Square s) {
+ return forward_ranks_bb(c, s) & (adjacent_files_bb(file_of(s)) | file_bb(s));
}
/// distance() functions return the distance between x and y, defined as the
/// number of steps for a king in x to reach y. Works with squares, ranks, files.
-template<typename T> inline int distance(T x, T y) { return x < y ? y - x : x - y; }
+template<typename T> inline int distance(T x, T y) { return std::abs(x - y); }
template<> inline int distance<Square>(Square x, Square y) { return SquareDistance[x][y]; }
template<typename T1, typename T2> inline int distance(T2 x, T2 y);
template<> inline int distance<File>(Square x, Square y) { return distance(file_of(x), file_of(y)); }
template<> inline int distance<Rank>(Square x, Square y) { return distance(rank_of(x), rank_of(y)); }
+template<class T> constexpr const T& clamp(const T& v, const T& lo, const T& hi) {
+ return v < lo ? lo : v > hi ? hi : v;
+}
/// attacks_bb() returns a bitboard representing all the squares attacked by a
/// piece of type Pt (bishop or rook) placed on 's'.
#ifndef USE_POPCNT
- extern uint8_t PopCnt16[1 << 16];
union { Bitboard bb; uint16_t u[4]; } v = { b };
return PopCnt16[v.u[0]] + PopCnt16[v.u[1]] + PopCnt16[v.u[2]] + PopCnt16[v.u[3]];
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include "bitboard.h"
if (file_of(pos.square<PAWN>(strongSide)) >= FILE_E)
sq = Square(sq ^ 7); // Mirror SQ_H1 -> SQ_A1
- if (strongSide == BLACK)
- sq = ~sq;
-
- return sq;
+ return strongSide == WHITE ? sq : ~sq;
}
} // namespace
Square loserKSq = pos.square<KING>(weakSide);
Square bishopSq = pos.square<BISHOP>(strongSide);
- // If our Bishop does not attack A1/H8, we flip the enemy king square
+ // If our Bishop does not attack A1/H8, we flip the enemy king square
// to drive to opposite corners (A8/H1).
Value result = VALUE_KNOWN_WIN
}
+/// KNN vs KP. Simply push the opposing king to the corner
+template<>
+Value Endgame<KNNKP>::operator()(const Position& pos) const {
+
+ assert(verify_material(pos, strongSide, 2 * KnightValueMg, 0));
+ assert(verify_material(pos, weakSide, VALUE_ZERO, 1));
+
+ Value result = 2 * KnightValueEg
+ - PawnValueEg
+ + PushToEdges[pos.square<KING>(weakSide)];
+
+ return strongSide == pos.side_to_move() ? result : -result;
+}
+
+
/// Some cases of trivial draws
template<> Value Endgame<KNNK>::operator()(const Position&) const { return VALUE_DRAW; }
template<>
ScaleFactor Endgame<KNPKB>::operator()(const Position& pos) const {
+ assert(verify_material(pos, strongSide, KnightValueMg, 1));
+ assert(verify_material(pos, weakSide, BishopValueMg, 0));
+
Square pawnSq = pos.square<PAWN>(strongSide);
Square bishopSq = pos.square<BISHOP>(weakSide);
Square weakKingSq = pos.square<KING>(weakSide);
EVALUATION_FUNCTIONS,
KNNK, // KNN vs K
+ KNNKP, // KNN vs KP
KXK, // Generic "mate lone king" eval
KBNK, // KBN vs K
KPK, // KP vs K
add<KRKN>("KRKN");
add<KQKP>("KQKP");
add<KQKR>("KQKR");
+ add<KNNKP>("KNNKP");
add<KNPK>("KNPK");
add<KNPKB>("KNPKB");
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include <cstring> // For std::memset
#include <iomanip>
namespace {
- constexpr Bitboard QueenSide = FileABB | FileBBB | FileCBB | FileDBB;
- constexpr Bitboard CenterFiles = FileCBB | FileDBB | FileEBB | FileFBB;
- constexpr Bitboard KingSide = FileEBB | FileFBB | FileGBB | FileHBB;
- constexpr Bitboard Center = (FileDBB | FileEBB) & (Rank4BB | Rank5BB);
-
- constexpr Bitboard KingFlank[FILE_NB] = {
- QueenSide ^ FileDBB, QueenSide, QueenSide,
- CenterFiles, CenterFiles,
- KingSide, KingSide, KingSide ^ FileEBB
- };
-
// Threshold for lazy and space evaluation
constexpr Value LazyThreshold = Value(1500);
constexpr Value SpaceThreshold = Value(12222);
// Penalties for enemy's safe checks
constexpr int QueenSafeCheck = 780;
- constexpr int RookSafeCheck = 880;
- constexpr int BishopSafeCheck = 435;
+ constexpr int RookSafeCheck = 1080;
+ constexpr int BishopSafeCheck = 635;
constexpr int KnightSafeCheck = 790;
#define S(mg, eg) make_score(mg, eg)
S(106,184), S(109,191), S(113,206), S(116,212) }
};
- // Outpost[knight/bishop][supported by pawn] contains bonuses for minor
- // pieces if they occupy or can reach an outpost square, bigger if that
- // square is supported by a pawn.
- constexpr Score Outpost[][2] = {
- { S(22, 6), S(36,12) }, // Knight
- { S( 9, 2), S(15, 5) } // Bishop
- };
-
// RookOnFile[semiopen/open] contains bonuses for each rook when there is
// no (friendly) pawn on the rook file.
constexpr Score RookOnFile[] = { S(18, 7), S(44, 20) };
// Assorted bonuses and penalties
constexpr Score BishopPawns = S( 3, 7);
- constexpr Score CloseEnemies = S( 8, 0);
constexpr Score CorneredBishop = S( 50, 50);
+ constexpr Score FlankAttacks = S( 8, 0);
constexpr Score Hanging = S( 69, 36);
constexpr Score KingProtector = S( 7, 8);
constexpr Score KnightOnQueen = S( 16, 12);
constexpr Score LongDiagonalBishop = S( 45, 0);
constexpr Score MinorBehindPawn = S( 18, 3);
+ constexpr Score Outpost = S( 9, 3);
constexpr Score PawnlessFlank = S( 17, 95);
constexpr Score RestrictedPiece = S( 7, 7);
constexpr Score RookOnPawn = S( 10, 32);
constexpr Score ThreatByPawnPush = S( 48, 39);
constexpr Score ThreatByRank = S( 13, 0);
constexpr Score ThreatBySafePawn = S(173, 94);
- constexpr Score TrappedRook = S( 96, 4);
+ constexpr Score TrappedRook = S( 47, 4);
constexpr Score WeakQueen = S( 49, 15);
constexpr Score WeakUnopposedPawn = S( 12, 23);
// kingRing[color] are the squares adjacent to the king, plus (only for a
// king on its first rank) the squares two ranks in front. For instance,
// if black's king is on g8, kingRing[BLACK] is f8, h8, f7, g7, h7, f6, g6
- // and h6. It is set to 0 when king safety evaluation is skipped.
+ // and h6.
Bitboard kingRing[COLOR_NB];
// kingAttackersCount[color] is the number of pieces of the given color
constexpr Direction Down = (Us == WHITE ? SOUTH : NORTH);
constexpr Bitboard LowRanks = (Us == WHITE ? Rank2BB | Rank3BB: Rank7BB | Rank6BB);
+ const Square ksq = pos.square<KING>(Us);
+
+ Bitboard dblAttackByPawn = pawn_double_attacks_bb<Us>(pos.pieces(Us, PAWN));
+
// Find our pawns that are blocked or on the first two ranks
Bitboard b = pos.pieces(Us, PAWN) & (shift<Down>(pos.pieces()) | LowRanks);
- // Squares occupied by those pawns, by our king or queen, or controlled by enemy pawns
- // are excluded from the mobility area.
+ // Squares occupied by those pawns, by our king or queen or controlled by
+ // enemy pawns are excluded from the mobility area.
mobilityArea[Us] = ~(b | pos.pieces(Us, KING, QUEEN) | pe->pawn_attacks(Them));
- // Initialise attackedBy bitboards for kings and pawns
- attackedBy[Us][KING] = pos.attacks_from<KING>(pos.square<KING>(Us));
+ // Initialize attackedBy[] for king and pawns
+ attackedBy[Us][KING] = pos.attacks_from<KING>(ksq);
attackedBy[Us][PAWN] = pe->pawn_attacks(Us);
attackedBy[Us][ALL_PIECES] = attackedBy[Us][KING] | attackedBy[Us][PAWN];
- attackedBy2[Us] = attackedBy[Us][KING] & attackedBy[Us][PAWN];
+ attackedBy2[Us] = (attackedBy[Us][KING] & attackedBy[Us][PAWN])
+ | dblAttackByPawn;
- kingRing[Us] = kingAttackersCount[Them] = 0;
+ // Init our king safety tables
+ kingRing[Us] = attackedBy[Us][KING];
+ if (relative_rank(Us, ksq) == RANK_1)
+ kingRing[Us] |= shift<Up>(kingRing[Us]);
- // Init our king safety tables only if we are going to use them
- if (pos.non_pawn_material(Them) >= RookValueMg + KnightValueMg)
- {
- kingRing[Us] = attackedBy[Us][KING];
- if (relative_rank(Us, pos.square<KING>(Us)) == RANK_1)
- kingRing[Us] |= shift<Up>(kingRing[Us]);
+ if (file_of(ksq) == FILE_H)
+ kingRing[Us] |= shift<WEST>(kingRing[Us]);
- if (file_of(pos.square<KING>(Us)) == FILE_H)
- kingRing[Us] |= shift<WEST>(kingRing[Us]);
+ else if (file_of(ksq) == FILE_A)
+ kingRing[Us] |= shift<EAST>(kingRing[Us]);
- else if (file_of(pos.square<KING>(Us)) == FILE_A)
- kingRing[Us] |= shift<EAST>(kingRing[Us]);
+ kingAttackersCount[Them] = popcount(kingRing[Us] & pe->pawn_attacks(Them));
+ kingAttacksCount[Them] = kingAttackersWeight[Them] = 0;
- kingAttackersCount[Them] = popcount(kingRing[Us] & pe->pawn_attacks(Them));
- kingRing[Us] &= ~double_pawn_attacks_bb<Us>(pos.pieces(Us, PAWN));
- kingAttacksCount[Them] = kingAttackersWeight[Them] = 0;
- }
+ // Remove from kingRing[] the squares defended by two pawns
+ kingRing[Us] &= ~dblAttackByPawn;
}
const Square* pl = pos.squares<Pt>(Us);
Bitboard b, bb;
- Square s;
Score score = SCORE_ZERO;
attackedBy[Us][Pt] = 0;
- while ((s = *pl++) != SQ_NONE)
+ for (Square s = *pl; s != SQ_NONE; s = *++pl)
{
// Find attacked squares, including x-ray attacks for bishops and rooks
b = Pt == BISHOP ? attacks_bb<BISHOP>(s, pos.pieces() ^ pos.pieces(QUEEN))
// Bonus if piece is on an outpost square or can reach one
bb = OutpostRanks & ~pe->pawn_attacks_span(Them);
if (bb & s)
- score += Outpost[Pt == BISHOP][bool(attackedBy[Us][PAWN] & s)] * 2;
+ score += Outpost * (Pt == KNIGHT ? 4 : 2)
+ * (1 + bool(attackedBy[Us][PAWN] & s));
else if (bb &= b & ~pos.pieces(Us))
- score += Outpost[Pt == BISHOP][bool(attackedBy[Us][PAWN] & bb)];
+ score += Outpost * (Pt == KNIGHT ? 2 : 1)
+ * (1 + bool(attackedBy[Us][PAWN] & bb));
// Knight and Bishop bonus for being right behind a pawn
if (shift<Down>(pos.pieces(PAWN)) & s)
{
File kf = file_of(pos.square<KING>(Us));
if ((kf < FILE_E) == (file_of(s) < kf))
- score -= (TrappedRook - make_score(mob * 22, 0)) * (1 + !pos.castling_rights(Us));
+ score -= TrappedRook * (1 + !pos.castling_rights(Us));
}
}
constexpr Bitboard Camp = (Us == WHITE ? AllSquares ^ Rank6BB ^ Rank7BB ^ Rank8BB
: AllSquares ^ Rank1BB ^ Rank2BB ^ Rank3BB);
+ Bitboard weak, b1, b2, safe, unsafeChecks = 0;
+ Bitboard rookChecks, queenChecks, bishopChecks, knightChecks;
+ int kingDanger = 0;
const Square ksq = pos.square<KING>(Us);
- Bitboard kingFlank, weak, b, b1, b2, safe, unsafeChecks;
- // King shelter and enemy pawns storm
+ // Init the score with king shelter and enemy pawns storm
Score score = pe->king_safety<Us>(pos);
- // Find the squares that opponent attacks in our king flank, and the squares
- // which are attacked twice in that flank.
- kingFlank = KingFlank[file_of(ksq)];
- b1 = attackedBy[Them][ALL_PIECES] & kingFlank & Camp;
- b2 = b1 & attackedBy2[Them];
+ // Attacked squares defended at most once by our queen or king
+ weak = attackedBy[Them][ALL_PIECES]
+ & ~attackedBy2[Us]
+ & (~attackedBy[Us][ALL_PIECES] | attackedBy[Us][KING] | attackedBy[Us][QUEEN]);
- int tropism = popcount(b1) + popcount(b2);
+ // Analyse the safe enemy's checks which are possible on next move
+ safe = ~pos.pieces(Them);
+ safe &= ~attackedBy[Us][ALL_PIECES] | (weak & attackedBy2[Them]);
- // Main king safety evaluation
- if (kingAttackersCount[Them] > 1 - pos.count<QUEEN>(Them))
- {
- int kingDanger = 0;
- unsafeChecks = 0;
+ b1 = attacks_bb<ROOK >(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN));
+ b2 = attacks_bb<BISHOP>(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN));
- // Attacked squares defended at most once by our queen or king
- weak = attackedBy[Them][ALL_PIECES]
- & ~attackedBy2[Us]
- & (~attackedBy[Us][ALL_PIECES] | attackedBy[Us][KING] | attackedBy[Us][QUEEN]);
+ // Enemy rooks checks
+ rookChecks = b1 & safe & attackedBy[Them][ROOK];
- // Analyse the safe enemy's checks which are possible on next move
- safe = ~pos.pieces(Them);
- safe &= ~attackedBy[Us][ALL_PIECES] | (weak & attackedBy2[Them]);
+ if (rookChecks)
+ kingDanger += RookSafeCheck;
+ else
+ unsafeChecks |= b1 & attackedBy[Them][ROOK];
+
+ // Enemy queen safe checks: we count them only if they are from squares from
+ // which we can't give a rook check, because rook checks are more valuable.
+ queenChecks = (b1 | b2)
+ & attackedBy[Them][QUEEN]
+ & safe
+ & ~attackedBy[Us][QUEEN]
+ & ~rookChecks;
+
+ if (queenChecks)
+ kingDanger += QueenSafeCheck;
+
+ // Enemy bishops checks: we count them only if they are from squares from
+ // which we can't give a queen check, because queen checks are more valuable.
+ bishopChecks = b2
+ & attackedBy[Them][BISHOP]
+ & safe
+ & ~queenChecks;
+
+ if (bishopChecks)
+ kingDanger += BishopSafeCheck;
+ else
+ unsafeChecks |= b2 & attackedBy[Them][BISHOP];
- b1 = attacks_bb<ROOK >(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN));
- b2 = attacks_bb<BISHOP>(ksq, pos.pieces() ^ pos.pieces(Us, QUEEN));
+ // Enemy knights checks
+ knightChecks = pos.attacks_from<KNIGHT>(ksq) & attackedBy[Them][KNIGHT];
- // Enemy queen safe checks
- if ((b1 | b2) & attackedBy[Them][QUEEN] & safe & ~attackedBy[Us][QUEEN])
- kingDanger += QueenSafeCheck;
+ if (knightChecks & safe)
+ kingDanger += KnightSafeCheck;
+ else
+ unsafeChecks |= knightChecks;
- b1 &= attackedBy[Them][ROOK];
- b2 &= attackedBy[Them][BISHOP];
+ // Unsafe or occupied checking squares will also be considered, as long as
+ // the square is in the attacker's mobility area.
+ unsafeChecks &= mobilityArea[Them];
- // Enemy rooks checks
- if (b1 & safe)
- kingDanger += RookSafeCheck;
- else
- unsafeChecks |= b1;
+ // Find the squares that opponent attacks in our king flank, and the squares
+ // which are attacked twice in that flank.
+ b1 = attackedBy[Them][ALL_PIECES] & KingFlank[file_of(ksq)] & Camp;
+ b2 = b1 & attackedBy2[Them];
- // Enemy bishops checks
- if (b2 & safe)
- kingDanger += BishopSafeCheck;
- else
- unsafeChecks |= b2;
+ int kingFlankAttacks = popcount(b1) + popcount(b2);
- // Enemy knights checks
- b = pos.attacks_from<KNIGHT>(ksq) & attackedBy[Them][KNIGHT];
- if (b & safe)
- kingDanger += KnightSafeCheck;
- else
- unsafeChecks |= b;
-
- // Unsafe or occupied checking squares will also be considered, as long as
- // the square is in the attacker's mobility area.
- unsafeChecks &= mobilityArea[Them];
-
- kingDanger += kingAttackersCount[Them] * kingAttackersWeight[Them]
- + 69 * kingAttacksCount[Them]
- + 185 * popcount(kingRing[Us] & weak)
- + 150 * popcount(pos.blockers_for_king(Us) | unsafeChecks)
- + tropism * tropism / 4
- - 873 * !pos.count<QUEEN>(Them)
- - 6 * mg_value(score) / 8
- + mg_value(mobility[Them] - mobility[Us])
- - 30;
-
- // Transform the kingDanger units into a Score, and subtract it from the evaluation
- if (kingDanger > 0)
- score -= make_score(kingDanger * kingDanger / 4096, kingDanger / 16);
- }
+ kingDanger += kingAttackersCount[Them] * kingAttackersWeight[Them]
+ + 69 * kingAttacksCount[Them]
+ + 185 * popcount(kingRing[Us] & weak)
+ - 100 * bool(attackedBy[Us][KNIGHT] & attackedBy[Us][KING])
+ + 150 * popcount(pos.blockers_for_king(Us) | unsafeChecks)
+ - 873 * !pos.count<QUEEN>(Them)
+ - 6 * mg_value(score) / 8
+ + mg_value(mobility[Them] - mobility[Us])
+ + 5 * kingFlankAttacks * kingFlankAttacks / 16
+ - 15;
+
+ // Transform the kingDanger units into a Score, and subtract it from the evaluation
+ if (kingDanger > 100)
+ score -= make_score(kingDanger * kingDanger / 4096, kingDanger / 16);
// Penalty when our king is on a pawnless flank
- if (!(pos.pieces(PAWN) & kingFlank))
+ if (!(pos.pieces(PAWN) & KingFlank[file_of(ksq)]))
score -= PawnlessFlank;
- // King tropism bonus, to anticipate slow motion attacks on our king
- score -= CloseEnemies * tropism;
+ // Penalty if king flank is under attack, potentially moving toward the king
+ score -= FlankAttacks * kingFlankAttacks;
if (T)
Trace::add(KING, Us, score);
constexpr Direction Up = (Us == WHITE ? NORTH : SOUTH);
constexpr Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
- Bitboard b, weak, defended, nonPawnEnemies, stronglyProtected, safe, restricted;
+ Bitboard b, weak, defended, nonPawnEnemies, stronglyProtected, safe;
Score score = SCORE_ZERO;
// Non-pawn enemies
- nonPawnEnemies = pos.pieces(Them) & ~pos.pieces(Them, PAWN);
+ nonPawnEnemies = pos.pieces(Them) & ~pos.pieces(PAWN);
// Squares strongly protected by the enemy, either because they defend the
// square with a pawn, or because they defend the square twice and we don't.
}
// Bonus for restricting their piece moves
- restricted = attackedBy[Them][ALL_PIECES]
- & ~stronglyProtected
- & attackedBy[Us][ALL_PIECES];
- score += RestrictedPiece * popcount(restricted);
+ b = attackedBy[Them][ALL_PIECES]
+ & ~stronglyProtected
+ & attackedBy[Us][ALL_PIECES];
+
+ score += RestrictedPiece * popcount(b);
// Bonus for enemy unopposed weak pawns
if (pos.pieces(Us, ROOK, QUEEN))
if (pos.non_pawn_material() < SpaceThreshold)
return SCORE_ZERO;
- constexpr Color Them = (Us == WHITE ? BLACK : WHITE);
+ constexpr Color Them = (Us == WHITE ? BLACK : WHITE);
+ constexpr Direction Down = (Us == WHITE ? SOUTH : NORTH);
constexpr Bitboard SpaceMask =
Us == WHITE ? CenterFiles & (Rank2BB | Rank3BB | Rank4BB)
: CenterFiles & (Rank7BB | Rank6BB | Rank5BB);
// Find all squares which are at most three squares behind some friendly pawn
Bitboard behind = pos.pieces(Us, PAWN);
- behind |= (Us == WHITE ? behind >> 8 : behind << 8);
- behind |= (Us == WHITE ? behind >> 16 : behind << 16);
+ behind |= shift<Down>(behind);
+ behind |= shift<Down>(shift<Down>(behind));
int bonus = popcount(safe) + popcount(behind & safe);
- int weight = pos.count<ALL_PIECES>(Us) - 2 * pe->open_files();
+ int weight = pos.count<ALL_PIECES>(Us)
+ - 2 * popcount(pe->semiopenFiles[WHITE] & pe->semiopenFiles[BLACK]);
Score score = make_score(bonus * weight * weight / 16, 0);
&& (pos.pieces(PAWN) & KingSide);
// Compute the initiative bonus for the attacking side
- int complexity = 8 * pe->pawn_asymmetry()
- + 1
2 * pos.count<PAWN>()
- + 12 * outflanking
- + 16 * pawnsOnBothFlanks
- + 48 * !pos.non_pawn_material()
- -118 ;
+ int complexity = 9 * pe->passed_count()
+ + 1
1 * pos.count<PAWN>()
+ + 9 * outflanking
+ + 18 * pawnsOnBothFlanks
+ + 49 * !pos.non_pawn_material()
+ -103 ;
// Now apply the bonus: note that we find the attacking side by extracting
// the sign of the endgame value, and that we carefully cap the bonus so
if ( pos.opposite_bishops()
&& pos.non_pawn_material(WHITE) == BishopValueMg
&& pos.non_pawn_material(BLACK) == BishopValueMg)
- sf = 8 + 4 * pe->pawn_asymmetry();
+ sf = 16 + 4 * pe->passed_count();
else
sf = std::min(40 + (pos.opposite_bishops() ? 2 : 7) * pos.count<PAWN>(strongSide), sf);
v = mg_value(score) * int(me->game_phase())
+ eg_value(score) * int(PHASE_MIDGAME - me->game_phase()) * sf / SCALE_FACTOR_NORMAL;
- v /= int(PHASE_MIDGAME);
+ v /= PHASE_MIDGAME;
// In case of tracing add all remaining individual evaluation terms
if (T)
<< " ------------+-------------+-------------+------------\n"
<< " Material | " << Term(MATERIAL)
<< " Imbalance | " << Term(IMBALANCE)
- << " Initiative | " << Term(INITIATIVE)
<< " Pawns | " << Term(PAWN)
<< " Knights | " << Term(KNIGHT)
<< " Bishops | " << Term(BISHOP)
<< " Threats | " << Term(THREAT)
<< " Passed | " << Term(PASSED)
<< " Space | " << Term(SPACE)
+ << " Initiative | " << Term(INITIATIVE)
<< " ------------+-------------+-------------+------------\n"
<< " Total | " << Term(TOTAL);
Position::init();
Bitbases::init();
Search::init();
- Pawns::init();
Threads.set(Options["Threads"]);
Search::clear(); // After threads are up
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm> // For std::min
#include <cassert>
#include <cstring> // For std::memset
bool is_KBPsK(const Position& pos, Color us) {
return pos.non_pawn_material(us) == BishopValueMg
- && pos.count<BISHOP>(us) == 1
&& pos.count<PAWN >(us) >= 1;
}
bool is_KQKRPs(const Position& pos, Color us) {
return !pos.count<PAWN>(us)
&& pos.non_pawn_material(us) == QueenValueMg
- && pos.count<QUEEN>(us) == 1
&& pos.count<ROOK>(~us) == 1
&& pos.count<PAWN>(~us) >= 1;
}
Value npm_w = pos.non_pawn_material(WHITE);
Value npm_b = pos.non_pawn_material(BLACK);
- Value npm = std::max(EndgameLimit, std::min(npm_w + npm_b, MidgameLimit));
+ Value npm = clamp(npm_w + npm_b, EndgameLimit, MidgameLimit);
// Map total non-pawn material into [PHASE_ENDGAME, PHASE_MIDGAME]
e->gamePhase = Phase(((npm - EndgameLimit) * PHASE_MIDGAME) / (MidgameLimit - EndgameLimit));
// OK, we didn't find any special evaluation function for the current material
// configuration. Is there a suitable specialized scaling function?
- const EndgameBase<ScaleFactor>* sf;
+ const auto* sf = pos.this_thread()->endgames.probe<ScaleFactor>(key);
- if ((sf = pos.this_thread()->endgames.probe<ScaleFactor>(key)) != nullptr)
+ if (sf)
{
e->scalingFunction[sf->strongSide] = sf; // Only strong color assigned
return e;
Entry* operator[](Key key) { return &table[(uint32_t)key & (Size - 1)]; }
private:
- std::vector<Entry> table = std::vector<Entry>(Size);
+ std::vector<Entry> table = std::vector<Entry>(Size); // Allocate on the heap
};
namespace {
- template<Color Us, CastlingSide Cs, bool Checks, bool Chess960>
- ExtMove* generate_castling(const Position& pos, ExtMove* moveList) {
-
- constexpr CastlingRight Cr = Us | Cs;
- constexpr bool KingSide = (Cs == KING_SIDE);
-
- if (pos.castling_impeded(Cr) || !pos.can_castle(Cr))
- return moveList;
-
- // After castling, the rook and king final positions are the same in Chess960
- // as they would be in standard chess.
- Square kfrom = pos.square<KING>(Us);
- Square rfrom = pos.castling_rook_square(Cr);
- Square kto = relative_square(Us, KingSide ? SQ_G1 : SQ_C1);
- Bitboard enemies = pos.pieces(~Us);
-
- assert(!pos.checkers());
-
- const Direction step = Chess960 ? kto > kfrom ? WEST : EAST
- : KingSide ? WEST : EAST;
-
- for (Square s = kto; s != kfrom; s += step)
- if (pos.attackers_to(s) & enemies)
- return moveList;
-
- // Because we generate only legal castling moves we need to verify that
- // when moving the castling rook we do not discover some hidden checker.
- // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
- if (Chess960 && (attacks_bb<ROOK>(kto, pos.pieces() ^ rfrom) & pos.pieces(~Us, ROOK, QUEEN)))
- return moveList;
-
- Move m = make<CASTLING>(kfrom, rfrom);
-
- if (Checks && !pos.gives_check(m))
- return moveList;
-
- *moveList++ = m;
- return moveList;
- }
-
-
template<GenType Type, Direction D>
ExtMove* make_promotions(ExtMove* moveList, Square to, Square ksq) {
template<Color Us, GenType Type>
ExtMove* generate_pawn_moves(const Position& pos, ExtMove* moveList, Bitboard target) {
- // Compute our parametrized parameters at compile time, named according to
- // the point of view of white side.
+ // Compute some compile time parameters relative to the white side
constexpr Color Them = (Us == WHITE ? BLACK : WHITE);
- constexpr Bitboard TRank8BB = (Us == WHITE ? Rank8BB : Rank1BB);
constexpr Bitboard TRank7BB = (Us == WHITE ? Rank7BB : Rank2BB);
constexpr Bitboard TRank3BB = (Us == WHITE ? Rank3BB : Rank6BB);
constexpr Direction Up = (Us == WHITE ? NORTH : SOUTH);
// if the pawn is not on the same file as the enemy king, because we
// don't generate captures. Note that a possible discovery check
// promotion has been already generated amongst the captures.
- Bitboard dcCandidates = pos.blockers_for_king(Them);
- if (pawnsNotOn7 & dcCandidates)
+ Bitboard dcCandidateQuiets = pos.blockers_for_king(Them) & pawnsNotOn7;
+ if (dcCandidateQuiets)
{
- Bitboard dc1 = shift<Up>(pawnsNotOn7 & dcCandidates) & emptySquares & ~file_bb(ksq);
+ Bitboard dc1 = shift<Up>(dcCandidateQuiets) & emptySquares & ~file_bb(ksq);
Bitboard dc2 = shift<Up>(dc1 & TRank3BB) & emptySquares;
b1 |= dc1;
}
// Promotions and underpromotions
- if (pawnsOn7 && (Type != EVASIONS || (target & TRank8BB)))
+ if (pawnsOn7)
{
if (Type == CAPTURES)
emptySquares = ~pos.pieces();
template<Color Us, GenType Type>
ExtMove* generate_all(const Position& pos, ExtMove* moveList, Bitboard target) {
- constexpr bool Checks = Type == QUIET_CHECKS;
+ constexpr CastlingRight OO = Us | KING_SIDE;
+ constexpr CastlingRight OOO = Us | QUEEN_SIDE;
+ constexpr bool Checks = Type == QUIET_CHECKS; // Reduce template instantations
moveList = generate_pawn_moves<Us, Type>(pos, moveList, target);
moveList = generate_moves<KNIGHT, Checks>(pos, moveList, Us, target);
Bitboard b = pos.attacks_from<KING>(ksq) & target;
while (b)
*moveList++ = make_move(ksq, pop_lsb(&b));
- }
- if (Type != CAPTURES && Type != EVASIONS && pos.castling_rights(Us))
- {
- if (pos.is_chess960())
- {
- moveList = generate_castling<Us, KING_SIDE, Checks, true>(pos, moveList);
- moveList = generate_castling<Us, QUEEN_SIDE, Checks, true>(pos, moveList);
- }
- else
+ if (Type != CAPTURES && pos.can_castle(CastlingRight(OO | OOO)))
{
- moveList = generate_castling<Us, KING_SIDE, Checks, false>(pos, moveList);
- moveList = generate_castling<Us, QUEEN_SIDE, Checks, false>(pos, moveList);
+ if (!pos.castling_impeded(OO) && pos.can_castle(OO))
+ *moveList++ = make<CASTLING>(ksq, pos.castling_rook_square(OO));
+
+ if (!pos.castling_impeded(OOO) && pos.can_castle(OOO))
+ *moveList++ = make<CASTLING>(ksq, pos.castling_rook_square(OOO));
}
}
} // namespace
-/// generate<CAPTURES> generates all pseudo-legal captures and queen
-/// promotions. Returns a pointer to the end of the move list.
-///
-/// generate<QUIETS> generates all pseudo-legal non-captures and
-/// underpromotions. Returns a pointer to the end of the move list.
+/// <CAPTURES> Generates all pseudo-legal captures and queen promotions
+/// <QUIETS> Generates all pseudo-legal non-captures and underpromotions
+/// <NON_EVASIONS> Generates all pseudo-legal captures and non-captures
///
-/// generate<NON_EVASIONS> generates all pseudo-legal captures and
-/// non-captures. Returns a pointer to the end of the move list.
+/// Returns a pointer to the end of the move list.
template<GenType Type>
ExtMove* generate(const Position& pos, ExtMove* moveList) {
QSEARCH_TT, QCAPTURE_INIT, QCAPTURE, QCHECK_INIT, QCHECK
};
- // Helper filter used with select()
- const auto Any = [](){ return true; };
-
// partial_insertion_sort() sorts moves in descending order up to and including
// a given limit. The order of moves smaller than the limit is left unspecified.
void partial_insertion_sort(ExtMove* begin, ExtMove* end, int limit) {
assert(d <= DEPTH_ZERO);
stage = pos.checkers() ? EVASION_TT : QSEARCH_TT;
- ttMove = ttm
- && pos.pseudo_legal(ttm)
- && (depth > DEPTH_QS_RECAPTURES || to_sq(ttm) == recaptureSquare) ? ttm : MOVE_NONE;
+ ttMove = ttm
+ && (depth > DEPTH_QS_RECAPTURES || to_sq(ttm) == recaptureSquare)
+ && pos.pseudo_legal(ttm) ? ttm : MOVE_NONE;
stage += (ttMove == MOVE_NONE);
}
stage = PROBCUT_TT;
ttMove = ttm
- && pos.pseudo_legal(ttm)
&& pos.capture(ttm)
+ && pos.pseudo_legal(ttm)
&& pos.see_ge(ttm, threshold) ? ttm : MOVE_NONE;
stage += (ttMove == MOVE_NONE);
}
m.value = (*mainHistory)[pos.side_to_move()][from_to(m)]
+ (*continuationHistory[0])[pos.moved_piece(m)][to_sq(m)]
+ (*continuationHistory[1])[pos.moved_piece(m)][to_sq(m)]
- + (*continuationHistory[3])[pos.moved_piece(m)][to_sq(m)];
+ + (*continuationHistory[3])[pos.moved_piece(m)][to_sq(m)]
+ + (*continuationHistory[5])[pos.moved_piece(m)][to_sq(m)] / 2;
else // Type == EVASIONS
{
/* fallthrough */
case BAD_CAPTURE:
- return select<Next>(Any);
+ return select<Next>([](){ return true; });
case EVASION_INIT:
cur = moves;
/* fallthrough */
case EVASION:
- return select<Best>(Any);
+ return select<Best>([](){ return true; });
case PROBCUT:
return select<Best>([&](){ return pos.see_ge(move, threshold); });
/* fallthrough */
case QCHECK:
- return select<Next>(Any);
+ return select<Next>([](){ return true; });
}
assert(false);
/// ButterflyHistory records how often quiet moves have been successful or
/// unsuccessful during the current search, and is used for reduction and move
/// ordering decisions. It uses 2 tables (one for each color) indexed by
-/// the move's from and to squares, see chessprogramming.wikispaces.com/Butterfly+Boards
+/// the move's from and to squares, see www.chessprogramming.org/Butterfly_Boards
typedef Stats<int16_t, 10692, COLOR_NB, int(SQUARE_NB) * int(SQUARE_NB)> ButterflyHistory;
/// CounterMoveHistory stores counter moves indexed by [piece][to] of the previous
-/// move, see chessprogramming.wikispaces.com/Countermove+Heuristic
+/// move, see www.chessprogramming.org/Countermove_Heuristic
typedef Stats<Move, NOT_USED, PIECE_NB, SQUARE_NB> CounterMoveHistory;
/// CapturePieceToHistory is addressed by a move's [piece][to][captured piece type]
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include "bitboard.h"
constexpr Score Doubled = S(11, 56);
constexpr Score Isolated = S( 5, 15);
- // Connected pawn bonus by opposed, phalanx, #support and rank
- Score Connected[2][2][3][RANK_NB];
+ // Connected pawn bonus
+ constexpr int Connected[RANK_NB] = { 0, 13, 24, 18, 65, 100, 175, 330 };
// Strength of pawn shelter for our king by [distance from edge][rank].
// RANK_1 = 0 is used for files where we have no pawn, or pawn is behind our king.
// Flag the pawn
opposed = theirPawns & forward_file_bb(Us, s);
- stoppers = theirPawns & passed_pawn_mask(Us, s);
+ stoppers = theirPawns & passed_pawn_span(Us, s);
lever = theirPawns & PawnAttacks[Us][s];
leverPush = theirPawns & PawnAttacks[Us][s + Up];
doubled = ourPawns & (s - Up);
// which could become passed after one or two pawn pushes when are
// not attacked more times than defended.
if ( !(stoppers ^ lever ^ leverPush)
- && popcount(support) >= popcount(lever) - 1
- && popcount(phalanx) >= popcount(leverPush))
+ && (support || !more_than_one(lever))
+ && popcount(phalanx) >= popcount(leverPush))
e->passedPawns[Us] |= s;
- else if ( stoppers == SquareBB[s + Up]
+ else if ( stoppers == square_bb(s + Up)
&& relative_rank(Us, s) >= RANK_5)
{
b = shift<Up>(support) & ~theirPawns;
// Score this pawn
if (support | phalanx)
- score += Connected[opposed][bool(phalanx)][popcount(support)][relative_rank(Us, s)];
-
+ {
+ int r = relative_rank(Us, s);
+ int v = phalanx ? Connected[r] + Connected[r + 1] : 2 * Connected[r];
+ v = 17 * popcount(support) + (v >> (opposed + 1));
+ score += make_score(v, v * (r - 2) / 4);
+ }
else if (!neighbours)
score -= Isolated, e->weakUnopposed[Us] += !opposed;
namespace Pawns {
-/// Pawns::init() initializes some tables needed by evaluation. Instead of using
-/// hard-coded tables, when makes sense, we prefer to calculate them with a formula
-/// to reduce independent parameters and to allow easier tuning and better insight.
-
-void init() {
-
- static constexpr int Seed[RANK_NB] = { 0, 13, 24, 18, 65, 100, 175, 330 };
-
- for (int opposed = 0; opposed <= 1; ++opposed)
- for (int phalanx = 0; phalanx <= 1; ++phalanx)
- for (int support = 0; support <= 2; ++support)
- for (Rank r = RANK_2; r < RANK_8; ++r)
- {
- int v = 17 * support;
- v += (Seed[r] + (phalanx ? (Seed[r + 1] - Seed[r]) / 2 : 0)) >> opposed;
-
- Connected[opposed][phalanx][support][r] = make_score(v, v * (r - 2) / 4);
- }
-}
-
-
/// Pawns::probe() looks up the current position's pawns configuration in
/// the pawns hash table. It returns a pointer to the Entry if the position
/// is found. Otherwise a new Entry is computed and stored there, so we don't
e->key = key;
e->scores[WHITE] = evaluate<WHITE>(pos, e);
e->scores[BLACK] = evaluate<BLACK>(pos, e);
- e->openFiles = popcount(e->semiopenFiles[WHITE] & e->semiopenFiles[BLACK]);
- e->asymmetry = popcount( (e->passedPawns[WHITE] | e->passedPawns[BLACK])
- | (e->semiopenFiles[WHITE] ^ e->semiopenFiles[BLACK]));
+ e->passedCount= popcount(e->passedPawns[WHITE] | e->passedPawns[BLACK]);
return e;
}
Value safety = (shift<Down>(theirPawns) & (FileABB | FileHBB) & BlockRanks & ksq) ?
Value(374) : Value(5);
- File center = std::max(FILE_B, std::min(FILE_G, file_of(ksq)));
+ File center = clamp(file_of(ksq), FILE_B, FILE_G);
for (File f = File(center - 1); f <= File(center + 1); ++f)
{
b = ourPawns & file_bb(f);
Bitboard passed_pawns(Color c) const { return passedPawns[c]; }
Bitboard pawn_attacks_span(Color c) const { return pawnAttacksSpan[c]; }
int weak_unopposed(Color c) const { return weakUnopposed[c]; }
- int pawn_asymmetry() const { return asymmetry; }
- int open_files() const { return openFiles; }
+ int passed_count() const { return passedCount; }
int semiopen_file(Color c, File f) const {
return semiopenFiles[c] & (1 << f);
int castlingRights[COLOR_NB];
int semiopenFiles[COLOR_NB];
int pawnsOnSquares[COLOR_NB][COLOR_NB]; // [color][light/dark squares]
- int asymmetry;
- int openFiles;
+ int passedCount;
};
typedef HashTable<Entry, 16384> Table;
-void init();
Entry* probe(const Position& pos);
} // namespace Pawns
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include <cstddef> // For offsetof()
#include <cstring> // For std::memset, std::memcmp
{
std::swap(cuckoo[i], key);
std::swap(cuckooMove[i], move);
- if (move == 0) // Arrived at empty slot ?
+ if (move == MOVE_NONE) // Arrived at empty slot?
break;
i = (i == H1(key)) ? H2(key) : H1(key); // Push victim to alternative slot
}
Square kto = relative_square(c, cs == KING_SIDE ? SQ_G1 : SQ_C1);
Square rto = relative_square(c, cs == KING_SIDE ? SQ_F1 : SQ_D1);
- for (Square s = std::min(rfrom, rto); s <= std::max(rfrom, rto); ++s)
- if (s != kfrom && s != rfrom)
- castlingPath[cr] |= s;
-
- for (Square s = std::min(kfrom, kto); s <= std::max(kfrom, kto); ++s)
- if (s != kfrom && s != rfrom)
- castlingPath[cr] |= s;
+ castlingPath[cr] = (between_bb(rfrom, rto) | between_bb(kfrom, kto) | rto | kto)
+ & ~(square_bb(kfrom) | rfrom);
}
ss << (sideToMove == WHITE ? " w " : " b ");
if (can_castle(WHITE_OO))
- ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | KING_SIDE))) : 'K');
+ ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OO ))) : 'K');
if (can_castle(WHITE_OOO))
- ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE | QUEEN_SIDE))) : 'Q');
+ ss << (chess960 ? char('A' + file_of(castling_rook_square(WHITE_OOO))) : 'Q');
if (can_castle(BLACK_OO))
- ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | KING_SIDE))) : 'k');
+ ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OO ))) : 'k');
if (can_castle(BLACK_OOO))
- ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK | QUEEN_SIDE))) : 'q');
+ ss << (chess960 ? char('a' + file_of(castling_rook_square(BLACK_OOO))) : 'q');
if (!can_castle(ANY_CASTLING))
ss << '-';
Bitboard blockers = 0;
pinners = 0;
- // Snipers are sliders that attack 's' when a piece is removed
+ // Snipers are sliders that attack 's' when a piece and other snipers are removed
Bitboard snipers = ( (PseudoAttacks[ ROOK][s] & pieces(QUEEN, ROOK))
| (PseudoAttacks[BISHOP][s] & pieces(QUEEN, BISHOP))) & sliders;
+ Bitboard occupancy = pieces() & ~snipers;
while (snipers)
{
Square sniperSq = pop_lsb(&snipers);
- Bitboard b = between_bb(s, sniperSq) & pieces();
+ Bitboard b = between_bb(s, sniperSq) & occupancy;
if (b && !more_than_one(b))
{
Color us = sideToMove;
Square from = from_sq(m);
+ Square to = to_sq(m);
assert(color_of(moved_piece(m)) == us);
assert(piece_on(square<KING>(us)) == make_piece(us, KING));
if (type_of(m) == ENPASSANT)
{
Square ksq = square<KING>(us);
- Square to = to_sq(m);
Square capsq = to - pawn_push(us);
Bitboard occupied = (pieces() ^ from ^ capsq) | to;
&& !(attacks_bb<BISHOP>(ksq, occupied) & pieces(~us, QUEEN, BISHOP));
}
- // If the moving piece is a king, check whether the destination
- // square is attacked by the opponent. Castling moves are checked
- // for legality during move generation.
+ // Castling moves generation does not check if the castling path is clear of
+ // enemy attacks, it is delayed at a later time: now!
+ if (type_of(m) == CASTLING)
+ {
+ // After castling, the rook and king final positions are the same in
+ // Chess960 as they would be in standard chess.
+ to = relative_square(us, to > from ? SQ_G1 : SQ_C1);
+ Direction step = to > from ? WEST : EAST;
+
+ for (Square s = to; s != from; s += step)
+ if (attackers_to(s) & pieces(~us))
+ return false;
+
+ // In case of Chess960, verify that when moving the castling rook we do
+ // not discover some hidden checker.
+ // For instance an enemy queen in SQ_A1 when castling rook is in SQ_B1.
+ return !chess960
+ || !(attacks_bb<ROOK>(to, pieces() ^ to_sq(m)) & pieces(~us, ROOK, QUEEN));
+ }
+
+ // If the moving piece is a king, check whether the destination square is
+ // attacked by the opponent.
if (type_of(piece_on(from)) == KING)
- return type_of(m) == CASTLING || !(attackers_to(to_sq(m)) & pieces(~us));
+ return !(attackers_to(to) & pieces(~us));
// A non-king move is legal if and only if it is not pinned or it
// is moving along the ray towards or away from the king.
return !(blockers_for_king(us) & from)
- || aligned(from, to_sq(m), square<KING>(us));
+ || aligned(from, to, square<KING>(us));
}
{
// We have already handled promotion moves, so destination
// cannot be on the 8th/1st rank.
- if (rank_of(to) == relative_rank(us, RANK_8))
+ if ((Rank8BB | Rank1BB) & to)
return false;
if ( !(attacks_from<PAWN>(from, us) & pieces(~us) & to) // Not a capture
stmAttackers = attackers & pieces(stm);
// Don't allow pinned pieces to attack (except the king) as long as
- // all pinners are on their original square.
- if (!(st->pinners[~stm] & ~occupied))
+ // any pinners are on their original square.
+ if (st->pinners[~stm] & occupied)
stmAttackers &= ~st->blockersForKing[stm];
// If stm has no more attackers then give up: stm loses
}
inline int Position::castling_rights(Color c) const {
- return st->castlingRights & ((WHITE_OO | WHITE_OOO) << (2 * c));
+ return st->castlingRights & (c == WHITE ? WHITE_CASTLING : BLACK_CASTLING);
}
inline bool Position::castling_impeded(CastlingRight cr) const {
}
inline bool Position::pawn_passed(Color c, Square s) const {
- return !(pieces(~c, PAWN) & passed_pawn_mask(c, s));
+ return !(pieces(~c, PAWN) & passed_pawn_span(c, s));
}
inline bool Position::advanced_pawn_push(Move m) const {
// index[from] is not updated and becomes stale. This works as long as index[]
// is accessed just by known occupied squares.
- Bitboard fromTo = SquareBB[from] ^ SquareBB[to];
+ Bitboard fromTo = square_bb(from) | square_bb(to);
byTypeBB[ALL_PIECES] ^= fromTo;
byTypeBB[type_of(pc)] ^= fromTo;
byColorBB[color_of(pc)] ^= fromTo;
{ S(-48,-51), S( -3,-40), S(-12,-39), S(-25,-20) }
},
{ // Rook
- { S(-24, -2), S(-13,-6), S( -7, -3), S( 2,-2) },
- { S(-18,-10), S(-10,-7), S( -5, 1), S( 9, 0) },
- { S(-21, 10), S( -7,-4), S( 3, 2), S(-1,-2) },
- { S(-13, -5), S( -5, 2), S( -4, -8), S(-6, 8) },
- { S(-24, -8), S(-12, 5), S( -1, 4), S( 6,-9) },
- { S(-24, 3), S( -4,-2), S( 4,-10), S(10, 7) },
- { S( -8, 1), S( 6, 2), S( 10, 17), S(12,-8) },
- { S(-22, 12), S(-24,-6), S( -6, 13), S( 4, 7) }
+ { S(-24, -2), S(-13,-6), S(-7, -3), S( 2,-2) },
+ { S(-18,-10), S(-10,-7), S(-5, 1), S( 9, 0) },
+ { S(-21, 10), S( -7,-4), S( 3, 2), S(-1,-2) },
+ { S(-13, -5), S( -5, 2), S(-4, -8), S(-6, 8) },
+ { S(-24, -8), S(-12, 5), S(-1, 4), S( 6,-9) },
+ { S(-24, 3), S( -4,-2), S( 4,-10), S(10, 7) },
+ { S( -8, 1), S( 6, 2), S(10, 17), S(12,-8) },
+ { S(-22, 12), S(-24,-6), S(-6, 13), S( 4, 7) }
},
{ // Queen
- { S( 3,-69), S(-5,-57), S(-5,-47), S( 4,-26) },
- { S( -3,-55), S( 5,-31), S( 8,-22), S(12, -4) },
- { S( -3,-39), S( 6,-18), S(13, -9), S( 7, 3) },
- { S( 4,-23), S( 5, -3), S( 9, 13), S( 8, 24) },
- { S( 0,-29), S(14, -6), S(12, 9), S( 5, 21) },
- { S( -4,-38), S(10,-18), S( 6,-12), S( 8, 1) },
- { S( -5,-50), S( 6,-27), S(10,-24), S( 8, -8) },
- { S( -2,-75), S(-2,-52), S( 1,-43), S(-2,-36) }
+ { S( 3,-69), S(-5,-57), S(-5,-47), S( 4,-26) },
+ { S(-3,-55), S( 5,-31), S( 8,-22), S(12, -4) },
+ { S(-3,-39), S( 6,-18), S(13, -9), S( 7, 3) },
+ { S( 4,-23), S( 5, -3), S( 9, 13), S( 8, 24) },
+ { S( 0,-29), S(14, -6), S(12, 9), S( 5, 21) },
+ { S(-4,-38), S(10,-18), S( 6,-12), S( 8, 1) },
+ { S(-5,-50), S( 6,-27), S(10,-24), S( 8, -8) },
+ { S(-2,-75), S(-2,-52), S( 1,-43), S(-2,-36) }
},
{ // King
{ S(272, 0), S(325, 41), S(273, 80), S(190, 93) },
{ S(277, 57), S(305, 98), S(241,138), S(183,131) },
{ S(198, 86), S(253,138), S(168,165), S(120,173) },
{ S(169,103), S(191,152), S(136,168), S(108,169) },
- { S(145, 98), S(176,166), S(112,197), S(69, 194) },
- { S(122, 87), S(159,164), S(85, 174), S(36, 189) },
- { S(87, 40), S(120, 99), S(64, 128), S(25, 141) },
- { S(64, 5), S(87, 60), S(49, 75), S(0, 75) }
+ { S(145, 98), S(176,166), S(112,197), S( 69,194) },
+ { S(122, 87), S(159,164), S( 85,174), S( 36,189) },
+ { S( 87, 40), S(120, 99), S( 64,128), S( 25,141) },
+ { S( 64, 5), S( 87, 60), S( 49, 75), S( 0, 75) }
}
};
-constexpr Score PBonus[RANK_NB][FILE_NB] =\r
- { // Pawn\r
- { S( 0, 0), S( 0, 0), S( 0, 0), S( 0, 0), S( 0, 0), S( 0, 0), S( 0, 0), S( 0, 0) },\r
- { S( 0,-11), S( -3, -4), S( 13, -1), S( 19, -4), S( 16, 17), S( 13, 7), S( 4, 4), S( -4,-13) },\r
- { S(-16, -8), S(-12, -6), S( 20, -3), S( 21, 0), S( 25,-11), S( 29, 3), S( 0, 0), S(-27, -1) },\r
- { S(-11, 3), S(-17, 6), S( 11,-10), S( 21, 1), S( 32, -6), S( 19,-11), S( -5, 0), S(-14, -2) },\r
- { S( 4, 13), S( 6, 7), S( -8, 3), S( 3, -5), S( 8,-15), S( -2, -1), S(-19, 9), S( -5, 13) },\r
- { S( -5, 25), S(-19, 20), S( 7, 16), S( 8, 12), S( -7, 21), S( -2, 3), S(-10, -4), S(-16, 15) },\r
- { S(-10, 6), S( 9, -5), S( -7, 16), S(-12, 27), S( -7, 15), S( -8, 11), S( 16, -7), S( -8, 4) }\r
+constexpr Score PBonus[RANK_NB][FILE_NB] =
+ { // Pawn (asymmetric distribution)
+ { },
+ { S( 0,-10), S( -5,-3), S( 10, 7), S( 13,-1), S( 21, 7), S( 17, 6), S( 6, 1), S( -3,-20) },
+ { S(-11, -6), S(-10,-6), S( 15,-1), S( 22,-1), S( 26, -1), S( 28, 2), S( 4,-2), S(-24, -5) },
+ { S( -9, 4), S(-18,-5), S( 8,-4), S( 22,-5), S( 33, -6), S( 25,-13), S( -4,-3), S(-16, -7) },
+ { S( 6, 18), S( -3, 2), S(-10, 2), S( 1,-9), S( 12,-13), S( 6, -8), S(-12,11), S( 1, 9) },
+ { S( -6, 25), S( -8,17), S( 5,19), S( 11,29), S(-14, 29), S( 0, 8), S(-12, 4), S(-14, 12) },
+ { S(-10, -1), S( 6,-6), S( -5,18), S(-11,22), S( -2, 22), S(-14, 17), S( 12, 2), S( -1, 9) }
};
#undef S
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstring> // For std::memset
// Different node types, used as a template parameter
enum NodeType { NonPV, PV };
- // Sizes and phases of the skip-blocks, used for distributing search depths across the threads
- constexpr int SkipSize[] = { 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4 };
- constexpr int SkipPhase[] = { 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7 };
-
// Razor and futility margins
constexpr int RazorMargin = 600;
Value futility_margin(Depth d, bool improving) {
return Value((175 - 50 * improving) * d / ONE_PLY);
}
- // Futility and reductions lookup tables, initialized at startup
- int FutilityMoveCounts[2][16]; // [improving][depth]
- int Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber]
+ // Reductions lookup table, initialized at startup
+ int Reductions[64]; // [depth or moveNumber]
template <bool PvNode> Depth reduction(bool i, Depth d, int mn) {
- return Reductions[PvNode][i][std::min(d / ONE_PLY, 63)][std::min(mn, 63)] * ONE_PLY;
+ int r = Reductions[std::min(d / ONE_PLY, 63)] * Reductions[std::min(mn, 63)] / 1024;
+ return ((r + 512) / 1024 + (!i && r > 1024) - PvNode) * ONE_PLY;
+ }
+
+ constexpr int futility_move_count(bool improving, int depth) {
+ return (5 + depth * depth) * (1 + improving) / 2;
}
// History and stats update bonus, based on depth
return d > 17 ? 0 : 29 * d * d + 138 * d - 134;
}
- // Add a small random component to draw evaluations to keep search dynamic
- // and to avoid 3fold-blindness.
+ // Add a small random component to draw evaluations to avoid 3fold-blindness
Value value_draw(Depth depth, Thread* thisThread) {
- return depth < 4 ? VALUE_DRAW
- : VALUE_DRAW + Value(2 * (thisThread->nodes.load(std::memory_order_relaxed) % 2) - 1);
+ return depth < 4 * ONE_PLY ? VALUE_DRAW
+ : VALUE_DRAW + Value(2 * (thisThread->nodes & 1) - 1);
}
// Skill structure is used to implement strength limit
Value value_from_tt(Value v, int ply);
void update_pv(Move* pv, Move move, Move* childPv);
void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus);
- void update_quiet_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietsCnt, int bonus);
- void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCnt, int bonus);
-
- inline bool gives_check(const Position& pos, Move move) {
- Color us = pos.side_to_move();
- return type_of(move) == NORMAL && !(pos.blockers_for_king(~us) & pos.pieces(us))
- ? pos.check_squares(type_of(pos.moved_piece(move))) & to_sq(move)
- : pos.gives_check(move);
- }
+ void update_quiet_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietCount, int bonus);
+ void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCount, int bonus);
// perft() is our utility to verify move generation. All the leaf nodes up
// to the given depth are generated and counted, and the sum is returned.
void Search::init() {
- for (int imp = 0; imp <= 1; ++imp)
- for (int d = 1; d < 64; ++d)
- for (int mc = 1; mc < 64; ++mc)
- {
- double r = log(d) * log(mc) / 1.95;
-
- Reductions[NonPV][imp][d][mc] = int(std::round(r));
- Reductions[PV][imp][d][mc] = std::max(Reductions[NonPV][imp][d][mc] - 1, 0);
-
- // Increase reduction for non-PV nodes when eval is not improving
- if (!imp && r > 1.0)
- Reductions[NonPV][imp][d][mc]++;
- }
-
- for (int d = 0; d < 16; ++d)
- {
- FutilityMoveCounts[0][d] = int(2.4 + 0.74 * pow(d, 1.78));
- FutilityMoveCounts[1][d] = int(5.0 + 1.00 * pow(d, 2.00));
- }
+ for (int i = 1; i < 64; ++i)
+ Reductions[i] = int(1024 * std::log(i) / std::sqrt(1.95));
}
Time.availableNodes = 0;
TT.clear();
Threads.clear();
- Tablebases::init(Options["SyzygyPath"]); // Free up mapped files
+ Tablebases::init(Options["SyzygyPath"]); // Free mapped files
}
-/// MainThread::search() is called by the main thread when the program receives
-/// the UCI 'go' command. It searches from the root position and outputs the "bestmove".
+/// MainThread::search() is started when the program receives the UCI 'go'
+/// command. It searches from the root position and outputs the "bestmove".
void MainThread::search() {
else
{
for (Thread* th : Threads)
+ {
+ th->bestMoveChanges = 0;
if (th != this)
th->start_searching();
+ }
Thread::search(); // Let's start searching!
}
// Threads.stop. However, if we are pondering or in an infinite search,
// the UCI protocol states that we shouldn't print the best move before the
// GUI sends a "stop" or "ponderhit" command. We therefore simply wait here
- // until the GUI sends one of those commands (which also raises Threads.stop).
- Threads.stopOnPonderhit = true;
+ // until the GUI sends one of those commands.
- while (!Threads.stop && (Threads.ponder || Limits.infinite))
+ while (!Threads.stop && (ponder || Limits.infinite))
{} // Busy wait for a stop or a ponder reset
// Stop the threads if not already stopped (also raise the stop if
if (Limits.npmsec)
Time.availableNodes += Limits.inc[us] - Threads.nodes_searched();
- // Check if there are threads with a better score than main thread
Thread* bestThread = this;
+
+ // Check if there are threads with a better score than main thread
if ( Options["MultiPV"] == 1
&& !Limits.depth
&& !Skill(Options["Skill Level"]).enabled()
// Find out minimum score and reset votes for moves which can be voted
for (Thread* th: Threads)
- {
minScore = std::min(minScore, th->rootMoves[0].score);
- votes[th->rootMoves[0].pv[0]] = 0;
- }
// Vote according to score and depth
- auto square = [](int64_t x) { return x * x; };
for (Thread* th : Threads)
- votes[th->rootMoves[0].pv[0]] += 200 + (square(th->rootMoves[0].score - minScore + 1)
- * int64_t(th->completedDepth));
+ {
+ int64_t s = th->rootMoves[0].score - minScore + 1;
+ votes[th->rootMoves[0].pv[0]] += 200 + s * s * int(th->completedDepth);
+ }
// Select best thread
- int64_t bestVote = votes[this->rootMoves[0].pv[0]];
+ auto bestVote = votes[this->rootMoves[0].pv[0]];
for (Thread* th : Threads)
- {
if (votes[th->rootMoves[0].pv[0]] > bestVote)
{
bestVote = votes[th->rootMoves[0].pv[0]];
bestThread = th;
}
- }
}
previousScore = bestThread->rootMoves[0].score;
void Thread::search() {
- // To allow access to (ss-5) up to (ss+2), the stack must be oversized.
+ // To allow access to (ss-7) up to (ss+2), the stack must be oversized.
// The former is needed to allow update_continuation_histories(ss-1, ...),
- // which accesses its argument at ss-4, also near the root.
+ // which accesses its argument at ss-6, also near the root.
// The latter is needed for statScores and killer initialization.
- Stack stack[MAX_PLY+8], *ss = stack+5;
+ Stack stack[MAX_PLY+10], *ss = stack+7;
Move pv[MAX_PLY+1];
Value bestValue, alpha, beta, delta;
Move lastBestMove = MOVE_NONE;
Depth lastBestMoveDepth = DEPTH_ZERO;
MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr);
- double timeReduction = 1.0;
+ double timeReduction = 1, totBestMoveChanges = 0;
Color us = rootPos.side_to_move();
- bool failedLow;
- std::memset(ss-5, 0, 8 * sizeof(Stack));
- for (int i = 5; i > 0; i--)
+ std::memset(ss-7, 0, 10 * sizeof(Stack));
+ for (int i = 7; i > 0; i--)
(ss-i)->continuationHistory = &this->continuationHistory[NO_PIECE][0]; // Use as sentinel
ss->pv = pv;
bestValue = delta = alpha = -VALUE_INFINITE;
beta = VALUE_INFINITE;
- if (mainThread)
- mainThread->bestMoveChanges = 0, failedLow = false;
-
size_t multiPV = Options["MultiPV"];
Skill skill(Options["Skill Level"]);
: Options["Analysis Contempt"] == "Black" && us == WHITE ? -ct
: ct;
- // In evaluate.cpp the evaluation is from the white point of view
+ // Evaluation score is from the white point of view
contempt = (us == WHITE ? make_score(ct, ct / 2)
: -make_score(ct, ct / 2));
&& !Threads.stop
&& !(Limits.depth && mainThread && rootDepth / ONE_PLY > Limits.depth))
{
- // Distribute search depths across the helper threads
- if (idx > 0)
- {
- int i = (idx - 1) % 20;
- if (((rootDepth / ONE_PLY + SkipPhase[i]) / SkipSize[i]) % 2)
- continue; // Retry with an incremented rootDepth
- }
-
// Age out PV variability metric
if (mainThread)
- mainThread->bestMoveChanges *= 0.517, failedLow = false;
+ totBestMoveChanges /= 2;
// Save the last iteration's scores before first PV line is searched and
// all the move scores except the (new) PV are set to -VALUE_INFINITE.
if (mainThread)
{
failedHighCnt = 0;
- failedLow = true;
- Threads.stopOnPonderhit = false;
+ mainThread->stopOnPonderhit = false;
}
}
else if (bestValue >= beta)
// Do we have time for the next iteration? Can we stop searching now?
if ( Limits.use_time_management()
&& !Threads.stop
- && !Threads.stopOnPonderhit)
+ && !mainThread->stopOnPonderhit)
+ {
+ double fallingEval = (314 + 9 * (mainThread->previousScore - bestValue)) / 581.0;
+ fallingEval = clamp(fallingEval, 0.5, 1.5);
+
+ // If the bestMove is stable over several iterations, reduce time accordingly
+ timeReduction = lastBestMoveDepth + 10 * ONE_PLY < completedDepth ? 1.95 : 1.0;
+ double reduction = std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction;
+
+ // Use part of the gained time from a previous stable move for the current move
+ for (Thread* th : Threads)
{
- double fallingEval = (306 + 119 * failedLow + 6 * (mainThread->previousScore - bestValue)) / 581.0;
- fallingEval = std::max(0.5, std::min(1.5, fallingEval));
-
- // If the bestMove is stable over several iterations, reduce time accordingly
- timeReduction = 1.0;
- for (int i : {3, 4, 5})
- if (lastBestMoveDepth * i < completedDepth)
- timeReduction *= 1.25;
-
- // Use part of the gained time from a previous stable move for the current move
- double bestMoveInstability = 1.0 + mainThread->bestMoveChanges;
- bestMoveInstability *= std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction;
-
- // Stop the search if we have only one legal move, or if available time elapsed
- if ( rootMoves.size() == 1
- || Time.elapsed() > Time.optimum() * bestMoveInstability * fallingEval)
- {
- // If we are allowed to ponder do not stop the search now but
- // keep pondering until the GUI sends "ponderhit" or "stop".
- if (Threads.ponder)
- Threads.stopOnPonderhit = true;
- else
- Threads.stop = true;
- }
+ totBestMoveChanges += th->bestMoveChanges;
+ th->bestMoveChanges = 0;
}
+ double bestMoveInstability = 1 + totBestMoveChanges / Threads.size();
+
+ // Stop the search if we have only one legal move, or if available time elapsed
+ if ( rootMoves.size() == 1
+ || Time.elapsed() > Time.optimum() * fallingEval * reduction * bestMoveInstability)
+ {
+ // If we are allowed to ponder do not stop the search now but
+ // keep pondering until the GUI sends "ponderhit" or "stop".
+ if (mainThread->ponder)
+ mainThread->stopOnPonderhit = true;
+ else
+ Threads.stop = true;
+ }
+ }
}
if (!mainThread)
Key posKey;
Move ttMove, move, excludedMove, bestMove;
Depth extension, newDepth;
- Value bestValue, value, ttValue, eval, maxValue, pureStaticEval;
- bool ttHit, inCheck, givesCheck, improving;
- bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact;
+ Value bestValue, value, ttValue, eval, maxValue;
+ bool ttHit, ttPv, inCheck, givesCheck, improving;
+ bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture;
Piece movedPiece;
int moveCount, captureCount, quietCount;
ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
: ttHit ? tte->move() : MOVE_NONE;
+ ttPv = (ttHit && tte->is_pv()) || (PvNode && depth > 4 * ONE_PLY);
// At non-PV nodes we check for an early TT cutoff
if ( !PvNode
if ( b == BOUND_EXACT
|| (b == BOUND_LOWER ? value >= beta : value <= alpha))
{
- tte->save(posKey, value_to_tt(value, ss->ply), b,
+ tte->save(posKey, value_to_tt(value, ss->ply), ttPv, b,
std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY),
MOVE_NONE, VALUE_NONE);
// Step 6. Static evaluation of the position
if (inCheck)
{
- ss->staticEval = eval = pureStaticEval = VALUE_NONE;
+ ss->staticEval = eval = VALUE_NONE;
improving = false;
goto moves_loop; // Skip early pruning when in check
}
else if (ttHit)
{
// Never assume anything on values stored in TT
- ss->staticEval = eval = pureStaticEval = tte->eval();
+ ss->staticEval = eval = tte->eval();
if (eval == VALUE_NONE)
- ss->staticEval = eval = pureStaticEval = evaluate(pos);
+ ss->staticEval = eval = evaluate(pos);
// Can ttValue be used as a better position evaluation?
if ( ttValue != VALUE_NONE
{
if ((ss-1)->currentMove != MOVE_NULL)
{
- int p = (ss-1)->statScore;
- int bonus = p > 0 ? (-p - 2500) / 512 :
- p < 0 ? (-p + 2500) / 512 : 0;
+ int bonus = -(ss-1)->statScore / 512;
- pureStaticEval = evaluate(pos);
- ss->staticEval = eval = pureStaticEval + bonus;
+ ss->staticEval = eval = evaluate(pos) + bonus;
}
else
- ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo;
+ ss->staticEval = eval = -(ss-1)->staticEval + 2 * Eval::Tempo;
- tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval);
+ tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval);
}
// Step 7. Razoring (~2 Elo)
&& (ss-1)->currentMove != MOVE_NULL
&& (ss-1)->statScore < 23200
&& eval >= beta
- && pureStaticEval >= beta - 36 * depth / ONE_PLY + 225
+ && ss->staticEval >= beta - 36 * depth / ONE_PLY + 225
&& !excludedMove
&& pos.non_pawn_material(us)
&& (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor))
// Do verification search at high depths, with null move pruning disabled
// for us, until ply exceeds nmpMinPly.
- thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / 4;
+ thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / (4 * ONE_PLY);
thisThread->nmpColor = us;
Value v = search<NonPV>(pos, ss, beta-1, beta, depth-R, false);
int probCutCount = 0;
while ( (move = mp.next_move()) != MOVE_NONE
- && probCutCount < 3)
+ && probCutCount < 2 + 2 * cutNode)
if (move != excludedMove && pos.legal(move))
{
probCutCount++;
// Perform a preliminary qsearch to verify that the move holds
value = -qsearch<NonPV>(pos, ss+1, -raisedBeta, -raisedBeta+1);
- // If the qsearch held perform the regular search
+ // If the qsearch held, perform the regular search
if (value >= raisedBeta)
value = -search<NonPV>(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4 * ONE_PLY, !cutNode);
}
// Step 11. Internal iterative deepening (~2 Elo)
- if ( depth >= 8 * ONE_PLY
- && !ttMove)
+ if (depth >= 8 * ONE_PLY && !ttMove)
{
search<NT>(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode);
moves_loop: // When in check, search starts from here
- const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory };
+ const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
+ nullptr, (ss-4)->continuationHistory,
+ nullptr, (ss-6)->continuationHistory };
+
Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq];
MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory,
contHist,
countermove,
ss->killers);
- value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
- skipQuiets = false;
+ value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc
+ moveCountPruning = false;
ttCapture = ttMove && pos.capture_or_promotion(ttMove);
- pvExact = PvNode && ttHit && tte->bound() == BOUND_EXACT;
// Step 12. Loop through all pseudo-legal moves until no moves remain
// or a beta cutoff occurs.
- while ((move = mp.next_move(skipQuiets)) != MOVE_NONE)
+ while ((move = mp.next_move(moveCountPruning)) != MOVE_NONE)
{
assert(is_ok(move));
extension = DEPTH_ZERO;
captureOrPromotion = pos.capture_or_promotion(move);
movedPiece = pos.moved_piece(move);
- givesCheck = gives_check(pos, move);
-
- moveCountPruning = depth < 16 * ONE_PLY
- && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY];
+ givesCheck = pos.gives_check(move);
// Step 13. Extensions (~70 Elo)
&& move == ttMove
&& !rootNode
&& !excludedMove // Avoid recursive singular search
- && ttValue != VALUE_NONE
+ /* && ttValue != VALUE_NONE Already implicit in the next condition */
+ && abs(ttValue) < VALUE_KNOWN_WIN
&& (tte->bound() & BOUND_LOWER)
&& tte->depth() >= depth - 3 * ONE_PLY
&& pos.legal(move))
{
- Value reducedBeta = std::max(ttValue - 2 * depth / ONE_PLY, -VALUE_MATE);
+ Value singularBeta = ttValue - 2 * depth / ONE_PLY;
+ Depth halfDepth = depth / (2 * ONE_PLY) * ONE_PLY; // ONE_PLY invariant
ss->excludedMove = move;
- value = search<NonPV>(pos, ss, reducedBeta - 1, reducedBeta, depth / 2, cutNode);
+ value = search<NonPV>(pos, ss, singularBeta - 1, singularBeta, halfDepth, cutNode);
ss->excludedMove = MOVE_NONE;
- if (value < reducedBeta)
+ if (value < singularBeta)
extension = ONE_PLY;
+
+ // Multi-cut pruning
+ // Our ttMove is assumed to fail high, and now we failed high also on a reduced
+ // search without the ttMove. So we assume this expected Cut-node is not singular,
+ // that is multiple moves fail high, and we can prune the whole subtree by returning
+ // the hard beta bound.
+ else if (cutNode && singularBeta > beta)
+ return beta;
}
- else if ( givesCheck // Check extension (~2 Elo)
- && pos.see_ge(move))
+
+ // Check extension (~2 Elo)
+ else if ( givesCheck
+ && (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move)))
extension = ONE_PLY;
- // Extension if castling
+ // Castling extension
else if (type_of(move) == CASTLING)
extension = ONE_PLY;
+ // Passed pawn extension
+ else if ( move == ss->killers[0]
+ && pos.advanced_pawn_push(move)
+ && pos.pawn_passed(us, to_sq(move)))
+ extension = ONE_PLY;
+
// Calculate new depth for this move
newDepth = depth - ONE_PLY + extension;
&& pos.non_pawn_material(us)
&& bestValue > VALUE_MATED_IN_MAX_PLY)
{
+ // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold
+ moveCountPruning = moveCount >= futility_move_count(improving, depth / ONE_PLY);
+
if ( !captureOrPromotion
&& !givesCheck
&& !pos.advanced_pawn_push(move))
{
// Move count based pruning (~30 Elo)
if (moveCountPruning)
- {
- skipQuiets = true;
continue;
- }
// Reduced depth of the next LMR search
- int lmrDepth = std::max(newDepth - reduction<PvNode>(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY;
+ int lmrDepth = std::max(newDepth - reduction<PvNode>(improving, depth, moveCount), DEPTH_ZERO);
+ lmrDepth /= ONE_PLY;
// Countermoves based pruning (~20 Elo)
if ( lmrDepth < 3 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1)
if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth)))
continue;
}
- else if ( !extension // (~20 Elo)
- && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY)))
+ else if (!pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo)
continue;
}
{
Depth r = reduction<PvNode>(improving, depth, moveCount);
+ // Decrease reduction if position is or has been on the PV
+ if (ttPv)
+ r -= ONE_PLY;
+
// Decrease reduction if opponent's move count is high (~10 Elo)
if ((ss-1)->moveCount > 15)
r -= ONE_PLY;
if (!captureOrPromotion)
{
- // Decrease reduction for exact PV nodes (~0 Elo)
- if (pvExact)
- r -= ONE_PLY;
-
// Increase reduction if ttMove is a capture (~0 Elo)
if (ttCapture)
r += ONE_PLY;
// We record how often the best move has been changed in each
// iteration. This information is used for time management: When
// the best move changes frequently, we allocate some more time.
- if (moveCount > 1 && thisThread == Threads.main())
- ++static_cast<MainThread*>(thisThread)->bestMoveChanges;
+ if (moveCount > 1)
+ ++thisThread->bestMoveChanges;
}
else
// All other moves but the PV are set to the lowest value: this
bestValue = std::min(bestValue, maxValue);
if (!excludedMove)
- tte->save(posKey, value_to_tt(bestValue, ss->ply),
+ tte->save(posKey, value_to_tt(bestValue, ss->ply), ttPv,
bestValue >= beta ? BOUND_LOWER :
PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
- depth, bestMove, pureStaticEval);
+ depth, bestMove, ss->staticEval);
assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
Move ttMove, move, bestMove;
Depth ttDepth;
Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
- bool ttHit, inCheck, givesCheck, evasionPrunable;
+ bool ttHit, pvHit, inCheck, givesCheck, evasionPrunable;
int moveCount;
if (PvNode)
tte = TT.probe(posKey, ttHit);
ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
ttMove = ttHit ? tte->move() : MOVE_NONE;
+ pvHit = ttHit && tte->is_pv();
if ( !PvNode
&& ttHit
if (bestValue >= beta)
{
if (!ttHit)
- tte->save(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER,
+ tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, BOUND_LOWER,
DEPTH_NONE, MOVE_NONE, ss->staticEval);
return bestValue;
futilityBase = bestValue + 128;
}
- const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, nullptr, (ss-4)->continuationHistory };
+ const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,
+ nullptr, (ss-4)->continuationHistory,
+ nullptr, (ss-6)->continuationHistory };
// Initialize a MovePicker object for the current position, and prepare
// to search the moves. Because the depth is <= 0 here, only captures,
{
assert(is_ok(move));
- givesCheck = gives_check(pos, move);
+ givesCheck = pos.gives_check(move);
moveCount++;
if (inCheck && bestValue == -VALUE_INFINITE)
return mated_in(ss->ply); // Plies to mate from the root
- tte->save(posKey, value_to_tt(bestValue, ss->ply),
+ tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit,
bestValue >= beta ? BOUND_LOWER :
PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
ttDepth, bestMove, ss->staticEval);
void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) {
- for (int i : {1, 2, 4})
+ for (int i : {1, 2, 4, 6})
if (is_ok((ss-i)->currentMove))
(*(ss-i)->continuationHistory)[pc][to] << bonus;
}
// update_capture_stats() updates move sorting heuristics when a new capture best move is found
void update_capture_stats(const Position& pos, Move move,
- Move* captures, int captureCnt, int bonus) {
+ Move* captures, int captureCount, int bonus) {
CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory;
Piece moved_piece = pos.moved_piece(move);
captureHistory[moved_piece][to_sq(move)][captured] << bonus;
// Decrease all the other played capture moves
- for (int i = 0; i < captureCnt; ++i)
+ for (int i = 0; i < captureCount; ++i)
{
moved_piece = pos.moved_piece(captures[i]);
captured = type_of(pos.piece_on(to_sq(captures[i])));
// update_quiet_stats() updates move sorting heuristics when a new quiet best move is found
void update_quiet_stats(const Position& pos, Stack* ss, Move move,
- Move* quiets, int quietsCnt, int bonus) {
+ Move* quiets, int quietCount, int bonus) {
if (ss->killers[0] != move)
{
}
// Decrease all the other played quiet moves
- for (int i = 0; i < quietsCnt; ++i)
+ for (int i = 0; i < quietCount; ++i)
{
thisThread->mainHistory[us][from_to(quiets[i])] << -bonus;
update_continuation_histories(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus);
}
// We should not stop pondering until told so by the GUI
- if (Threads.ponder)
+ if (ponder)
return;
- if ( (Limits.use_time_management() && elapsed > Time.maximum() - 10)
+ if ( (Limits.use_time_management() && (elapsed > Time.maximum() - 10 || stopOnPonderhit))
|| (Limits.movetime && elapsed >= Limits.movetime)
|| (Limits.nodes && Threads.nodes_searched() >= (uint64_t)Limits.nodes))
Threads.stop = true;
assert(pv.size() == 1);
- if (!pv[0])
+ if (pv[0] == MOVE_NONE)
return false;
pos.do_move(pv[0], st);
/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (c) 2013 Ronald de Man
- Copyright (C) 2016-2018 Marco Costalba, Lucas Braesch
+ Copyright (C) 2016-2019 Marco Costalba, Lucas Braesch
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
#include "../movegen.h"
#include "../position.h"
#include "../search.h"
-#include "../thread_win32.h"
+#include "../thread_win32_osx.h"
#include "../types.h"
#include "../uci.h"
return *baseAddress = nullptr, nullptr;
fstat(fd, &statbuf);
+
+ if (statbuf.st_size % 64 != 16)
+ {
+ std::cerr << "Corrupt tablebase file " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
*mapping = statbuf.st_size;
*baseAddress = mmap(nullptr, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0);
madvise(*baseAddress, statbuf.st_size, MADV_RANDOM);
::close(fd);
- if (*baseAddress == MAP_FAILED) {
+ if (*baseAddress == MAP_FAILED)
+ {
std::cerr << "Could not mmap() " << fname << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
#else
// Note FILE_FLAG_RANDOM_ACCESS is only a hint to Windows and as such may get ignored.
DWORD size_high;
DWORD size_low = GetFileSize(fd, &size_high);
+
+ if (size_low % 64 != 16)
+ {
+ std::cerr << "Corrupt tablebase file " << fname << std::endl;
+ exit(EXIT_FAILURE);
+ }
+
HANDLE mmap = CreateFileMapping(fd, nullptr, PAGE_READONLY, size_high, size_low, nullptr);
CloseHandle(fd);
- if (!mmap) {
+ if (!mmap)
+ {
std::cerr << "CreateFileMapping() failed" << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
*mapping = (uint64_t)mmap;
*baseAddress = MapViewOfFile(mmap, FILE_MAP_READ, 0, 0, 0);
- if (!*baseAddress) {
+ if (!*baseAddress)
+ {
std::cerr << "MapViewOfFile() failed, name = " << fname
<< ", error = " << GetLastError() << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
#endif
uint8_t* data = (uint8_t*)*baseAddress;
constexpr uint8_t Magics[][4] = { { 0xD7, 0x66, 0x0C, 0xA5 },
{ 0x71, 0xE8, 0x23, 0x5D } };
- if (memcmp(data, Magics[type == WDL], 4)) {
+ if (memcmp(data, Magics[type == WDL], 4))
+ {
std::cerr << "Corrupted table in file " << fname << std::endl;
unmap(*baseAddress, *mapping);
return *baseAddress = nullptr, nullptr;
}
}
std::cerr << "TB hash table size too low!" << std::endl;
- exit(1);
+ exit(EXIT_FAILURE);
}
public:
/*
Stockfish, a UCI chess playing engine derived from Glaurung 2.1
Copyright (c) 2013 Ronald de Man
- Copyright (C) 2016-2018 Marco Costalba, Lucas Braesch
+ Copyright (C) 2016-2019 Marco Costalba, Lucas Braesch
Stockfish is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm> // For std::count
#include <cassert>
#include "movegen.h"
/// Thread constructor launches the thread and waits until it goes to sleep
-/// in idle_loop(). Note that 'searching' and 'exit' should be alredy set.
+/// in idle_loop(). Note that 'searching' and 'exit' should be already set.
Thread::Thread(size_t n) : idx(n), stdThread(&Thread::idle_loop, this) {
main()->wait_for_search_finished();
- stopOnPonderhit = stop = false;
- ponder = ponderMode;
+ main()->stopOnPonderhit = stop = false;
+ main()->ponder = ponderMode;
Search::Limits = limits;
Search::RootMoves rootMoves;
#include "pawns.h"
#include "position.h"
#include "search.h"
-#include "thread_win32.h"
+#include "thread_win32_osx.h"
/// Thread class keeps together all the thread-related stuff. We use
ConditionVariable cv;
size_t idx;
bool exit = false, searching = true; // Set before starting std::thread
- std::thread stdThread;
+ NativeThread stdThread;
public:
explicit Thread(size_t);
size_t pvIdx, pvLast;
int selDepth, nmpMinPly;
Color nmpColor;
- std::atomic<uint64_t> nodes, tbHits;
+ std::atomic<uint64_t> nodes, tbHits, bestMoveChanges;
Position rootPos;
Search::RootMoves rootMoves;
void search() override;
void check_time();
- double bestMoveChanges, previousTimeReduction;
+ double previousTimeReduction;
Value previousScore;
int callsCnt;
+ bool stopOnPonderhit;
+ std::atomic_bool ponder;
};
uint64_t nodes_searched() const { return accumulate(&Thread::nodes); }
uint64_t tb_hits() const { return accumulate(&Thread::tbHits); }
- std::atomic_bool stop, ponder, stopOnPonderhit;
+ std::atomic_bool stop;
private:
StateListPtr setupStates;
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#ifndef THREAD_WIN32_H_INCLUDED
-#define THREAD_WIN32_H_INCLUDED
+#ifndef THREAD_WIN32_OSX_H_INCLUDED
+#define THREAD_WIN32_OSX_H_INCLUDED
/// STL thread library used by mingw and gcc when cross compiling for Windows
/// relies on libwinpthread. Currently libwinpthread implements mutexes directly
#include <condition_variable>
#include <mutex>
+#include <thread>
#if defined(_WIN32) && !defined(_MSC_VER)
#endif
-#endif // #ifndef THREAD_WIN32_H_INCLUDED
+/// On OSX threads other than the main thread are created with a reduced stack
+/// size of 512KB by default, this is dangerously low for deep searches, so
+/// adjust it to TH_STACK_SIZE. The implementation calls pthread_create() with
+/// proper stack size parameter.
+
+#if defined(__APPLE__)
+
+#include <pthread.h>
+
+static const size_t TH_STACK_SIZE = 2 * 1024 * 1024;
+
+template <class T, class P = std::pair<T*, void(T::*)()>>
+void* start_routine(void* ptr)
+{
+ P* p = reinterpret_cast<P*>(ptr);
+ (p->first->*(p->second))(); // Call member function pointer
+ delete p;
+ return NULL;
+}
+
+class NativeThread {
+
+ pthread_t thread;
+
+public:
+ template<class T, class P = std::pair<T*, void(T::*)()>>
+ explicit NativeThread(void(T::*fun)(), T* obj) {
+ pthread_attr_t attr_storage, *attr = &attr_storage;
+ pthread_attr_init(attr);
+ pthread_attr_setstacksize(attr, TH_STACK_SIZE);
+ pthread_create(&thread, attr, start_routine<T>, new P(obj, fun));
+ }
+ void join() { pthread_join(thread, NULL); }
+};
+
+#else // Default case: use STL classes
+
+typedef std::thread NativeThread;
+
+#endif
+
+#endif // #ifndef THREAD_WIN32_OSX_H_INCLUDED
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cfloat>
#include <cmath>
TranspositionTable TT; // Our global transposition table
-/// TTEntry::save saves a TTEntry
-void TTEntry::save(Key k, Value v, Bound b, Depth d, Move m, Value ev) {
+/// TTEntry::save populates the TTEntry with a new node's data, possibly
+/// overwriting an old position. Update is not atomic and can be racy.
+
+void TTEntry::save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev) {
assert(d / ONE_PLY * ONE_PLY == d);
key16 = (uint16_t)(k >> 48);
value16 = (int16_t)v;
eval16 = (int16_t)ev;
- genBound8 = (uint8_t)(TT.generation8 | b);
+ genBound8 = (uint8_t)(TT.generation8 | uint8_t(pv) << 2 | b);
depth8 = (int8_t)(d / ONE_PLY);
}
}
for (int i = 0; i < ClusterSize; ++i)
if (!tte[i].key16 || tte[i].key16 == key16)
{
- tte[i].genBound8 = uint8_t(generation8 | tte[i].bound()); // Refresh
+ tte[i].genBound8 = uint8_t(generation8 | (tte[i].genBound8 & 0x7)); // Refresh
return found = (bool)tte[i].key16, &tte[i];
}
TTEntry* replace = tte;
for (int i = 1; i < ClusterSize; ++i)
// Due to our packed storage format for generation and its cyclic
- // nature we add 259 (256 is the modulus plus 3 to keep the lowest
- // two bound bits from affecting the result) to calculate the entry
+ // nature we add 263 (256 is the modulus plus 7 to keep the unrelated
+ // lowest three bits from affecting the result) to calculate the entry
// age correctly even after generation8 overflows into the next cycle.
- if ( replace->depth8 - ((259 + generation8 - replace->genBound8) & 0xFC) * 2
- > tte[i].depth8 - ((259 + generation8 - tte[i].genBound8) & 0xFC) * 2)
+ if ( replace->depth8 - ((263 + generation8 - replace->genBound8) & 0xF8)
+ > tte[i].depth8 - ((263 + generation8 - tte[i].genBound8) & 0xF8))
replace = &tte[i];
return found = false, replace;
int cnt = 0;
for (int i = 0; i < 1000 / ClusterSize; ++i)
for (int j = 0; j < ClusterSize; ++j)
- cnt += (table[i].entry[j].genBound8 & 0xFC) == generation8;
+ cnt += (table[i].entry[j].genBound8 & 0xF8) == generation8;
return cnt * 1000 / (ClusterSize * (1000 / ClusterSize));
}
/// move 16 bit
/// value 16 bit
/// eval value 16 bit
-/// generation 6 bit
+/// generation 5 bit
+/// pv node 1 bit
/// bound type 2 bit
/// depth 8 bit
Value value() const { return (Value)value16; }
Value eval() const { return (Value)eval16; }
Depth depth() const { return (Depth)(depth8 * int(ONE_PLY)); }
+ bool is_pv() const { return (bool)(genBound8 & 0x4); }
Bound bound() const { return (Bound)(genBound8 & 0x3); }
- void save(Key k, Value v, Bound b, Depth d, Move m, Value ev);
+ void save(Key k, Value v, bool pv, Bound b, Depth d, Move m, Value ev);
private:
friend class TranspositionTable;
public:
~TranspositionTable() { free(mem); }
- void new_search() { generation8 += 4; } // Lower 2 bits are used by Bound
+ void new_search() { generation8 += 8; } // Lower 3 bits are used by PV flag and Bound
TTEntry* probe(const Key key, bool& found) const;
int hashfull() const;
void resize(size_t mbSize);
WHITE_OOO = WHITE_OO << 1,
BLACK_OO = WHITE_OO << 2,
BLACK_OOO = WHITE_OO << 3,
- ANY_CASTLING = WHITE_OO | WHITE_OOO | BLACK_OO | BLACK_OOO,
+
+ WHITE_CASTLING = WHITE_OO | WHITE_OOO,
+ BLACK_CASTLING = BLACK_OO | BLACK_OOO,
+ ANY_CASTLING = WHITE_CASTLING | BLACK_CASTLING,
+
CASTLING_RIGHT_NB = 16
};
VALUE_MATE_IN_MAX_PLY = VALUE_MATE - 2 * MAX_PLY,
VALUE_MATED_IN_MAX_PLY = -VALUE_MATE + 2 * MAX_PLY,
- PawnValueMg = 136, PawnValueEg = 208,
+ PawnValueMg = 128, PawnValueEg = 213,
KnightValueMg = 782, KnightValueEg = 865,
BishopValueMg = 830, BishopValueEg = 918,
RookValueMg = 1289, RookValueEg = 1378,
token.clear(); // Avoid a stale if getline() returns empty or blank line
is >> skipws >> token;
- // The GUI sends 'ponderhit' to tell us the user has played the expected move.
- // So 'ponderhit' will be sent if we were told to ponder on the same move the
- // user has played. We should continue searching but switch from pondering to
- // normal search. In case Threads.stopOnPonderhit is set we are waiting for
- // 'ponderhit' to stop the search, for instance if max search depth is reached.
if ( token == "quit"
- || token == "stop"
- || (token == "ponderhit" && Threads.stopOnPonderhit))
+ || token == "stop")
Threads.stop = true;
+ // The GUI sends 'ponderhit' to tell us the user has played the expected move.
+ // So 'ponderhit' will be sent if we were told to ponder on the same move the
+ // user has played. We should continue searching but switch from pondering to
+ // normal search.
else if (token == "ponderhit")
- Threads.ponder = false; // Switch to normal search
+ Threads.main()->ponder = false; // Switch to normal search
else if (token == "uci")
sync_cout << "id name " << engine_info(true)
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <algorithm>
#include <cassert>
#include <ostream>
+#include <sstream>
#include "misc.h"
#include "search.h"
bool Option::operator==(const char* s) const {
assert(type == "combo");
- return !CaseInsensitiveLess()(currentValue, s)
- && !CaseInsensitiveLess()(s, currentValue);
+ return !CaseInsensitiveLess()(currentValue, s)
+ && !CaseInsensitiveLess()(s, currentValue);
}
/// operator=() updates currentValue and triggers on_change() action. It's up to
-/// the GUI to check for option's limits, but we could receive the new value from
-/// the user by console window, so let's check the bounds anyway.
+/// the GUI to check for option's limits, but we could receive the new value
+/// from the user by console window, so let's check the bounds anyway.
Option& Option::operator=(const string& v) {
|| (type == "spin" && (stof(v) < min || stof(v) > max)))
return *this;
+ if (type == "combo")
+ {
+ OptionsMap comboMap; // To have case insensitive compare
+ string token;
+ std::istringstream ss(defaultValue);
+ while (ss >> token)
+ comboMap[token] << Option();
+ if (!comboMap.count(v) || v == "var")
+ return *this;
+ }
+
if (type != "button")
currentValue = v;
echo "sanitizer-undefined testing started"
prefix='!'
exeprefix=''
- postfix='2>&1 | grep "runtime error:"'
+ postfix='2>&1 | grep -A50 "runtime error:"'
threads="1"
;;
--sanitizer-thread)
echo "sanitizer-thread testing started"
prefix='!'
exeprefix=''
- postfix='2>&1 | grep "WARNING: ThreadSanitizer:"'
+ postfix='2>&1 | grep -A50 "WARNING: ThreadSanitizer:"'
threads="2"
cat << EOF > tsan.supp
race:TTEntry::save
race:TTEntry::value
race:TTEntry::eval
+race:TTEntry::is_pv
race:TranspositionTable::probe
race:TranspositionTable::hashfull
#!/bin/bash
-# verify perft numbers (positions from https://chessprogramming.wikispaces.com/Perft+Results)
+# verify perft numbers (positions from www.chessprogramming.org/Perft_Results)
error()
{
projects / stockfish / commitdiff