Introduce Counter Move History tables

Introduce a counter move history table which additionally is indexed by the last move's piece and target square.
For quiet move ordering use now the sum of standard and counter move history table.

STC:
LLR: 2.96 (-2.94,2.94) [-1.50,4.50]
Total: 4747 W: 1005 L: 885 D: 2857

LTC:
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 5726 W: 1001 L: 872 D: 3853

Because of reported low NPS on multi core test
STC (7 threads):
ELO: 7.26 +-3.3 (95%) LOS: 100.0%
Total: 14937 W: 2710 L: 2398 D: 9829

Bench: 7725341

Resolves #282

Use thread specific mutexes instead of a global one.

This is necessary to improve the scalability with high number of cores.

There is no functional change in a single thread mode.

Resolves #281

Retire spinlocks

Use Mutex instead.

This is in preparaation for merging with master branch,
where we stilll don't have spinlocks.

Eventually spinlocks will be readded in some future
patch, once c++11 has been merged.

No functional change.

Cleanup thread_win.h

No functional change.

Disable spinlocks

To allow testing on fishtest.

No functional change.

Add thread_win32.h header

Workaround slow std::thread implementation in mingw
and gcc for Windows with our own old low level thread
functions.

No functional change.

Sync with master

bench: 8285241

Sync with master

No functional change.

Transform minKingPawnDistance into a local variable

minKingPawnDistance is used only as local variable in one place so we don't need it to be part of "Pawns::Entry" structure.

No functional change.

Resolves #277

Update Makefile for Mac OS X compilation

This change in the Makefile restores the possibility to compile
Stockfish on Mac OS X 10.9 and 10.10 after the C++11 has been merged.

To use the default (fastest) settings, compile with:

make build ARCH=x86-64-modern

To test the clang settings, compile with

make build ARCH=x86-64-modern COMP=clang

Beware that the clang settings may provide a slightly slower (6%)
executable.

Backported from master.

No functional change

Resolves #275

Re-enable spinlocks

For branch C++11, that doe snot run on fishtest,
there is no need of this kludge, let only master
have it.

No functional change.

Revert C++11 merge

Restore the state of repo back to commit 'Simplify pawn code a bit' (1e6d21dbb6)

No functional change

Update Makefile for Mac OS X compilation

This change in the Makefile restores the possibility to compile
Stockfish on Mac OS X 10.9 and 10.10 after the C++11 has been merged.

To use the default (fastest) settings, compile with:

make build ARCH=x86-64-modern

To test the clang settings, compile with

make build ARCH=x86-64-modern COMP=clang

Beware that the clang settings may provide a slightly slower (6%)
executable.

No functional change

Resolves #275

Disable spinlocks

Now that c++11 branch has been merged in master,
disable unconditionally the spinlocks and use mutex
instead. This will allow to run fishtest even on HT
machines withouth changes.

In the future we will reintorduce spinlocks, once
we will have took care of fishtest.

No functional change.

Allow to disable spinlocks

And use mutex instead. You may never want to do this.
It is a workaround to run c++11 on fishtest where many
machiens have HTenabled and this can be a problem when
number of cores set is higher than number of physical cores.

To disable spinlocks, just compile with -DNO_SPINLOCK flag

No functional change.

Rename available_to()

Change this API to be more natural and simple.

Inspired by a patch by Joona.

No functional change.

Sync with master

bench: 8285241

Simplify pawn code a bit

Simplify a bit the number of bitwise operators used to calculate the
pawn evaluation in pawns.cpp

No functional change.

Resolves #269

Raise penalty for knight attacked by pawn

Raise a bit the penalty for knight attacked by pawn.

STC:
LLR: 2.97 (-2.94,2.94) [-1.50,4.50]
Total: 27744 W: 5563 L: 5380 D: 16801

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,4.00]
Total: 87571 W: 14747 L: 14314 D: 58510

Bench: 8285241

Resolves #270

Retire apply_weight()

Use the more natural operator*() instead.

No functional change.

Sync with master

bench: 8069601

Normalize twice supported pawns

Align codying style to current conventions and move
formula for twice supported pawns to Pawns::init()
where it should be.

