Skip evaluate() call after a null move

Reuse the evaluation of the parent with inverted sign and
set margin to zero (this is an hack!).

This is done only in qsearch where almost 15% of calls are
from a null move. In normal search the number of nodes where

(ss-1)->currentMove == MOVE_NULL

is almost zero and so there is no need of using this trick.

The big advantage of this patch is a speed-up due to skipped
evaluate() calls, that are very costly.

Functionality is of course affected and we will need to proper
test it later. For now we just register a 3-4% speed up.

Suggested by Hongzhi Cheng.

bench: 5051328

Correctly fix "break from split" patch

In case split cut-offs we return with still
some moves to go but we really want to break
out from the loop now.

No functional change.

Relax constrain in prevents_threat()

When testing if a move blocks the threat path there is no
reason to require the threat to be a slider. Indeed threat
can be a double pawn push like in this example:

r1bq1rk1/ppp1np1p/4n1p1/3p4/3P2Q1/2P1B3/PPBN2PP/R4RK1 w - - 0 16

Where white's move Rf6 blocks the threat f5.

As a nice side effect we can retire the now useless helper
piece_is_slider().

This patch kicks in only very rare cases, indeed the bench is
still the same!

bench: 5809010

Sync connected_threat() and yields_to_threat()

Rename stuff so to sync as much as posisble the
two related functions.

No functional change.

Don't 'break' upon returning from split()

There is no guarantee that split() consumes all the node's
moves. Indeed split() can return without performing any job
for instance because MAX_SPLITPOINTS_PER_THREAD is reached
or becuase no available threads are found (this latter case
is much more common).

So search must continue in those cases and we cannot force
exiting from move's loop.

Bug introduced by 1ac417edb845 of 5/10/2012

Spotted by Frank Genot.

No functional change.

Remove a redundant condition in connected_moves()

If a previous move attacks the king (with the piece
of the threat move removed) then must be a discovered
check, otherwise it means that first move gave check
and we were not able to do a null move.

Also renamed stuff to better document the function's
context.

No functional change.

Relax constrain in connected_moves()

When testing if a piece is moving through the squares
vacated by a previous move there is no reason to require
the piece to be a slider, indeed we can have a double
pawn push like in this example:

r1q2rk1/2p1bppp/2Pp4/pN5b/Q1P1p3/4B2P/PP1R1PP1/1K5R w - - 3 18

Where black's move f5 is connected to previous move Be7 that
frees the path.

Or we can have a castle move:

r1bqkb1r/pppp1ppp/2n1pn2/1B6/4P3/2N2N2/PPPP1PPP/R1BQK2R b KQkq - 5 1

Where a previous move Bb5 allows the white to castle king side.

This time patch is mine ;-)

new bench: 5809010

Reformat connected_moves()

Prepare code for the next patch that
will affect functionality.

No functional change.

Fix an off-by-one bug in multi pv print

We send to GUI multi-pv info after each cycle,
not just once at the end of the PV loop. This is
because at high depths a single root search can
be very slow and we want to update the gui as
soon as we have a new PV score.

Idea is good but implementation is broken because
sort() takes as arguments a pointer to the first
element and one past the last element.

So fix the bug and rename sort arguments to better
reflect their meaning.

Another hit by Hongzhi Cheng.  Impressive!

No functional change.

Fix a condition in connected_moves()

When checking if the moving piece p1 in a previous
move m1 defends the destination square of a move m2
we have to use the occupancy with the from square of
m2 removed so to take in account the case in which
f2 will block an x-ray attack from p1.

For instance in this position:
r2k3r/p1pp1pb1/qn3np1/1N2P3/1p3P2/2B5/PPP3QP/R3K2R b KQ - 1 9

The move eXf6 is connected to the previous move Bc3 that
defends the destination square f6.

With this patch we have about 10% more moves detected as
'connected'. Anyhow the absolute number is very low, about
4000 more moves out of 6M nodes searched.

Another issue spotted by Hongzhi "Hawk Eye" Cheng ;-)

new bench: 5757373

Micro-optimize pop_lsb() for 64bit case

On Intel, perhaps due to 'lea' instruction this way of
zeroing the lsb of *b seems faster than a shift+negate.

