Support codrus chess

Variant of antichess with forced captures; losing the king wins.

http://www.chessvariants.com/diffobjective.dir/giveaway.html
http://www.binnewirtz.com/Schlagschach1.htm

Support breakthrough

https://en.wikipedia.org/wiki/Breakthrough_(board_game)

bench: 5016237

Insert missing value for clobber pieces

Support clobber

https://en.wikipedia.org/wiki/Clobber

bench: 4737198

Support horde chess

- Add horde chess.
- Increase piece list size.
- Add configuration option for pawn double steps from first rank.

No functional change for existing variants.

Tweak probcut margin for extinction variants

extinction STC
LLR: 2.96 (-2.94,2.94) [0.00,10.00]
Total: 411 W: 238 L: 138 D: 35
http://35.161.250.236:6543/tests/view/5b71df356e23db0fbab0dca3

Tweak bonus for racing kings

racing kings STC
LLR: 2.96 (-2.94,2.94) [0.00,10.00]
Total: 469 W: 262 L: 162 D: 45
http://35.161.250.236:6543/tests/view/5b71dcbb6e23db0fbab0dca0

Fix #5: Set attack bitboards for all piece types

This fixes issues with uninitialized attack tables.
Bench results are deterministic now also for variants
that are missing some of the standard chess piece types.

No functional change for standard chess.

Reference wiki in readme

Use negative piece values for antichess-like variants

giveaway STC
LLR: 7.17 (-2.94,2.94) [0.00,10.00]
Total: 234 W: 231 L: 2 D: 1
http://35.161.250.236:6543/tests/view/5b6e12d56e23db0fbab0dc73

losers STC
LLR: 0.00 (-2.94,2.94) [0.00,10.00]
Total: 1342 W: 1071 L: 271 D: 0
http://35.161.250.236:6543/tests/view/5b6e12f06e23db0fbab0dc76

Threat evaluation for variants with mandatory captures

giveaway STC
LLR: 2.96 (-2.94,2.94) [0.00,10.00]
Total: 704 W: 401 L: 290 D: 13
http://35.161.250.236:6543/tests/view/5b6ca2256e23db0fbab0dc69

losers STC
LLR: 2.95 (-2.94,2.94) [0.00,10.00]
Total: 288 W: 187 L: 86 D: 15
http://35.161.250.236:6543/tests/view/5b6ca24c6e23db0fbab0dc6c

Fix Zobrist initialization for pawns in hand

No functional change for variants without drops.

Add benchmark support for variants

Use e.g. "bench crazyhouse" to run bench test for variants.

Add support for USI protocol

Specification: http://hgm.nubati.net/usi.html

- Switch protocol when receiving uci/usi command,
  or when option "Protocol" is changed.
- Support parsing of SFEN, but internally use FEN.
- Use shogi coordinates (e.g., 3e3d) for all moves,
  and notation with "*" for piece drops.
- Specify mate distance in ply instead of fullmoves.
- Todo: Adapt option names to be compliant with USI
  - No whitespaces.
  - Standard options should be prefixed by "USI_".

Prettify debug output for non-standard board sizes

Update name and author

Extend mandatory captures that are only moves

STC
LLR: 2.95 (-2.94,2.94) [0.00,10.00]
Total: 485 W: 290 L: 183 D: 12

LTC
LLR: 2.97 (-2.94,2.94) [0.00,10.00]
Total: 890 W: 483 L: 371 D: 36

Skip problematic travis mac builds

Enable CI for all branches

Divide piece score by 2 for drop variants

STC
LLR: 2.97 (-2.94,2.94) [0.00,10.00]
Total: 302 W: 202 L: 96 D: 4

LTC
LLR: 2.95 (-2.94,2.94) [0.00,10.00]
Total: 262 W: 182 L: 77 D: 3

Tweak SEE for nCheck and extinction variants

3check STC
LLR: 2.96 (-2.94,2.94) [0.00,10.00]
Total: 131 W: 115 L: 14 D: 2

extinction STC
LLR: 2.97 (-2.94,2.94) [0.00,10.00]
Total: 92 W: 90 L: 1 D: 1

Increase king danger for drop games and nCheck

3check STC
LLR: 2.95 (-2.94,2.94) [0.00,10.00]
Total: 229 W: 162 L: 60 D: 7

crazyhouse STC
LLR: 2.97 (-2.94,2.94) [0.00,10.00]
Total: 722 W: 404 L: 294 D: 24

Skip early pruning in case of mandatory captures