No functional change.

Apex Pawns

Pawns which are supported already have a bonus. Apex are pawns which are
supported twice.
This patch gives an additional 50% bonus for them.

STC
LLR: 2.96 (-2.94,2.94) [-1.50,4.50]
Total: 6549 W: 1333 L: 1209 D: 4007

LTC
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 18002 W: 3037 L: 2850 D: 12115

Bench: 8069601

Resolves #267

Don't assume the type of Time::point

But instead use the proper definition. Also
rewrite chrono functions while there.

No functional change.

Small tweaks in pawns.cpp

No functional change.

Improve spinlock implementation

Calling lock.test_and_set() in a tight loop creates expensive
memory synchronizations among processors and penalize other
running threads. So syncronize only only once at the beginning
with fetch_sub() and then loop on a simple load() that puts much
less pressure on the system.

Reported about 2-3% speed up on various systems.

Patch by Ronald de Man.

No functional change.

Use spinlock instead of mutex for Threads and SplitPoint

It is reported to be defenitly faster with increasing
number of threads, we go from a +3.5% with 4 threads
to a +15% with 16 threads.

The only drawback is that now when testing with more
threads than physical available cores, the speed slows
down to a crawl. This is expected and was similar at what
we had setting the old sleepingThreads to false.

No functional change.

Introduce Spinlock class

Initialization is more complex than what I'd like due
to MSVC compatibility that for some reason does not like:

std::atomic_flag lock = ATOMIC_FLAG_INIT;

No functional change.

Sync with master

bench: 8253813

Fix build under OS X

Reported by Vince Negri

No functional change.

Sync with master

bench: 8253813

Use only 'level' as late join metric

It seems other metric are useless, this allow us
to simplify the code and to prune useless stuff.

STC 20K games 4 threads
ELO: -0.76 +-2.8 (95%) LOS: 29.9%
Total: 20000 W: 3477 L: 3521 D: 13002

STC 10K games 16 threads
ELO: 1.36 +-3.9 (95%) LOS: 75.0%
Total: 10000 W: 1690 L: 1651 D: 6659

bench: 8253813

Further refine SMP code

Backported from C++11 branch:

https://github.com/official-stockfish/Stockfish/commit/7ff965eebfbc17d2b
https://github.com/official-stockfish/Stockfish/commit/e74c2df907d5336d3d2b

Fully verified it is equivalent to master (see log msg
of individual commits for details).

No functional change.

Use sp->master instead of bestThread

Verified with:

dbg_hit_on(th != sp->master);

It is 100% equivalent on more than 200K hits.

No functional change.

Fix comment for kingAdjacentZoneAttacksCount

The comment for kingAdjacentZoneAttacksCount[] was bogus, using
reversed semantics for color.

No functional change

Resolves #262

Mobile phalanxes

Try to create mobile phalanxes

STC:
LLR: 2.97 (-2.94,2.94) [-1.50,4.50]
Total: 52393 W: 10912 L: 10656 D: 30825

LTC:
LLR: 2.96 (-2.94,2.94) [0.00,6.00]
Total: 30398 W: 5315 L: 5063 D: 20020

Bench: 8253813

Resolves #261

Improve comments in SMP code

No functional change.

Use range-based-for in late join

No functional change.

Sync with master

bench: 7911944

Clarify we don't late join with only 2 threads

Thanks to Gary for pointing this out.

No functional change.

Use size_t consistently across thread code

No functional change.

Retire redundant sp->slavesCount field

It should be used slavesMask.count() instead.

Verified 100% equivalent when sp->allSlavesSearching:

dbg_hit_on(sp->allSlavesSearching, sp->slavesCount != sp->slavesMask.count());

No functional change.

Fix a warning under MSVC

Assignment of size_t to int.

No functional change.

Add a couple of asserts to late join

Document and clarify that we cannot rejoin on ourselves
and that we never late join if we are master and all
slaves have finished, inded in this case we exit idle_loop.

No functional change.

Remove useless condition in late join