On perft (where any speed difference is magnified) I
got a 6% speed up on my Intel i5 64bit.

Suggested by Hongzhi Cheng.

No functional change.

Fix a warning under MSVC

Compiler complies that 'cnt' is initialized but
unused (in !CheckThreeFold case). Moving the
definition of 'cnt'out of the loop  seems to do
the trick.

No functional change.

Pass InCheck as template parameter of qsearch()

Instead of use a variable so to resolve many conditions
already at compile time. In quiesce is also where we
have most of the InCheck nodes and is one of the most
performance critical code paths.

Speed up of 1.5% with Clang and 1% with gcc

Suggested by Hongzhi Cheng.

No functional change.

Use correct occupancy in connected_threat()

When checking if a move defends the threatened piece
we correctly remove from the occupancy bitboard the
moved piece. This patch removes from the occupancy also
the threatening piece so to consider the cases of moves
that defend the threatened piece x-raying through the
threat move.

As example in this position:
r3k2r/p1ppqp2/Bn4p1/3p1n2/4P1N1/5Q1P/PPP2P1P/R3K2R w KQkq - 1 10

The threat black move is dxe4. With this patch we include
(and so don't prune) white's Bb7 that would be pruned otherwise.

The number of affected position is very low, around 1% of cases,
so we don't expect ELO changes, neverthless this is the logical
and natural thing to do.

Patch suggested by Hongzhicheng.

new bench: 5323798

Retire move_attacks_square()

There is only one call site. This patch is a
preparation for the next one that will affect
functionality.

No functional change.

Get rid of ReducedStateInfo struct

ReducedStateInfo is a redundant struct that is also
prone to errors, indeed must be updated any time is
updated StateInfo. It is a trick to partial copy a
StateInfo object in do_move().

This patch takes advantage of builtin macro offsetof()
to directly calculate the number of quad words to copy.
Note that we still use memcpy to do the actual job of
copying the (48 bytes) of data.

Idea by Richard Vida.

No functional and no performance change.

Creative formatting in uci.cpp

Have some fun breaking the indentation rules :-)

No functional change.

Detect drawish KQKP endings

Based off of the rules from the wikipedia page,
here: http://en.wikipedia.org/wiki/Queen_versus_pawn_endgame.

bench does not change: 5312693 but patch is real, has been
tested on specific positions.

Reformat check_is_dangerous()

And shuffle some code at search.cpp tail.

No functional change.

Use std::stack instead of fixed size array

Only in not performance critical code like pretty_pv(),
otherwise continue to use the good old C-style arrays
like in extract/insert PV where I have done some code
refactoring anyhow.

No functional change.

Fix broken uci notation for promotions

Silly typo (introduced in e304db9d1ecf6a23) completely
messed up move notation in case of promotions causing
"Illegal move" warning in cutechess-cli.

Reported by Jörg Oster.

No functional change.

Fix asserts due to TT access races

In multi-threads runs with debug on we experience some
asserts due to the fact that TT access is intrinsecally
racy and its contents cannot be always trusted so must
be validated before to be used and this is what the
patch does.

No functional case.

Extend full 3 fold detection to PvNodes

And restore old behaviour of not returning from a RootNode
without updating RootMoves[].

Also renamed is_draw() template parameters to reflect a
'positive' logic (Check instead of Skip) that is easier
to follow.

New bench: 5312693

Merge pull request #34 from jromang/repetition

Improve 3 fold repetition detection

Full three fold repetition detection only at root node

Enable true 3 fold detection in search

Allow full repetition detection

Based on sshivaji 6ee19aa5389ce60181907ba53bbb50642f2d5657 commit

Fix an assert when we stop the search

When signal 'stop' is raised we return bestValue
that could be still set at -VALUE_INFINITE and
this triggers an assert. Fix it by returning
a value we know for sure is not +-VALUE_INFINITE.

Reported by 平岡拓也 Hiraoka.

No functional change.

Rename RootPosition and shuffle think()

Just slightly code reshuffles, noting interesting here...

No functional change.

Drop Chess960 and UCIMultiPV globals and rename MultiPV

No functional change.

Wrap in a class Skill Level code

Note that the actual pickup is done in the class
d'tor so to be sure it is always triggered, even
in case of a sudden exit due to a 'stop' signal.