giveaway STC
LLR: 2.97 (-2.94,2.94) [0.00,10.00]
Total: 86 W: 83 L: 1 D: 2

losers STC
LLR: 2.98 (-2.94,2.94) [0.00,10.00]
Total: 96 W: 89 L: 3 D: 4

Fix king piece-square table

chess STC
LLR: 2.97 (-2.94,2.94) [0.00,10.00]
Total: 984 W: 284 L: 205 D: 495

bench: 4515065

Fix Analysis Contempt combo option

Fix signature verification script

Fix relative_rank for maximum rank != 2^n

No functional change for 8x8 boards.

Add support for Judkins Shogi

Add shogi variants to readme

Support FEN notation for promoted shogi pieces

Parse and generate FENs with promoted pieces using the '+'-Notation,
e.g. '+r' for a promoted rook.

Performance improvement for small board sizes

Filter out illegal moves early.

No functional change.

Fix move validation for minishogi

Invalidate drops and normal moves that result in a piece having no legal move.
Perft looks good now for euroshogi and minishogi, so add them to tests.

Extend perft tests

Add perft tests for variants

No functional change.

Partial support for shogi variants

Support minishogi and euroshogi with the limitation that the position
must be sent via "position startpos moves ..." and not using an FEN.

Limitations:
- FENs with promoted pieces do not work.
- Mates by pawn drops are not recognized to be losing.

bench: 4604661

Update variant list in readme

Use endgame evaluation only for moderate variants

Endgame evaluation functions and scaling factors are no longer applied
to games where they are not applicable, e.g., crazyhouse, giveaway, etc.

No functional change for standard chess.

Support giveaway, antichess, extinction, and kinglet chess

Includes implementation of
- positions without kings
- castling with non-king piece
- winning condition "extinction"
- piece type commoner

bench: 4948195

Update variant list in readme

Support chessgi and pocketknight

Fix appveyor build

Explicitly include <functional> for std::greater.

Support shatar (incomplete), chigorin, and almost chess

bench: 4636838

Use a general mobility bonus formula for fairy pieces

No functional change for standard chess.

Fix #3: Filter out double steps when disabled

Fixes pseudo-legal move validation for variants without double steps.

Minishogi WIP

Minor readme changes

Add links to readme

Fix tablebase initialization (#2)

Increase timeout for Travis perft test (#2)

Update appveyor link

Enable Travis CI

bench: 4847945

Scale passed pawn evaluation by promotion piece value

No functional change for standard chess.

Shatranj STC
LLR: 2.95 (-2.94,2.94) [0.00,10.00]
Total: 82 W: 63 L: 1 D: 18

Add support for smaller board sizes, implement los alamos chess

However, the evaluation does not reflect the dependence of symmetry
on number of ranks and files yet.

EuroShogi WIP

Promotion rules, pawn drop restrictions, and perpetuals not implemented yet.

Fix king of the hill and racing kings

Furthermore introduce some basic variant-specific bonuses.

Add variants to readme

Support crazyhouse and loop chess

Add brief description to readme

Support 3check/5check/nCheck ; initial development for crazyhouse

Support king of the hill, racing kings, and losers chess

Add options for bare king rule, checkmate/stalemate value,
king target squares, mandatory captures, and prohibited checks to
support king of the hill, racing kings, and losers, and to complete the
implementation of shatranj.

Reduce limit to 32 piece types

Initial development for fairy chess variants

Generalize code to be able to easily configure new variants
with different pieces and rules. Add a few initial variants:
- Chess
- Makruk
- ASEAN
- Ai-Wok
- Shatranj
- Amazon
- Hoppel-Poppel

Remove lmrDepth restriction on quiet see pruning

And tweak the threshold value. With this threshold and the current piece
values, this permits see pruning on quiets to be done up to an lmrDepth
of 9 (beyond that the threshold is below -QueenValueMg and see_ge will
pass unconditionally).

STC:
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 110316 W: 24612 L: 24667 D: 61037
http://tests.stockfishchess.org/tests/view/5b20aa760ebc5902ab9c9c1d

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 17352 W: 2968 L: 2842 D: 11542
http://tests.stockfishchess.org/tests/view/5b20cf1e0ebc5902ab9c9fb6

Closes https://github.com/official-stockfish/Stockfish/pull/1651

Bench: 5069074

Remove depth condition for pruning captures.

The SEE condition alone is sufficient.

passed STC:
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 109863 W: 24339 L: 24392 D: 61132
http://tests.stockfishchess.org/tests/view/5b1f5b000ebc5902ab9c8668

passed LTC:
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 23390 W: 4020 L: 3903 D: 15467
http://tests.stockfishchess.org/tests/view/5b1f94b40ebc5902ab9c8b5e

Closes https://github.com/official-stockfish/Stockfish/pull/1648

Bench: 4834747

Optimize an expression in endgame.cpp

I believe using foward_file_bb() here is fewer instructions.

a) Fewer instructions and probably more clear (debatable).
b) Possible that a lookup is slower than a few local operations, but the
   forward_file_bb table is probably used often enough that it is always
   cached.