In case of Threads.size() == 2 we have that sp->allSlavesSearching
is always false (because we have finished our search), bestSp is
always NULL and we never late join, so there is no need to special
case here.

Tested with dbg_hit_on(sp && sp->allSlavesSearching) and
verified it never fires.

No functional change.

Compute SplitPoint::spLevel on the fly

And retire a redundant field. This is important also
from a concept point of view becuase we want to keep
SMP structures as simple as possible with the only
strictly necessary data.

Verified with

dbg_hit_on(sp->spLevel != level)

that the values are 100% the same out of more 50K samples.

No functional change.

Simplify attackUnits formula

Use '/ 8' instead of '* 31 / 256'

Passed STC
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 55077 W: 10999 L: 10940 D: 33138

And LTC
LLR: 2.95 (-2.94,2.94) [-3.00,1.00]
Total: 14751 W: 2530 L: 2400 D: 9821

bench: 7911944

Improve smp performance for high number of threads

Balance threads between split points.

There are huge differences between different machines and autopurging makes it very difficult to measure the improvement in fishtest, but the following was recorded for 16 threads at 15+0.05:

    For Bravone (1000 games): 0 ELO
    For Glinscott (1000 games): +20 ELO
    For bKingUs (1000 games): +50 ELO
    For fastGM (1500 games): +50 ELO

The change was regression for no one, and a big improvement for some, so it should be fine to commit it.
Also for 8 threads at 15+0.05 we measured a statistically significant improvement:
ELO: 6.19 +-3.9 (95%) LOS: 99.9%
Total: 10325 W: 1824 L: 1640 D: 6861

Finally it was verified that there was no (significant) regression for

4 threads:
ELO: 0.09 +-2.8 (95%) LOS: 52.4%
Total: 19908 W: 3422 L: 3417 D: 13069

2 threads:
ELO: 0.38 +-3.0 (95%) LOS: 60.0%
Total: 19044 W: 3480 L: 3459 D: 12105

1 thread:
ELO: -1.27 +-2.1 (95%) LOS: 12.3%
Total: 40000 W: 7829 L: 7975 D: 24196

Resolves #258

Compute checkers from scratch

This micro-optimization only complicates the code and provides no benefit.
Removing it is even a speedup on my machine (i7-3770k, linux, gcc 4.9.1):

stat        test     master    diff
mean   2,403,118  2,390,904  12,214
stdev     12,043     10,620   3,677

speedup       0.51%
P(speedup>0) 100.0%

No functional change.

Retire one do_move() overload

After Lucas patch it is almost useless.

No functional change.

Compute checkers from scratch

This micro-optimization only complicates the code and provides no benefit.
Removing it is even a speedup on my machine (i7-3770k, linux, gcc 4.9.1):

stat        test     master    diff
mean   2,403,118  2,390,904  12,214
stdev     12,043     10,620   3,677

speedup       0.51%
P(speedup>0) 100.0%

No functional change.

Revert "Delayed killers checking"

It seems a slowdown when run with fishbench.

No functional change.

Further simplify KingDanger init

And remove a tale whitespace while there.

No functional change.

Further simplify KingDanger init

And remove a tale whitespace while there.

No functional change.

Sync with master

Bench: 7369224

Small bonus for all safe pawn pushes

Pawn flexibility: add a small bonus for all safe pawn pushes

STC:
LLR: 2.70 (-2.94,2.94) [-1.50,4.50]
Total: 18233 W: 3705 L: 3557 D: 10971

LTC:
LLR: 2.97 (-2.94,2.94) [0.00,6.00]
Total: 17684 W: 3042 L: 2854 D: 11788

Bench: 7369224

Resolves #253

Reformat tracing functions

No functional change.

Fix KingDanger[] array initialization

Use integer arithmetic instead of floating point arithmetic.
Floating point arithmetic was causing different results for some 32-bit compiles

No functional change

Resolves #249
Resolves #250

Sync with master

bench: 7699138

Pawn Center Bind Bonus

Bonus for two pawns controlling the same central square

STC:

LLR: 3.14 (-2.94,2.94) [-1.50,4.50]
Total: 15974 W: 3291 L: 3133 D: 9550