No functional change.

Shuffle aspiration window loop

No functional change.

Retire refine_eval()

Inline its content and better comment what it does through
some renaming.

No functional change.

Don't copy a full Position object in print()

Function move_to_san() requires the Position to be
passed by referenced because a do/undo move is done
inside the function to detect a possible mate and to
add to the san string the corresponding '#' suffix.

Instead of passing a copy of current position pass
directly the original position object after const
casting it. This has the advantage to avoid a costly
Position copy, on the down side a bench test could
report different searched nodes if print(move) is
used, due to the additionals do_move() calls.

No functional change.

Don't need to init board[] with NO_PIECE

Now that NO_PIECE == 0 the common memset() will
do the work.

No functional change.

Change NO_PIECE value and shrink PieceValue[]

This requires changing color_of() definition.

No functional change.

Use self-describing constants instead of numbers

And remove now useless comments.

No functional change.

Move RootColor from Eval to Search

No functional change.

Contempt factor: use DrawValue also in case of stealmates

Spotted by Jörg Oster.

No functional change (when contempt factor is not used).

Fix compatibility with old Windows 95 and 98

Report and patches by bnemias.

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

Merge pull request #33 from daylen/master

Further improve OS X compatibility

Change the minimum supported version from 10.6 to 10.0

No functional change.

Further improve compatibility when compiling on OS X

Change the minimum supported version from 10.6 to 10.0

Fix Makefile for PowerPC with prefetch enabled

Existing Makefile is buggy for PowerPC, it has no
SSE, yet it is given it if Prefetch is enabled,
because it isn't ARMv7.

Patch from Matthew Brades.

No functional change.

Document why is safe ttValue == VALUE_NONE

We can have ttValue == VALUE_NONE when we use a TT
slot to just save a position static evaluation, but
in this case we also save DEPTH_NONE so to avoid
using the ttValue in search. This happens to work,
but due to a number of lucky and tricky cases that
we now documnet through a bunch of asserts and a
little change to value_from_tt() that has no real
effect but clarifing the code.

No functional change.

Set TT size to 32 MB during 'bench'

On some platforms 128 MB of RAM for TT is too much,
so run 'bench' with the default 32 MB size.

No functional change although of course now 'bench'
reports a different number: 5545018

Move all Contempt Factor code to search.cpp

Where it is used.

No functional change.

Retire BitCount8Bit[] table

Use popcount() instead in the only calling place.
It is used only at initialization so there is no
speed regression and anyhow even initialization
itself is not slowed down: magic bitboard setup
stays around 175 msec on my slow 32bit Core Duo.

No functional change.

Use new 64 bit De Bruijn BitScan

Allows to sync 32 and 64 bits implementations.

Idea by Kim Walisch, reported by Gerd Isenberg:
http://talkchess.com/forum/viewtopic.php?t=45554

No functional change.

Retire can_return_tt() and rewirte TT-hit code

Simplify the code and doing this introduce a couple
of (very small) functional changes:

- Always compare to depth even in "mate value" condition
- TT cut-off in qsearch also in case of PvNode, as in search

Verified against regression with 2500 games at 30"+0.05
on 2 threads: 451 - 444 - 1602

Functional changed: new bench is 5544977

Scale contempt factor to zero at endgame

Contempt Factor is more effective at opening/middle game
and seems harmful at endgame phase. See:

http://chessprogramming.wikispaces.com/Contempt+Factor

http://web.archive.org/web/20070707023203/www.brucemo.com/compchess/programming/contempt.htm

Therefore we scale down the contempt factor while going
on with the game so to reach zero at endgame phase.

No functional change.

Fix a minor bug in search

As Joona says: "The problem is that when doing full
window search (-VALUE_INFINITE, VALUE_INFINITE), and
pruning all the moves will return fail low which is
mate score, because only clause touching alpha is
"mate distance pruning". So we are returning mate score
although we are just pruning all the moves. In reality
there probably is no mate in sight.

Bug spotted and fixed by Joona.

ARM lsb/msb assembly