Passed
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 21004 W: 4263 L: 4141 D: 12600
http://tests.stockfishchess.org/tests/view/5b1cad830ebc5902ab9c6239

Closes https://github.com/official-stockfish/Stockfish/pull/1644

No functional change.

Simplify capture pruning margin formula

Using just `PawnValueEg * depth` as Capture Prune Margin. There was a bunch
of patches that passed recently regarding captures, maybe this part of the
master code redundant? The patch was tested as a simplification:

STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 20833 W: 4218 L: 4096 D: 12519
http://tests.stockfishchess.org/tests/view/5b1cf2100ebc5902ab9c6651

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 27050 W: 3975 L: 3864 D: 19211
http://tests.stockfishchess.org/tests/view/5b1cfdc80ebc5902ab9c6776

Closes https://github.com/official-stockfish/Stockfish/pull/1643

Bench: 4980482

Optimize contempt value (21)

After several tests it seems best to increase contempt from 12 to 21. This does
not regress against contempt=0 and gives a gain of around 7-8 elo against SF 7
in comparison to current default contempt.

STC: Test for non-regression contempt=21 against contempt=0
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 71250 W: 13956 L: 13926 D: 43368
http://tests.stockfishchess.org/tests/view/5b19a58d0ebc5902ab9c3bfa

STC: Test contempt 21 against SF 7
ELO: 190.06 +-2.8 (95%) LOS: 100.0%
Total: 40000 W: 22608 L: 2676 D: 14716
http://tests.stockfishchess.org/tests/view/5b19a6520ebc5902ab9c3c0e

STC: Test master against SF 7 for comparison
ELO: 182.95 +-2.7 (95%) LOS: 100.0%
Total: 40000 W: 21905 L: 2595 D: 15500
http://tests.stockfishchess.org/tests/view/5b16f5bc0ebc59214346d5ca

LTC: Test for non-regression contempt=21 against contempt=0
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 47666 W: 6914 L: 6832 D: 33920
http://tests.stockfishchess.org/tests/view/5b1a170b0ebc5902ab9c3fde

LTC: Test contempt 21 against SF 7
ELO: 203.92 +-2.6 (95%) LOS: 100.0%
Total: 40000 W: 22447 L: 1340 D: 16213
http://tests.stockfishchess.org/tests/view/5b1a174b0ebc5902ab9c3fe1

LTC: Test master against SF 7 for comparison
ELO: 196.08 +-2.6 (95%) LOS: 100.0%
Total: 40000 W: 21639 L: 1191 D: 17170
http://tests.stockfishchess.org/tests/view/5b1a17e40ebc5902ab9c3fe4

Closes https://github.com/official-stockfish/Stockfish/pull/1646

Bench: 4786912

Remove failedLow from the mainThread struct

failedLow is in fact a local variable in Thread::search().

Also clean some spaces and tabs in code.

No functional change.

Quiet move soft fail high bonus

Extra bonus for quiet move creating a huge soft fail high (triggered
in 21% of quiet bestmoves on a normal bench run). Pb00067 original idea
using PawnValueMg.

Passed STC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 138207 W: 28060 L: 27295 D: 82852
http://tests.stockfishchess.org/tests/view/5b14471b0ebc5902a81689c1

Passe LTC:
LLR: 2.94 (-2.94,2.94) [0.00,5.00]
Total: 157289 W: 23200 L: 22518 D: 111571
http://tests.stockfishchess.org/tests/view/5b149dde0ebc5902a8b41c5a

bench: 4441320

Simplify capture bonus

Simplify capture bonus by simply adding ONE_DEPTH instead of being
dependent on BestValue.

STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 24419 W: 4939 L: 4824 D: 14656
http://tests.stockfishchess.org/tests/view/5b16b2040ebc5963ba37e2a5

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 44560 W: 6524 L: 6438 D: 31598
http://tests.stockfishchess.org/tests/view/5b16ccc00ebc59214346d403

Closes https://github.com/official-stockfish/Stockfish/pull/1640

Bench: 4782637