LTC:

LLR: 3.24 (-2.94,2.94) [0.00,6.00]
Total: 10449 W: 1837 L: 1674 D: 6938

Idea from Lyudmil Tsvetkov.

Bench: 7699138

Resolves #248

Shuffle put_piece() and friends signatures

It is more consistent with the others member functions.

No functional change.

Small tweaks in do_move and friends

Also remove useless StateCopySize64 optimization:
compiler uses SSE movups instruction anyhow and
does not need this trick (verified with fishbench).

No functional change.

Avoid casting to char* in prefetch()

Funny enough, gcc __builtin_prefetch() expects
already a void*, instead Windows's _mm_prefetch()
requires a char*.

The patch allows to remove ugly casts from caller
sites.

No functional change.

Rewrite pos_is_ok()

No functional change.

Micro-optimize SEE

Results for 10 tests for each version (gcc 4.8.3 on mingw):

            Base      Test      Diff
    Mean    1502447   1507917   -5470
    StDev   3119      1364      4153

p-value: 0,906
speedup: 0,004

Results for 10 tests for each version (MSVC 2013):

            Base      Test      Diff
    Mean    1400899   1403713   -2814
    StDev   1273      2804      2700

p-value: 0,851
speedup: 0,002

No functional change.

Rename dbg_hit_on_c() to dbg_hit_on()

Use an overload instead of a new named function.

I have found this handier and easier when adding
some quick debug code.

No functional change.

Rename dbg_hit_on_c() to dbg_hit_on()

Use an overload instead of a new named function.

I have found this handier and easier when adding
some quick debug code.

No functional change.

Sync with master

bench: 7696257

Removes useless templates, some of which lead to code duplication: is_K*() functions.

No functional change

Resolves #245

Add bonus for pawn attack threats

Latent pawn attacks: Add a bonus to safe pawn pushes which attacks an
enemy piece.  Based on an idea of Lyudmil Tsvetkov.

STC:
LLR: 2.95 (-2.94,2.94) [-1.50,4.50]
Total: 7925 W: 1666 L: 1537 D: 4722

LTC:
LLR: 2.95 (-2.94,2.94) [0.00,6.00]
Total: 40109 W: 6841 L: 6546 D: 26722

Bench: 7696257

Resolves #240

Profile build options

I went through all the individual compile options that differ between
-fprofile-generate/-fprofile-use  and  -fprofile-arcs/-fbranch-probabilities
and distilled the speed difference down to only turning off
-fno-peel-loops and -fno-tracer.  Using this we still get the full speedup
(maybe a bit more because other optimizations stay on) and it's also much cleaner
because we can get rid of the "@rm -f ucioption.gc*" hack for all versions of gcc.

No functional change.

Resolves #237

Improved King Safety values

From an SPSA-session on king safety.

STC:
ELO: 3.21 +-2.1 (95%) LOS: 99.8%
Total: 40000 W: 8181 L: 7812 D: 24007

LTC:
LLR: 2.95 (-2.94,2.94) [0.00,4.00]
Total: 47765 W: 8091 L: 7785 D: 31889

Bench: 8589262

Resolves #241

Use move assignment in movegen.h

No functional change and same speed (tested with perft)

Allow to assign a Move to an ExtMove

After defining ExtMove::operator Move(), this is a
natural extension.

No fnctional change.

Delay checking for duplicated killer moves

Follow the usual approach to delay computation
as far as possible, in case an earlier killer
cut-offs we avoid to do useless work.

This also greatly simplifies the code.

No functional change.

Small tweaks in movepick.cpp

No functional change.

Silence a warning under MSVC

warning C4100: 'ci' : unreferenced formal parameter

It is a silly and wrong one, but just silent it.

No functional change.

More readable score<CAPTURES>()

No functional change.

Use C++11 loops in MovePicker

No functional change.

Implicit conversion from ExtMove to Move

Verified with perft there is no speed regression,
and code is simpler. It is also conceptually correct
becuase an extended move is just a move that happens
to have also a score.

No functional change.

Another small tweak to skills

No functional change.

Sync with master

bench: 7374604