Implement lsb/msb using armv7 assembly instructions.
msb is the easiest one, using a gcc intrinsic that generates
code using the ARM's clz instruction. lsb is also using this
clz instruction, but with the help of ARM's 'rbit' (bit
reversing) instruction. This leads to a >2% speed gain.

I also renamed 'arm-32' to the more meaningfull 'armv7' in the Makefile

No functional change.

Introduce arm-32 ARCH in Makefile

No functional change.

Retire is_dangerous() and inline its content

No functional change.

Rearrange prefetch code

No functional change.

Merge pull request #29 from RyanTaker/patch-3

Add Contempt Factor to Polyglot.ini

Add Contempt Factor in Polyglot

The contempt factor was previously not included in polyglot.ini

Sync qsearch with search

Port to qsearch() the same changes we recently
added to search().

Overall this search refactoring series shows
almost 2% speed up on gcc compile.

No functional change.

Improve compatibility with older versions of Mac OS X

Use the -mmacosx-version-min flag to support older versions of Mac OS X
(like version 10.6 and 10.7) when compiled on a machine running version
10.8.

Fix POPCNT support on mingw 64

When using asm 'popcnt' instruction the given
operand registers must be of the same type.

No functional change.

Fix mingw compile with ARCH=x86-64

When using the Makefile (as for the mingw case),
IS_64BIT and USE_BSFQ are already set with
ARCH=x86-64 and do not need to be redefined.

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

Fix Contempt Factor implementation

First disable Contempt Factor during analysis, then
calculate the modified draw score from the point of
view of the player, so from the point of view of
RootPosition color.

Thanks to Ryan Taker for suggesting the fixes.

No functional change.

Fix fallouts from previous patch

These kind of arch specific code is really nasty
to make it right becuase you need to verify on
all the platforms.

Now should compile properly also on ARM

Reported by Jean-Francois.

No functional change.

Allow prefetching on non-x86 platforms with gcc

In particular on ARM processors. Original patch by
Jean-Francois, sligtly modified by me to preserve
the meaning of NO_PREFETCH flag.

Verified with gcc, clang and icc that prefetch instruction
is correctly created.

No functional change.

Retire futility_move_count()

And remove (bestValue < beta) condition from
moves loop.

No functional change.

Rewrite search best value update

A simplification and also a small speed-up of
about 1% mainly due to reducing calls to
thisThread->cutoff_occurred().

Worst case split point recovering time after a
cut-off occurred is limited to 3 msec on my slow
PC, and usually is below 1 msec, so it seems safe
to remove the cutoff_occurred() check.

No functional change.

Add experimental contempt factor

This is very crude and very basic: simply in case
of a draw for repetition or 50 moves rule return
a negative score instead of zero according to the
contempt factor (in centipawns). If contempt is
positive engine will try to avoid draws (to use
with weaker opponents), if negative engine will
try to draw. If zero (default) there are no changes.

No functional change.

Retire EasyMoveMargin

Use a value related to PawnValue instead.

This is a different patch from previous one because
could affect game play and skill levels, although
in a mostly unmeasurable way. Indeed thresold has
been raised so easy move is a bit harder to trigger
and skill level is a bit more prone to blunders.

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

Don't hide thresolds values

Show the real value in the code, not hide it
behind a variable name, especially when there
is only once occurence.

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

Further push singular extension

Extend for an extra half-ply in case the node is (probably)
going to fail high. In this case the added overhead is limited.

A novelity is the way this patch has been tested: Always in
self-play but with a much longer TC to allow the singular
extension to fully kick in and also (my impression) to have
less noisy results.

Ater 1015 games on my QUAD at 60"+0.05
Mod vs Orig 173 - 150 - 692 ELO +8

Further rearrange search()

No functional change.

Don't push on the stack 200KB in one go

This could be a limit on some platforms (as it seems
to be in Native Client). Patch from a SF fork on github:

https://github.com/ccherng/Stockfish/commit/47374afd6fdfabd9de183a7a67d645daad45fb21

No functional change.

Add support for node limited search

Handle also the SMP case. This has been quite tricky, not
trivial to enforce the node limit in SMP case becuase
with "helpful master" concept we can have recursive split
points and we cannot lock them all at once so there is the
risk of counting the same nodes more than once.

Anyhow this patch should be race free and counted nodes are
correct.