Call cycle detection before qsearch()

This has the property of raising alpha before calling qsearch(), thus
maybe giving some more cuts during qsearch(). The patch is equivalent
to the use of cycle detection inside qsearch() at depth 0, but is in
fact implemented by re-ordering code inside search(), which explains
the [0..4] bounds in the following tests.

STC (interrupted after 124250 games, with LLR=0.87):
http://tests.stockfishchess.org/tests/view/5b1500bd0ebc5902a8b420bf
LLR: 0.87 (-2.94,2.94) [0.00,4.00]
Total: 124250 W: 24973 L: 24470 D: 74807

LTC:
http://tests.stockfishchess.org/tests/view/5b1590eb0ebc5902a84dcd09
LLR: 2.96 (-2.94,2.94) [0.00,4.00]
Total: 74234 W: 11098 L: 10733 D: 52403

Closes https://github.com/official-stockfish/Stockfish/pull/1635

Bench: 4326784

Stabilize AppVeyor CI

After a helpful suggestion from AppVeyor support staff, moving the Stockfish
execution from ps to cmd seems to work. Alternative to PR #1624 tested in PR #1637.

No functional change.

Remove a superfluous subtrahend

The '- 1' subtrahend was introduced for guarding against null move
search at root, which would be nonsense. But this is actually already
guaranteed by the !PvNode condition. This followed from the discussion
in pull request 1609: https://github.com/official-stockfish/Stockfish/pull/1609

No functional change

Simplify LMR for captures

Simplify LMR for captures by removing capture's stat score logic for reduction.

STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 37068 W: 7462 L: 7370 D: 22236
http://tests.stockfishchess.org/tests/view/5b115bc30ebc591af58a6fd2

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 80061 W: 11706 L: 11671 D: 56684
http://tests.stockfishchess.org/tests/view/5b117f590ebc59033d2d5315

Closes https://github.com/official-stockfish/Stockfish/pull/1631

Bench: 4470519

Bugfix of Position::has_repeated()

The function Position::has_repeated() is used by Tablebases::root_probe()
to determine whether we can rank all winning moves with the same value, or
if we need to strictly rank by dtz in case the position has already been
repeated once, and we are risking to run into the 50-move rule and thus
losing the win (especially critical in some very complicated endgames).

To check whether the current position or one of the previous positions
after the last zeroing move has already been occured once, we start looking
for a repetition of the current position, and if that is not the case, we
step one position back and repeat the check for that position, and so on.

If you now look at how this was done before the new root ranking patch was
merged two months ago, it seems quite obvious that it is a simple oversight:
https://github.com/official-stockfish/Stockfish/commit/108f0da4d7f993732aa2e854b8f3fa8ca6d3b46c

More specifically, after we stepped one position back with

```
stc = stc->previous;
```

we now have to start checking for a repetition with

```
StateInfo* stp = stc->previous->previous;
```

and not with

```
StateInfo* stp = st->previous->previous;
```

Closes https://github.com/official-stockfish/Stockfish/pull/1625

No functional change

Fix overload ambiguity

Fix an error when compiling current master with MSVC due to the
ambiguity of which operator* overload was intended (reported by
Jarrod Torriero).

No functional change.

Extra bonus for capture creating a huge fail high

STC:
http://tests.stockfishchess.org/tests/view/5b114f3d0ebc596e9e0881f6
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 13007 W: 2730 L: 2541 D: 7736

LTC:
http://tests.stockfishchess.org/tests/view/5b1176740ebc59033d2d52c6
LLR: 2.96 (-2.94,2.94) [0.00,5.00]
Total: 15594 W: 2417 L: 2239 D: 10938

See https://github.com/official-stockfish/Stockfish/pull/1627

Bench: 4790240

Fix comments, rename variables

Thanks everybody for the various hints in the perpetual renaming thread:
https://github.com/official-stockfish/Stockfish/issues/1426

No functional change

Reallocate TT on threadpool resize.

Makes sure the potential benefit of first touch does not depend on
the order of the UCI commands Threads and Hash, by reallocating the
hash if a Threads is issued. The cost is zeroing the TT once more
than needed. In case the prefered order (first Threads than Hash)
is employed, this amounts to zeroing the default sized TT (16Mb),
which is essentially instantaneous.

Follow up for https://github.com/official-stockfish/Stockfish/pull/1601
where additional data and discussion is available.

Closes https://github.com/official-stockfish/Stockfish/pull/1620

No functional change.

Simplify depth reduction in IID.

Use a constant reduction instead of a depth dependent reduction.