Use C++ loops in insert_pv_in_tt

Also small tweak to extract_ponder_from_tt

No functional change.

Move uci_pv under UCI namespace

That's the correct place.

No functional change.

Convert Reductions[] from int8_t to Depth

This is the type anyhow. Assorted cleanup while there.

No functional change.

Fix a MSVC warning

warning C4805: '|' : unsafe mix of type 'Bitboard' and type 'bool' in operation

No functional change.

Ressurrect hashfull patch

This is an old patch from Jean-Francois Romang to send
UCI hashfull info to the GUI:
https://github.com/mcostalba/Stockfish/pull/60/files

It was wrongly judged as a slowdown, but it takes much
less than 1 ms to run, indeed on my core i5 2.6Ghz it
takes about 2 microsecs to run!

Regression test is good:

STC
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 7352 W: 1548 L: 1401 D: 4403

LTC
LLR: 2.96 (-2.94,2.94) [-3.00,1.00]
Total: 61432 W: 10307 L: 10251 D: 40874

I have set the name of the author to the original
one.

No functional change.

Sync with master

bench: 7374604

Simplify skill level and reduce ELO

This patch has two positive effects:

- Retire a hackish formula and leave
  just a natural, simple and plain one.

- Reduce strenght at very low level, but
  don't impact medium/high levels.

Actually even at level 0, SF is still too
strong for many beginners (this was reported
many times for instance on Droidfish user
comments on Google Play).

Test on fishtest shows that ELO drop is around
170 ELO at level 0 (good!), 130 ELO at level 1
and smoothly reduces (as expected) until level
10 where the drop is just of 8 ELO.

No functional change.

Simplify backward pawn definition

Make use of 'lever' attribute

No functional change

Resolves #234

King safety tuning with values obtained by SPSA.

Part I:

LTC:

LLR: 2.96 (-2.94,2.94) [0.00,4.00]
Total: 11529 W: 2075 L: 1882 D: 7572

Part II:

LTC:

ELO: 2.07 +-2.1 (95%) LOS: 97.3%
Total: 34859 W: 5967 L: 5759 D: 23133

Bench: 7374604

Resolves #228

Restore development version

No functional change

Stockfish 6

Stockfish bench signature is: 8918745

Stockfish 6 Release Candidate 3

- Fix a skill level problem: Don't allow move pruning at root node
- Revert "Fix profile build for gcc on Mac OSX". Results for a faster binary in x86-64.
- Fix a MSVC warning

Bench: 8918745

Fix a skill level problem: Don't allow move pruning at root node

Bench: 8918745

Resolves #231

Revert "Fix profile build for gcc on Mac OSX"

Seems to be a performance regression for standard build.

For SF6 people compiling on Mac OSX using profile-build option
just need to make necessary adjustments manually...

No functional change

Resolves #223

Re-arrange Skill struct

Instead of swapping sub-optimal move in Skill
d'tor, make it explicitly at the end of the search.

Also streamline and clarify relation with multiPV
and pass it directly instead of relying on the hacky
'candidates' member.

No functional change.

Fix a MSVC warning at W4

Warning is C4512 (assignment operator could not be generated)

Now, apart the foreign syzygy code, everything compiles
without warnings at warning level 4.

Backported from C++11 branch.

No functional change.

Stockfish 6 Release Candidate 2

- Fix a compilation issue related to BMI2 PEXT instruction
- Retrieve a ponder move from TT if PV is only one move long

Bench: 8080602

No functional change

Don't use _pext_u64() directly

This intrinsic to call BMI2 PEXT instruction is
defined in immintrin.h. This header should be
included only when USE_PEXT is defined, otherwise
we define _pext_u64 as 0 forcing a nop.

But under some mingw platforms, even if we don't
include the header, immintrin.h gets included
anyhow through an include chain that starts with
STL <algorithm> header. So we end up both defining
_pext_u64 function and at the same time defining
_pext_u64 as 0 leading to a compile error.

The correct solution is of not using _pext_u64 directly.

This patch fixes a compile error with some mingw64
package when compiling with x86-64.

No functional change.

Resolves #222