No functional change.

Skip some useless initializations in search()

And rearrange a bit the initialization code. Still
some polishing to do, but it is a first step.

No functional change.

Don't need to early check PV moves for legality

As long as isPvMove (renamed to pvMove) is set after
legality check, we can postpone legality even in PV case.

Patch aligns the PV case with the common non-pv one.

No functional change.

Drop a magic in book.cpp

Mask out move's spacial flags without relying
on internal Move representation.

No functional change.

Tweaks to bitcount functions

Seems even a bit faster now (almost 1% in 32bit case).

No functional change.

Restore development version

Stockfish 2.3.1

Stockfish bench signature is: 5423738

Bonus for rook/queen attacking pawns on same rank

Patch and tuning by Gary Linscott from an idea of Ryan Taker.

Double tested by Gary:

Wins: 3390 Losses: 2972 Draws: 11323
LOS: 99.999992%
ELO: 8.213465 +- 99%: 6.746506 95%: 5.124415
Win%: 51.181792 +- 99%: 0.969791 95%: 0.736740

And by me:

After 5612 games 1255  1085  3271 +11 ELO

Fix compile on 64 bits

Reported by Quocvuong82.

No functional change.

Simplify BSFTable initialization

No functional change.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

Fix crash under Chess 960

We have a crash with this position:

rkqbnnbr/pppppppp/8/8/8/8/PPPPPPPP/RKQBNNBR w HAha -

What happens is that even if we are castling QUEEN_SIDE,
in this case we have kfrom (B8) < kto (C8) so the loop
that checks for attackers runs forever leading to a crash.

The fix is to check for (kto > kfrom) instead of
Side == KING_SIDE, but this is slower in the normal case of
ortodhox chess, so rewrite generate_castle() to handle the
chess960 case as a template parameter and allow the compiler
to optimize out the comparison in case of normal chess.

Reported by Ray Banks.

Rename class Book to PolyglotBook

And move struct BookEntry out of the header where it is
not needed.

No functional change.

Fix KpsK endgame

Broken by commit a44c5cf4f77b05a03 of 3 /12 / 2011 that
was labeled "No functional change" because our 'bench'
test didn't triggered that particular endgame. Indeed
we need to run a specific bench on a set of endgames
position when touching endgame.cpp because normal bench
does not cover endgames properly.

Found by MSVC 2012 code analyzer.

Restore development version

No functional change.

Stockfish 2.3

Stockfish bench signature is: 5416292

Fix compile with Intel 13.0

It seems Intel is unable to properly workout templates with 'static'
storage specifier.

Workaround using an anonymous namespace instead.

No functional change.

Don't exit earlier from aspiration window loop

Currently we exit the loop when

abs(bestValue) >= VALUE_KNOWN_WIN

but there is no logical reason for this. It seems more
natural to re-search again with full open window.

This has practically no impact in most cases, we have a
'no functional change' running 'bench' command.

Fix MSVC 2012 64bits warnings

Reported by Rein.

No functional change.

Speed-up generate<LEGAL>

The trick here is to check for legality only in the
(rare) cases we have pinned pieces or a king move
or an en-passant.

This trick is able to increase the speed of perft
of more then 20%!

No functional change.

Remove redundancy in move generation

Introduce generate_all_moves() and remove a good
bunch of redundant code.

No functional change.

Simplify generate_castle()

Skipping the calls to std::min(), std::man() we get
even a nice speed-up on perft.

No functional change.

Rename *last to *end

It is a more correct name because it points past the
last move of the list.

No functional change.

Enable link time optimization only when optimizing

Because it is quite slow, skip it when 'optimize' flag is 'no'

No functional change.

Revert "Simplify Option c'tor"

std::to_string() is C++11 material, not c++03.

So revert the patch.

Simplify Option c'tor

No functional change.

Get rid of struct Time

We just need the milliseconds of current system
time for our needs. This allows to simplify the
API.

No functional change.

Rename current_time() to now()

Follow C++11 naming conventions.

No functional change.

Greatly speed up SEE

Simply reshuffling the code inverting the condition in next_attacker()
yields a miraculous speed up of more than 3% under gcc!

On my laptop a bench run goes from 320Knps to 330Knps

No functional change.