passed STC:
http://tests.stockfishchess.org/tests/view/5b06eb600ebc5914abc12ba8
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 58086 W: 11710 L: 11657 D: 34719

passed LTC:
http://tests.stockfishchess.org/tests/view/5b07b25e0ebc5914abc12c6d
LLR: 3.09 (-2.94,2.94) [-3.00,1.00]
Total: 110414 W: 16217 L: 16219 D: 77978

Bench: 4521056

Use threads to clear the TT faster.

Stockfish currently takes a while to clear the TT when using larger hash sizes.

On one machine with 128 GB hash it takes about 50 seconds with a single thread,
allowing it to use all allocated cores brought that time down to 4 seconds on
some Linux systems. The patch was further tested on Windows and refined with
NUMA binding of the hash initializing threads (we refer to pull request #1601
for the complete discussion and the speed measurements).

Closes https://github.com/official-stockfish/Stockfish/pull/1601

No functional change

LMR Capture Tweak

Increase capture reduction by comparing opponent's stat score

STC: (Yellow)
LLR: -2.96 (-2.94,2.94) [0.00,5.00]
Total: 92291 W: 18647 L: 18350 D: 55294
http://tests.stockfishchess.org/tests/view/5b04225e0ebc5914abc1291b

LTC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 20176 W: 3061 L: 2868 D: 14247
http://tests.stockfishchess.org/tests/view/5b04bb3f0ebc5914abc129a3

How to continue?
• we could try a different value for the capture history threeshold

Closes https://github.com/official-stockfish/Stockfish/pull/1612

Bench: 5167159

Simplify BlockedByPawn to one dimension

I was able to get this to pass which reduces BlockedByPawn to one dimension
with NO distance from edge offset.

GOOD)  It's more simple and may provide additional clarity for further
simplifications.  Facilitates migrating unblocked to one dimension as well.

BAD) If there is indeed a distance component to BlockedStorm (may or may
not be the case), this obfuscates this component into ShelterStrength and
UnblockedStorm. This may be more convoluted. Also, it may be more convenient
to have each of the three arrays (ShelterStrength, BlockedStorm, and UnBlocked)
be the same size.

STC:
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 96173 W: 19326 L: 19343 D: 57504
http://tests.stockfishchess.org/tests/view/5b04544d0ebc5914abc12965

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 49818 W: 7441 L: 7363 D: 35014
http://tests.stockfishchess.org/tests/view/5b0487d50ebc5914abc12990

Closes https://github.com/official-stockfish/Stockfish/pull/1611

Bench: 5133208

Correctly prevent recursive verification in nmp.

As discussed with @pb00068, the condition to prevent recursive verification
was not completely correct. This patch corrects that condition, and adds an
assert. In the current implementation, recursive verification needs to be
avoided in order not to break the verification of the move closer to the
root (i.e. to not set thisThread->nmp_min_ply to zero prematurely).

This patch is tested as a bug fix, based on and tested against PR #1609 .

passed STC:
http://tests.stockfishchess.org/tests/view/5b050f170ebc5914abc129c5
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 7875 W: 1669 L: 1523 D: 4683

passed LTC:
http://tests.stockfishchess.org/tests/view/5b0513970ebc5914abc129cd
LLR: 3.00 (-2.94,2.94) [-3.00,1.00]
Total: 24048 W: 3525 L: 3407 D: 17116

Bench changes at high depth.

Closes https://github.com/official-stockfish/Stockfish/pull/1610
and    https://github.com/official-stockfish/Stockfish/pull/1609

Bench: 4484288

Simplify color usage in search.

define Color us and use this instead of pos.side_to_move() and nmp_odd. The latter allows to clarify the nmp verification criterion.

Tested for no regression:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 76713 W: 15303 L: 15284 D: 46126
http://tests.stockfishchess.org/tests/view/5b046a0d0ebc5914abc12971

No functional change.

Simply reset StatScore to zero at beta cutoff

STC:
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 43154 W: 8706 L: 8625 D: 25823
http://tests.stockfishchess.org/tests/view/5b01a7660ebc5914abc1271d

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 48155 W: 7036 L: 6955 D: 34164
http://tests.stockfishchess.org/tests/view/5b01b2e50ebc5914abc1272c

Closes https://github.com/official-stockfish/Stockfish/pull/1608

Bench: 4484288

Simplify shelter: always do strength and danger

This check of pawns before subtracting danger can be removed.

STC
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 21174 W: 4361 L: 4239 D: 12574
http://tests.stockfishchess.org/tests/view/5b00b9f90ebc5914abc12680

LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 56980 W: 8377 L: 8309 D: 40294
http://tests.stockfishchess.org/tests/view/5b00ca750ebc5914abc12683

Closes https://github.com/official-stockfish/Stockfish/pull/1607

Bench: 4746692

Simplifying away the progressKey

Simplifying away all the progressKey stuff gives exactly the same bench,
without any speed impact. Tested for speed against master with two benches
at depth 22 ran in parallel:

**testedpatch**
Total time (ms) : 92350
Nodes searched : 178962949
Nodes/second : 1937877

**master**
Total time (ms) : 92358
Nodes searched : 178962949
Nodes/second : 1937709

We also tested the patch at STC for no-regression with [-3, 1] bounds:

LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 57299 W: 11529 L: 11474 D: 34296
http://tests.stockfishchess.org/tests/view/5b015a1c0ebc5914abc126e5

Closes https://github.com/official-stockfish/Stockfish/pull/1603

No functional change.

Fix MSVC errors in tbprobe.cpp

Default template parameters values and recursive functions do not play well
together. Fix for below errors that showed up after updating to latest MSVC.

````
tbprobe.cpp(1156): error C2672:
    'search': no matching overloaded function found

tbprobe.cpp(1198): error C2783:
  'Tablebases::WDLScore `anonymous-namespace'::search(Position &,Tablebases::ProbeState *)':
could not deduce template argument for 'CheckZeroingMoves'

````

Closes https://github.com/official-stockfish/Stockfish/pull/1594

No functional change.

Use cycle detection to bound search value

A position which has a move which draws by repetition, or which could have
been reached from an earlier position in the game tree, is considered to be
at least a draw for the side to move.

Cycle detection algorithm by Marcel van Kervink:

       https://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf

----------------------------

How does the algorithm work in practice? The algorithm is an efficient
method to detect if the side to move has a drawing move, without doing any
move generation, thus possibly giving a cheap cutoffThe most interesting
conditions are both on line 1195:

```
  if (   originalKey == (progressKey ^ stp->key)
      || progressKey == Zobrist::side)
```

This uses the position keys as a sort-of Bloom filter, to avoid the expensive
checks which follow. For "upcoming repetition" consider the opening Nf3 Nf6 Ng1.
The XOR of this position's key with the starting position gives their difference,
which can be used to look up black's repeating move (Ng8). But that look-up is
expensive, so line 1195 checks that the white pieces are on their original squares.

This is the subtlest part of the algorithm, but the basic idea in the above game
is there are 4 positions (starting position and the one after each move). An XOR
of the first pair (startpos and after Nf3) gives a key matching Nf3. An XOR of
the second pair (after Nf6 and after Ng1) gives a key matching the move Ng1. But
since the difference in each pair is the location of the white knight those keys
are "identical" (not quite because while there are 4 keys the the side to move
changed 3 times, so the keys differ by Zobrist::side). The loop containing line
1195 does this pair-wise XOR-ing.

Continuing the example, after line 1195 determines that the white pieces are
back where they started we still need to make sure the changes in the black
pieces represents a legal move. This is done by looking up the "moveKey" to
see if it corresponds to possible move, and that there are no pieces blocking
its way. There is the additional complication that, to match the behavior of
is_draw(), if the repetition is not inside the search tree then there must be
an additional repetition in the game history. Since a position can have more
than one upcoming repetition a simple count does not suffice. So there is a
search loop ending on line 1215.

On the other hand, the "no-progress' is the same thing but offset by 1 ply.
I like the concept but think it currently has minimal or negative benefit,
and I'd be happy to remove it if that would get the patch accepted. This
will not, however, save many lines of code.

-----------------------------

STC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 36430 W: 7446 L: 7150 D: 21834
http://tests.stockfishchess.org/tests/view/5afc123f0ebc591fdf408dfc

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,5.00]
Total: 12998 W: 2045 L: 1876 D: 9077
http://tests.stockfishchess.org/tests/view/5afc2c630ebc591fdf408e0c

How could we continue after the patch:

• The code in search() that checks for cycles has numerous possible variants.
  Perhaps the check need could be done in qsearch() too.

• The biggest improvement would be to get "no progress" to be of actual benefit,
  and it would be helpful understand why it (probably) isn't. Perhaps there is an
  interaction with the transposition table or the (fantastically complex) tree
  search. Perhaps this would be hard to fix, but there may be a simple oversight.

Closes https://github.com/official-stockfish/Stockfish/pull/1575

Bench: 4550412

Update search.cpp

At PvNodes allow bonus for prior counter move that caused a fail low
for depth 1 and 2. Note : I did a speculative LTC on yellow STC patch
since history stats tend to be highly TC sensitive

STC (Yellow):
LLR: -2.96 (-2.94,2.94) [0.00,5.00]
Total: 64295 W: 13042 L: 12873 D: 38380
http://tests.stockfishchess.org/tests/view/5af507c80ebc5968e6524153

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,5.00]
Total: 22407 W: 3413 L: 3211 D: 15783
http://tests.stockfishchess.org/tests/view/5af85dd40ebc591fdf408b87

Also use local variable excludedMove in NMP (marotear)

Bench:  5294316

Tweak kingAttackersCount and KingAttackWeights

Use the whole kingRing for pawn attackers instead of only the squares directly
around the king. This tends to give quite a lot more kingAttackersCount, so to
compensate and to avoid raising the  king danger too fast we lower the values
in the KingAttackWeights array a little bit.

STC:
LLR: 2.95 (-2.94,2.94) [0.00,4.00]
Total: 51892 W: 10723 L: 10369 D: 30800
http://tests.stockfishchess.org/tests/view/5af6d4dd0ebc5968e652428e

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,4.00]
Total: 24536 W: 3737 L: 3515 D: 17284
http://tests.stockfishchess.org/tests/view/5af709890ebc5968e65242ac

Credits to user @xoroshiro for the idea of using the kingRing for pawn attackers.

How to continue? It seems that the KingAttackWeights[] array stores values
which are quite Elo-sensitive, yet they have not been tuned with SPSA recently.
There might be easy Elo points to get there.

Closes https://github.com/official-stockfish/Stockfish/pull/1597

Bench: 5282815

Include all blockers in king danger

Simplification: in king danger, include all blockers and not only pinned
pieces, since blockers enemy pieces can result in discovered checks which
are also bad.

STC  http://tests.stockfishchess.org/tests/view/5af35f9f0ebc5968e6523fe9
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 145781 W: 29368 L: 29478 D: 86935

LTC http://tests.stockfishchess.org/tests/view/5af3cb430ebc5968e652401f
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 76398 W: 11272 L: 11232 D: 53894

I also incorrectly scheduled STC with [0,5] which it failed.
http://tests.stockfishchess.org/tests/view/5af283c00ebc5968e6523f33
LLR: -2.94 (-2.94,2.94) [0.00,5.00]
Total: 12338 W: 2451 L: 2522 D: 7365

Closes https://github.com/official-stockfish/Stockfish/pull/1593

bench: 4698290

----------------------------------------

Thanks to @vondele and @Rocky640 for a cleaner version of the patch,
and the following comments!

> Most of the pinned, (or for this pull request, blocking) squares were
> already computed in the unsafeChecks, the only missing squares being:
>
> a) squares attacked by a Queen which are occupied by friendly piece
>    or "unsafe". Note that adding such squares never passed SPRT[0,5].
>
> b) squares not in mobilityArea[Us].
>
> There is a strong relationship between the blockers and the unsafeChecks,
> but the bitboard unsafeChecks is still useful when the checker is not
> aligned with the king, and the checking square is occupied by friendly
> piece or is "unsafe". This is always the case for the Knight.

Consolidate pawn storm types

Simplification: the Unopposed and Unblocked pawn storm types are mathematically
similar enough to combine with no Elo loss. This reduces the pawn storm types
to BlockedByPawn and UnBlocked.

STC
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 116869 W: 23549 L: 23605 D: 69715
http://tests.stockfishchess.org/tests/view/5af2def90ebc5968e6523f82

LTC
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 39912 W: 6090 L: 5998 D: 27824
http://tests.stockfishchess.org/tests/view/5af3b2e20ebc5968e6524013

Closes https://github.com/official-stockfish/Stockfish/pull/1592

Bench: 5244314

Tune null move pruning

Use a lower stat score threshold of 22500.

Failed yellow at STC after many games (~0.92 Elo):
LLR: -2.96 (-2.94,2.94) [0.00,4.00]
Total: 73978 W: 14947 L: 14834 D: 44197
http://tests.stockfishchess.org/tests/view/5af2deec0ebc5968e6523f80

But scales good and passed LTC:
LLR: 2.96 (-2.94,2.94) [0.00,4.00]
Total: 23147 W: 3453 L: 3237 D: 16457
http://tests.stockfishchess.org/tests/view/5af3cf820ebc5968e6524022

Closes https://github.com/official-stockfish/Stockfish/pull/1591

Bench: 4777674

Tuned some pawns and evaluation constants

Tuned values in pawns.cpp and evaluate.cpp after a SPSA session:
419k games 60sec 600nodetime.  We have adjusted the PassedRank[]
output of the SPSA session to keep increasing values with rank,
and PassedFile[] output to keep the West <–> East symmetry of
the evaluation.

STC:
LLR: 2.95 (-2.94,2.94) [0.00,4.00]
Total: 58948 W: 12431 L: 12046 D: 34471
http://tests.stockfishchess.org/tests/view/5af2302f0ebc5968e6523f0a

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,4.00]
Total: 22211 W: 3468 L: 3251 D: 15492
http://tests.stockfishchess.org/tests/view/5af264c80ebc5968e6523f1a

See https://github.com/official-stockfish/Stockfish/pull/1587
and https://github.com/official-stockfish/Stockfish/pull/1590

bench: 4437531

Remove goto, limit skipping to NMP

This patch simplifies the control flow in search(), removing an if
and a goto. A side effect of the patch is that Stockfish is now a
little bit more selective at low depths, because we allow razoring,
futility pruning and probcut pruning after a null move.

passed STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 32035 W: 6523 L: 6422 D: 19090
http://tests.stockfishchess.org/tests/view/5af142ca0ebc597fb3d39bb6

passed LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 41431 W: 6187 L: 6097 D: 29147
http://tests.stockfishchess.org/tests/view/5af148770ebc597fb3d39bc1

Ideas for further work:

• Use the nodes credit opened by the patch (the increased selectivity)
  to try somewhat higher razoring, futility or probcut margins at [0..4].

Bench: 4855031

Tweak null move pruning conditions

Allow null move pruning only if last stat score < 30000.

Passed STC:
LLR: 2.95 (-2.94,2.94) [0.00,5.00]
Total: 12653 W: 2641 L: 2454 D: 7558
http://tests.stockfishchess.org/tests/view/5af1d8830ebc5968e6523edb

Passed LTC:
LLR: 2.97 (-2.94,2.94) [0.00,5.00]
Total: 19782 W: 3072 L: 2878 D: 13832
http://tests.stockfishchess.org/tests/view/5af1ee8c0ebc5968e6523ee4

Ideas for further work:

• Tune the stat score threshold.
• Try depth based stat score threshold.
• Try stat score condition for other prunings.

Closes https://github.com/official-stockfish/Stockfish/pull/1589

Bench: 5088156

Drop the lever condition for backwards

We can view the patch version as adding some "undermining bonus" for
level pawns, when the defending side can not easily avoid the exchange
by advancing her pawn.

• Case 1) White b2,c3, Black a3,b3:
          Black is breaking through, b2 deserves a penalty

• Case 2) White b2,c3, Black a3,c4:
          if b2xa3 then White ends up with a weak pawn on a3
          and probably a weak pawn on c3 too.

In either case, White can still not safely play b2-b3 and make a
phalanx with c3, which is the essence of a backward pawn definition.

Passed STC in SPRT[0, 4]:
LLR: -2.96 (-2.94,2.94) [0.00,4.00]
Total: 131169 W: 26523 L: 26199 D: 78447
http://tests.stockfishchess.org/tests/view/5aefa4d50ebc5902a409a151
ELO 1.19 [-0.38,2.88] (95%)

Passed LTC in SPRT[-3, 1]:
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 24824 W: 3732 L: 3617 D: 17475
http://tests.stockfishchess.org/tests/view/5af04d3f0ebc5902a88b2e55
ELO 1.27 [-1.21,3.70] (95%)

Closes https://github.com/official-stockfish/Stockfish/pull/1584

How to continue from there?

There were some promising tests a couple of months ago about adding
a lever condition for king danger in evaluate.cpp, maybe it would
be time to re-try this after all the recent changes in pawns.cpp

Bench: 4773882

Remove skipEarlyPruning argument to search()

Remove nine boolean arguments and the corresponding skipEarlyPruning variable.
Instead, skip early pruning only when there is an excluded move, and try null
move pruning only if the previous move was not itself a null move.

passed STC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 33623 W: 6853 L: 6755 D: 20015
http://tests.stockfishchess.org/tests/view/5aef462a0ebc5902a409a10e

passed LTC:
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 39474 W: 5882 L: 5789 D: 27803
http://tests.stockfishchess.org/tests/view/5aefd4b80ebc5902a409a164

Closes https://github.com/official-stockfish/Stockfish/pull/1585

Bench: 4953556