Merge Gary's king safety tweak
authorMarco Costalba <mcostalba@gmail.com>
Fri, 15 Feb 2013 15:21:15 +0000 (07:21 -0800)
committerMarco Costalba <mcostalba@gmail.com>
Fri, 15 Feb 2013 15:25:33 +0000 (16:25 +0100)
Still well within error bars, so probably not a big improvement,
but may be worthwhile. I will let the test keep running. The idea
for the tweak came from the TCEC game against Houdini. Stockfish saw
it as a draw, well past when it should have seen problems. King safety
was off, since it was QN and pawns only, but in fact the king was
quite vulnerable.

After 8000 games at 60/1 (Gary's test)

ELO: -0.43 +- 99%: 10.02 95%: 7.62
Wins: 1235 Losses: 1245 Draws: 5520 Total: 8000

PGN of game against houdini. Moves 55-59 it was seeing a draw, and
Houdini was seeing a good sized advantage for black. With the change,
Stockfish now recognizes that moving the king there is a bad idea.

[Event "nTCEC - Stage 1 - Season 1"]
[Site "http://www.tcec-chess.net"]
[Date "2013.02.07"]
[Round "4.2"]
[White "Stockfish 2.31"]
[Black "Houdini 3.0"]
[Result "0-1"]
[Variant "normal"]

1. Nf3 Nf6 2. c4 e6 3. Nc3 Bb4 4. Qc2 O-O 5. a3 Bxc3 6. Qxc3 b6 7. b4 a5 8. Bb2
axb4 9. axb4 Rxa1+ 10. Bxa1 Na6 11. e3 Qe7 12. b5 Nc5 13. Qc2 Bb7 14. Be2 d6
15. O-O Ra8 16. Bb2 h6 17. Ra1 Rxa1+ 18. Bxa1 e5 19. Qa2 Be4 20. Ne1 Bg6
21. Bb2 Kh7 22. f3 Nfd7 23. Bc3 h5 24. Qa1 h4 25. Kf1 Qf6 26. Qa7 Qd8 27. Qa2
e4 28. Qa1 h3 29. g3 exf3 30. Nxf3 Bf5 31. Bd4 g6 32. Kf2 Kg8 33. Qa3 Bg4
34. d3 Qc8 35. Bxc5 bxc5 36. Ke1 Qb7 37. e4 Bxf3 38. Bxf3 Ne5 39. Be2 Qc8
40. Qa6 Qd8 41. Qa5 Kh7 42. Kd1 Kg7 43. Qa7 Kg8 44. Qa5 Kh7 45. Qa7 Kg7 46. Qa5
Qb8 47. Kd2 Kh7 48. Kc2 Kg8 49. Qa6 Qd8 50. Qa5 Qf6 51. Qe1 Kg7 52. Qf1 Qe6
53. Qe1 Qd7 54. Qc1 Qe8 55. Kc3 Qa8 56. Kb3 Kh7 57. Qa3 Qd8 58. Qc1 c6 59. Qc3
Qb6 60. Ka4 Qb7 61. Qd2 Nd7 62. Qc3 Qa7+ 63. Kb3 Kg8 64. Bg4 cxb5 65. cxb5 Nb6
66. Bxh3 Qa4+ 67. Kb2 Qd1 68. Ka3 Qe2 69. Kb3 Qh5 70. Bg2 Qxh2 71. Qf6 Qxg3
72. Bf1 Qe3 73. Kc2 Na4 74. b6 Nxb6 75. Qd8+ Kg7 76. Qxb6 Qf2+ 77. Kc3 Qxf1
78. Qxd6 Qf6+ 79. Qxf6+ Kxf6 80. Kc4 g5 81. Kxc5 Ke5 82. d4+ Kxe4 83. d5 g4
84. d6 g3 85. d7 g2 86. d8=Q g1=Q+ 87. Kb5 Qb1+ 88. Ka4 Qa2+ 89. Kb4 f5
90. Qe8+ Kf4 91. Qg6 Qd5 92. Qg1 Qe4+ 93. Ka5 Qe2 94. Qg8 Kf3 95. Qd5+ Qe4
96. Qd1+ Kg2 97. Qd2+ Kf1 98. Qh2 f4 99. Qh3+ Ke2 100. Qg4+ Kd2 101. Qg5 Kc2
102. Qh4 0-1

bench: 5518286

14 files changed:
src/bitbase.cpp
src/bitboard.h
src/endgame.cpp
src/movepick.cpp
src/notation.cpp
src/position.cpp
src/search.cpp
src/search.h
src/thread.cpp
src/thread.h
src/tt.cpp
src/tt.h
src/types.h
src/uci.cpp

index 5f0438a..ef067c6 100644 (file)
 */
 
 #include <cassert>
+#include <vector>
 
 #include "bitboard.h"
 #include "types.h"
 
 namespace {
 
+  // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
+  const unsigned IndexMax = 2*24*64*64; // stm * psq * wksq * bksq = 196608
+
+  // Each uint32_t stores results of 32 positions, one per bit
+  uint32_t KPKBitbase[IndexMax / 32];
+
+  // A KPK bitbase index is an integer in [0, IndexMax] range
+  //
+  // Information is mapped in a way that minimizes number of iterations:
+  //
+  // bit  0- 5: white king square (from SQ_A1 to SQ_H8)
+  // bit  6-11: black king square (from SQ_A1 to SQ_H8)
+  // bit    12: side to move (WHITE or BLACK)
+  // bit 13-14: white pawn file (from FILE_A to FILE_D)
+  // bit 15-17: white pawn 6 - rank (from 6 - RANK_7 to 6 - RANK_2)
+  unsigned index(Color us, Square bksq, Square wksq, Square psq) {
+    return wksq + (bksq << 6) + (us << 12) + (file_of(psq) << 13) + ((6 - rank_of(psq)) << 15);
+  }
+
   enum Result {
     INVALID = 0,
     UNKNOWN = 1,
@@ -35,198 +55,118 @@ namespace {
 
   struct KPKPosition {
 
-    Result classify_leaf(int idx);
-    Result classify(int idx, Result db[]);
+    operator Result() const { return res; }
+    Result classify_leaf(unsigned idx);
+    Result classify(const std::vector<KPKPosition>& db)
+    { return us == WHITE ? classify<WHITE>(db) : classify<BLACK>(db); }
 
   private:
-    template<Color Us> Result classify(const Result db[]) const;
-
-    template<Color Us> Bitboard k_attacks() const {
-      return Us == WHITE ? StepAttacksBB[W_KING][wksq] : StepAttacksBB[B_KING][bksq];
-    }
-
-    Bitboard p_attacks() const { return StepAttacksBB[W_PAWN][psq]; }
-    void decode_index(int idx);
+    template<Color Us> Result classify(const std::vector<KPKPosition>& db);
 
-    Square wksq, bksq, psq;
-    Color stm;
+    Color us;
+    Square bksq, wksq, psq;
+    Result res;
   };
 
-  // The possible pawns squares are 24, the first 4 files and ranks from 2 to 7
-  const int IndexMax = 2 * 24 * 64 * 64; // stm * wp_sq * wk_sq * bk_sq = 196608
-
-  // Each uint32_t stores results of 32 positions, one per bit
-  uint32_t KPKBitbase[IndexMax / 32];
+} // namespace
 
-  int index(Square wksq, Square bksq, Square psq, Color stm);
-}
 
+bool Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color us) {
 
-uint32_t Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm) {
+  assert(file_of(wpsq) <= FILE_D);
 
-  int idx = index(wksq, bksq, wpsq, stm);
-  return KPKBitbase[idx / 32] & (1 << (idx & 31));
+  unsigned idx = index(us, bksq, wksq, wpsq);
+  return KPKBitbase[idx / 32] & (1 << (idx & 0x1F));
 }
 
 
 void Bitbases::init_kpk() {
 
-  Result* db = new Result[IndexMax]; // Avoid to hit stack limit on some platforms
-  KPKPosition pos;
-  int idx, bit, repeat = 1;
+  unsigned idx, repeat = 1;
+  std::vector<KPKPosition> db(IndexMax);
 
-  // Initialize table with known win / draw positions
+  // Initialize db with known win / draw positions
   for (idx = 0; idx < IndexMax; idx++)
-      db[idx] = pos.classify_leaf(idx);
+      db[idx].classify_leaf(idx);
 
-  // Iterate until all positions are classified (30 cycles needed)
+  // Iterate until all positions are classified (15 cycles needed)
   while (repeat)
       for (repeat = idx = 0; idx < IndexMax; idx++)
-          if (db[idx] == UNKNOWN && (db[idx] = pos.classify(idx, db)) != UNKNOWN)
+          if (db[idx] == UNKNOWN && db[idx].classify(db) != UNKNOWN)
               repeat = 1;
 
-  // Map 32 position results into one KPKBitbase[] entry
-  for (idx = 0; idx < IndexMax / 32; idx++)
-      for (bit = 0; bit < 32; bit++)
-          if (db[32 * idx + bit] == WIN)
-              KPKBitbase[idx] |= 1 << bit;
-
-  delete [] db;
+  // Map 32 results into one KPKBitbase[] entry
+  for (idx = 0; idx < IndexMax; idx++)
+      if (db[idx] == WIN)
+          KPKBitbase[idx / 32] |= 1 << (idx & 0x1F);
 }
 
 
 namespace {
 
-  // A KPK bitbase index is an integer in [0, IndexMax] range
-  //
-  // Information is mapped in this way
-  //
-  // bit     0: side to move (WHITE or BLACK)
-  // bit  1- 6: black king square (from SQ_A1 to SQ_H8)
-  // bit  7-12: white king square (from SQ_A1 to SQ_H8)
-  // bit 13-14: white pawn file (from FILE_A to FILE_D)
-  // bit 15-17: white pawn rank - 1 (from RANK_2 - 1 to RANK_7 - 1)
-
-  int index(Square w, Square b, Square p, Color c) {
-
-    assert(file_of(p) <= FILE_D);
-
-    return c + (b << 1) + (w << 7) + (file_of(p) << 13) + ((rank_of(p) - 1) << 15);
-  }
-
-  void KPKPosition::decode_index(int idx) {
+  Result KPKPosition::classify_leaf(unsigned idx) {
 
-    stm  = Color(idx & 1);
-    bksq = Square((idx >> 1) & 63);
-    wksq = Square((idx >> 7) & 63);
-    psq  = File((idx >> 13) & 3) | Rank((idx >> 15) + 1);
-  }
-
-  Result KPKPosition::classify_leaf(int idx) {
-
-    decode_index(idx);
+    wksq = Square((idx >> 0) & 0x3F);
+    bksq = Square((idx >> 6) & 0x3F);
+    us   = Color((idx >> 12) & 0x01);
+    psq  = File((idx >> 13) & 3) | Rank(6 - (idx >> 15));
 
     // Check if two pieces are on the same square or if a king can be captured
     if (   wksq == psq || wksq == bksq || bksq == psq
-        || (k_attacks<WHITE>() & bksq)
-        || (stm == WHITE && (p_attacks() & bksq)))
-        return INVALID;
-
-    // The position is an immediate win if it is white to move and the white
-    // pawn can be promoted without getting captured.
-    if (   rank_of(psq) == RANK_7
-        && stm == WHITE
-        && wksq != psq + DELTA_N
-        && (   square_distance(bksq, psq + DELTA_N) > 1
-            ||(k_attacks<WHITE>() & (psq + DELTA_N))))
-        return WIN;
-
-    // Check for known draw positions
-    //
-    // Case 1: Stalemate
-    if (   stm == BLACK
-        && !(k_attacks<BLACK>() & ~(k_attacks<WHITE>() | p_attacks())))
-        return DRAW;
-
-    // Case 2: King can capture undefended pawn
-    if (   stm == BLACK
-        && (k_attacks<BLACK>() & psq & ~k_attacks<WHITE>()))
-        return DRAW;
-
-    // Case 3: Black king in front of white pawn
-    if (   bksq == psq + DELTA_N
-        && rank_of(psq) < RANK_7)
-        return DRAW;
-
-    // Case 4: White king in front of pawn and black has opposition
-    if (   stm == WHITE
-        && wksq == psq + DELTA_N
-        && bksq == wksq + DELTA_N + DELTA_N
-        && rank_of(psq) < RANK_5)
-        return DRAW;
-
-    // Case 5: Stalemate with rook pawn
-    if (   bksq == SQ_A8
-        && file_of(psq) == FILE_A)
-        return DRAW;
-
-    // Case 6: White king trapped on the rook file
-    if (   file_of(wksq) == FILE_A
-        && file_of(psq) == FILE_A
-        && rank_of(wksq) > rank_of(psq)
-        && bksq == wksq + 2)
-        return DRAW;
-
-    return UNKNOWN;
+        || (StepAttacksBB[KING][wksq] & bksq)
+        || (us == WHITE && (StepAttacksBB[PAWN][psq] & bksq)))
+        return res = INVALID;
+
+    if (us == WHITE)
+    {
+        // Immediate win if pawn can be promoted without getting captured
+        if (   rank_of(psq) == RANK_7
+            && wksq != psq + DELTA_N
+            && (   square_distance(bksq, psq + DELTA_N) > 1
+                ||(StepAttacksBB[KING][wksq] & (psq + DELTA_N))))
+            return res = WIN;
+    }
+    // Immediate draw if is stalemate or king captures undefended pawn
+    else if (  !(StepAttacksBB[KING][bksq] & ~(StepAttacksBB[KING][wksq] | StepAttacksBB[PAWN][psq]))
+             || (StepAttacksBB[KING][bksq] & psq & ~StepAttacksBB[KING][wksq]))
+        return res = DRAW;
+
+    return res = UNKNOWN;
   }
 
   template<Color Us>
-  Result KPKPosition::classify(const Result db[]) const {
+  Result KPKPosition::classify(const std::vector<KPKPosition>& db) {
 
-    // White to Move: If one move leads to a position classified as RESULT_WIN,
-    // the result of the current position is RESULT_WIN. If all moves lead to
-    // positions classified as RESULT_DRAW, the current position is classified
-    // RESULT_DRAW otherwise the current position is classified as RESULT_UNKNOWN.
+    // White to Move: If one move leads to a position classified as WIN, the result
+    // of the current position is WIN. If all moves lead to positions classified
+    // as DRAW, the current position is classified DRAW otherwise the current
+    // position is classified as UNKNOWN.
     //
-    // Black to Move: If one move leads to a position classified as RESULT_DRAW,
-    // the result of the current position is RESULT_DRAW. If all moves lead to
-    // positions classified as RESULT_WIN, the position is classified RESULT_WIN.
-    // Otherwise, the current position is classified as RESULT_UNKNOWN.
+    // Black to Move: If one move leads to a position classified as DRAW, the result
+    // of the current position is DRAW. If all moves lead to positions classified
+    // as WIN, the position is classified WIN otherwise the current position is
+    // classified UNKNOWN.
 
     Result r = INVALID;
-    Bitboard b = k_attacks<Us>();
+    Bitboard b = StepAttacksBB[KING][Us == WHITE ? wksq : bksq];
 
     while (b)
-    {
-        r |= Us == WHITE ? db[index(pop_lsb(&b), bksq, psq, BLACK)]
-                         : db[index(wksq, pop_lsb(&b), psq, WHITE)];
-
-        if (Us == WHITE && (r & WIN))
-            return WIN;
-
-        if (Us == BLACK && (r & DRAW))
-            return DRAW;
-    }
+        r |= Us == WHITE ? db[index(~Us, bksq, pop_lsb(&b), psq)]
+                         : db[index(~Us, pop_lsb(&b), wksq, psq)];
 
     if (Us == WHITE && rank_of(psq) < RANK_7)
     {
         Square s = psq + DELTA_N;
-        r |= db[index(wksq, bksq, s, BLACK)]; // Single push
+        r |= db[index(BLACK, bksq, wksq, s)]; // Single push
 
         if (rank_of(s) == RANK_3 && s != wksq && s != bksq)
-            r |= db[index(wksq, bksq, s + DELTA_N, BLACK)]; // Double push
-
-        if (r & WIN)
-            return WIN;
+            r |= db[index(BLACK, bksq, wksq, s + DELTA_N)]; // Double push
     }
 
-    return r & UNKNOWN ? UNKNOWN : Us == WHITE ? DRAW : WIN;
+    if (Us == WHITE)
+        return res = r & WIN  ? WIN  : r & UNKNOWN ? UNKNOWN : DRAW;
+    else
+        return res = r & DRAW ? DRAW : r & UNKNOWN ? UNKNOWN : WIN;
   }
 
-  Result KPKPosition::classify(int idx, Result db[]) {
-
-    decode_index(idx);
-    return stm == WHITE ? classify<WHITE>(db) : classify<BLACK>(db);
-  }
-
-}
+} // namespace
index 3590437..90dec81 100644 (file)
@@ -33,7 +33,7 @@ void print(Bitboard b);
 namespace Bitbases {
 
 void init_kpk();
-uint32_t probe_kpk(Square wksq, Square wpsq, Square bksq, Color stm);
+bool probe_kpk(Square wksq, Square wpsq, Square bksq, Color us);
 
 }
 
index d60ce39..8591676 100644 (file)
@@ -199,21 +199,21 @@ Value Endgame<KPK>::operator()(const Position& pos) const {
   assert(pos.piece_count(weakerSide, PAWN) == 0);
 
   Square wksq, bksq, wpsq;
-  Color stm;
+  Color us;
 
   if (strongerSide == WHITE)
   {
       wksq = pos.king_square(WHITE);
       bksq = pos.king_square(BLACK);
       wpsq = pos.piece_list(WHITE, PAWN)[0];
-      stm = pos.side_to_move();
+      us   = pos.side_to_move();
   }
   else
   {
       wksq = ~pos.king_square(BLACK);
       bksq = ~pos.king_square(WHITE);
       wpsq = ~pos.piece_list(BLACK, PAWN)[0];
-      stm  = ~pos.side_to_move();
+      us   = ~pos.side_to_move();
   }
 
   if (file_of(wpsq) >= FILE_E)
@@ -223,7 +223,7 @@ Value Endgame<KPK>::operator()(const Position& pos) const {
       wpsq = mirror(wpsq);
   }
 
-  if (!Bitbases::probe_kpk(wksq, wpsq, bksq, stm))
+  if (!Bitbases::probe_kpk(wksq, wpsq, bksq, us))
       return VALUE_DRAW;
 
   Value result = VALUE_KNOWN_WIN + PawnValueEg + Value(rank_of(wpsq));
@@ -471,6 +471,29 @@ ScaleFactor Endgame<KBPsK>::operator()(const Position& pos) const {
               return SCALE_FACTOR_DRAW;
       }
   }
+
+  // All pawns on same B or G file? Then potential draw
+  if (    (pawnFile == FILE_B || pawnFile == FILE_G)
+      && !(pos.pieces(PAWN) & ~file_bb(pawnFile))
+      && pos.non_pawn_material(weakerSide) == 0
+      && pos.piece_count(weakerSide, PAWN) >= 1)
+  {
+      // Get weaker pawn closest to opponent's queening square
+      Bitboard wkPawns = pos.pieces(weakerSide, PAWN);
+      Square weakerPawnSq = strongerSide == WHITE ? msb(wkPawns) : lsb(wkPawns);
+
+      Square strongerKingSq = pos.king_square(strongerSide);
+      Square weakerKingSq = pos.king_square(weakerSide);
+      Square bishopSq = pos.piece_list(strongerSide, BISHOP)[0];
+
+      // Draw if weaker pawn is on rank 7, bishop can't attack the pawn, and
+      // weaker king can stop opposing opponent's king from penetrating.
+      if (   relative_rank(strongerSide, weakerPawnSq) == RANK_7
+          && opposite_colors(bishopSq, weakerPawnSq)
+          && square_distance(weakerPawnSq, weakerKingSq) <= square_distance(weakerPawnSq, strongerKingSq))
+          return SCALE_FACTOR_DRAW;
+  }
+
   return SCALE_FACTOR_NONE;
 }
 
@@ -897,14 +920,14 @@ ScaleFactor Endgame<KPKP>::operator()(const Position& pos) const {
   Square wksq = pos.king_square(strongerSide);
   Square bksq = pos.king_square(weakerSide);
   Square wpsq = pos.piece_list(strongerSide, PAWN)[0];
-  Color stm = pos.side_to_move();
+  Color us = pos.side_to_move();
 
   if (strongerSide == BLACK)
   {
       wksq = ~wksq;
       bksq = ~bksq;
       wpsq = ~wpsq;
-      stm  = ~stm;
+      us   = ~us;
   }
 
   if (file_of(wpsq) >= FILE_E)
@@ -922,5 +945,5 @@ ScaleFactor Endgame<KPKP>::operator()(const Position& pos) const {
 
   // Probe the KPK bitbase with the weakest side's pawn removed. If it's a draw,
   // it's probably at least a draw even with the pawn.
-  return Bitbases::probe_kpk(wksq, wpsq, bksq, stm) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW;
+  return Bitbases::probe_kpk(wksq, wpsq, bksq, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW;
 }
index 72601bb..5c8338c 100644 (file)
@@ -35,6 +35,20 @@ namespace {
     STOP
   };
 
+  // Our insertion sort, guaranteed to be stable, as is needed
+  void insertion_sort(MoveStack* begin, MoveStack* end)
+  {
+    MoveStack tmp, *p, *q;
+
+    for (p = begin + 1; p < end; ++p)
+    {
+        tmp = *p;
+        for (q = p; q != begin && *(q-1) < tmp; --q)
+            *q = *(q-1);
+        *q = tmp;
+    }
+  }
+
   // Unary predicate used by std::partition to split positive scores from remaining
   // ones so to sort separately the two sets, and with the second sort delayed.
   inline bool has_positive_score(const MoveStack& ms) { return ms.score > 0; }
@@ -230,14 +244,14 @@ void MovePicker::generate_next() {
       endQuiets = end = generate<QUIETS>(pos, moves);
       score<QUIETS>();
       end = std::partition(cur, end, has_positive_score);
-      sort<MoveStack>(cur, end);
+      insertion_sort(cur, end);
       return;
 
   case QUIETS_2_S1:
       cur = end;
       end = endQuiets;
       if (depth >= 3 * ONE_PLY)
-          sort<MoveStack>(cur, end);
+          insertion_sort(cur, end);
       return;
 
   case BAD_CAPTURES_S1:
index bb4a713..b8e89b6 100644 (file)
@@ -110,8 +110,7 @@ const string move_to_san(Position& pos, Move m) {
 
   assert(MoveList<LEGAL>(pos).contains(m));
 
-  Bitboard attackers;
-  bool ambiguousMove, ambiguousFile, ambiguousRank;
+  Bitboard others, b;
   string san;
   Color us = pos.side_to_move();
   Square from = from_sq(m);
@@ -127,31 +126,23 @@ const string move_to_san(Position& pos, Move m) {
       {
           san = PieceToChar[WHITE][pt]; // Upper case
 
-          // Disambiguation if we have more then one piece with destination 'to'
-          // note that for pawns is not needed because starting file is explicit.
-          ambiguousMove = ambiguousFile = ambiguousRank = false;
+          // Disambiguation if we have more then one piece of type 'pt' that can
+          // reach 'to' with a legal move.
+          others = b = (pos.attacks_from(pc, to) & pos.pieces(us, pt)) ^ from;
 
-          attackers = (pos.attacks_from(pc, to) & pos.pieces(us, pt)) ^ from;
-
-          while (attackers)
+          while (b)
           {
-              Square sq = pop_lsb(&attackers);
-
-              // If the move is illegal, the piece is not included in the sub-set
-              if (!pos.pl_move_is_legal(make_move(sq, to), pos.pinned_pieces()))
-                  continue;
-
-              ambiguousFile |= file_of(sq) == file_of(from);
-              ambiguousRank |= rank_of(sq) == rank_of(from);
-              ambiguousMove = true;
+              Move move = make_move(pop_lsb(&b), to);
+              if (!pos.pl_move_is_legal(move, pos.pinned_pieces()))
+                  others ^= from_sq(move);
           }
 
-          if (ambiguousMove)
+          if (others)
           {
-              if (!ambiguousFile)
+              if (!(others & file_bb(from)))
                   san += file_to_char(file_of(from));
 
-              else if (!ambiguousRank)
+              else if (!(others & rank_bb(from)))
                   san += rank_to_char(rank_of(from));
 
               else
index 310e46e..ad0a621 100644 (file)
@@ -802,7 +802,7 @@ void Position::do_move(Move m, StateInfo& newSt, const CheckInfo& ci, bool moveI
       // Update piece list, move the last piece at index[capsq] position and
       // shrink the list.
       //
-      // WARNING: This is a not revresible operation. When we will reinsert the
+      // WARNING: This is a not reversible operation. When we will reinsert the
       // captured piece in undo_move() we will put it at the end of the list and
       // not in its original place, it means index[] and pieceList[] are not
       // guaranteed to be invariant to a do_move() + undo_move() sequence.
index 5e61b9e..74dc9e2 100644 (file)
@@ -98,7 +98,7 @@ namespace {
   void id_loop(Position& pos);
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);
-  bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta);
+  bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta);
   bool allows(const Position& pos, Move first, Move second);
   bool refutes(const Position& pos, Move first, Move second);
   string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
@@ -354,7 +354,7 @@ namespace {
                 // we want to keep the same order for all the moves but the new
                 // PV that goes to the front. Note that in case of MultiPV search
                 // the already searched PV lines are preserved.
-                sort<RootMove>(RootMoves.begin() + PVIdx, RootMoves.end());
+                std::stable_sort(RootMoves.begin() + PVIdx, RootMoves.end());
 
                 // Write PV back to transposition table in case the relevant
                 // entries have been overwritten during the search.
@@ -399,7 +399,7 @@ namespace {
             }
 
             // Sort the PV lines searched so far and update the GUI
-            sort<RootMove>(RootMoves.begin(), RootMoves.begin() + PVIdx + 1);
+            std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1);
 
             if (PVIdx + 1 == PVSize || Time::now() - SearchTime > 3000)
                 sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl;
@@ -594,8 +594,8 @@ namespace {
     else if (tte)
     {
         // Never assume anything on values stored in TT
-        if (  (ss->staticEval = eval = tte->static_value()) == VALUE_NONE
-            ||(ss->evalMargin = tte->static_value_margin()) == VALUE_NONE)
+        if (  (ss->staticEval = eval = tte->eval_value()) == VALUE_NONE
+            ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
             eval = ss->staticEval = evaluate(pos, ss->evalMargin);
 
         // Can ttValue be used as a better position evaluation?
@@ -1025,7 +1025,7 @@ split_point_start: // At split points actual search starts from here
       // Step 19. Check for splitting the search
       if (   !SpNode
           &&  depth >= Threads.minimumSplitDepth
-          &&  Threads.slave_available(thisThread)
+          &&  Threads.available_slave(thisThread)
           &&  thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD)
       {
           assert(bestValue < beta);
@@ -1164,8 +1164,8 @@ split_point_start: // At split points actual search starts from here
         if (tte)
         {
             // Never assume anything on values stored in TT
-            if (  (ss->staticEval = bestValue = tte->static_value()) == VALUE_NONE
-                ||(ss->evalMargin = tte->static_value_margin()) == VALUE_NONE)
+            if (  (ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE
+                ||(ss->evalMargin = tte->eval_margin()) == VALUE_NONE)
                 ss->staticEval = bestValue = evaluate(pos, ss->evalMargin);
         }
         else
@@ -1335,7 +1335,7 @@ split_point_start: // At split points actual search starts from here
 
   // check_is_dangerous() tests if a checking move can be pruned in qsearch()
 
-  bool check_is_dangerous(Position& pos, Move move, Value futilityBase, Value beta)
+  bool check_is_dangerous(const Position& pos, Move move, Value futilityBase, Value beta)
   {
     Piece pc = pos.piece_moved(move);
     Square from = from_sq(move);
@@ -1672,9 +1672,9 @@ void Thread::idle_loop() {
 
           sp->mutex.lock();
 
-          assert(sp->slavesPositions[idx] == NULL);
+          assert(activePosition == NULL);
 
-          sp->slavesPositions[idx] = &pos;
+          activePosition = &pos;
 
           switch (sp->nodeType) {
           case Root:
@@ -1693,7 +1693,7 @@ void Thread::idle_loop() {
           assert(searching);
 
           searching = false;
-          sp->slavesPositions[idx] = NULL;
+          activePosition = NULL;
           sp->slavesMask &= ~(1ULL << idx);
           sp->nodes += pos.nodes_searched();
 
@@ -1742,7 +1742,7 @@ void check_time() {
       nodes = RootPos.nodes_searched();
 
       // Loop across all split points and sum accumulated SplitPoint nodes plus
-      // all the currently active slaves positions.
+      // all the currently active positions nodes.
       for (size_t i = 0; i < Threads.size(); i++)
           for (int j = 0; j < Threads[i]->splitPointsSize; j++)
           {
@@ -1754,8 +1754,9 @@ void check_time() {
               Bitboard sm = sp.slavesMask;
               while (sm)
               {
-                  Position* pos = sp.slavesPositions[pop_lsb(&sm)];
-                  nodes += pos ? pos->nodes_searched() : 0;
+                  Position* pos = Threads[pop_lsb(&sm)]->activePosition;
+                  if (pos)
+                      nodes += pos->nodes_searched();
               }
 
               sp.mutex.unlock();
index 600d7a7..4a66b11 100644 (file)
@@ -56,12 +56,11 @@ struct Stack {
 /// all non-pv moves.
 struct RootMove {
 
-  RootMove(){} // Needed by sort()
   RootMove(Move m) : score(-VALUE_INFINITE), prevScore(-VALUE_INFINITE) {
     pv.push_back(m); pv.push_back(MOVE_NONE);
   }
 
-  bool operator<(const RootMove& m) const { return score < m.score; }
+  bool operator<(const RootMove& m) const { return score > m.score; } // Ascending sort
   bool operator==(const Move& m) const { return pv[0] == m; }
 
   void extract_pv_from_tt(Position& pos);
index b04b8ad..a6886b1 100644 (file)
@@ -43,11 +43,12 @@ namespace { extern "C" {
 // Thread c'tor starts a newly-created thread of execution that will call
 // the the virtual function idle_loop(), going immediately to sleep.
 
-Thread::Thread() : splitPoints() {
+Thread::Thread() /* : splitPoints() */ { // Value-initialization bug in MSVC
 
   searching = exit = false;
   maxPly = splitPointsSize = 0;
   activeSplitPoint = NULL;
+  activePosition = NULL;
   idx = Threads.size();
 
   if (!thread_create(handle, start_routine, this))
@@ -229,13 +230,13 @@ void ThreadPool::read_uci_options() {
 // slave_available() tries to find an idle thread which is available as a slave
 // for the thread 'master'.
 
-bool ThreadPool::slave_available(Thread* master) const {
+Thread* ThreadPool::available_slave(Thread* master) const {
 
   for (const_iterator it = begin(); it != end(); ++it)
       if ((*it)->is_available_to(master))
-          return true;
+          return *it;
 
-  return false;
+  return NULL;
 }
 
 
@@ -288,20 +289,18 @@ void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bes
 
   splitPointsSize++;
   activeSplitPoint = &sp;
+  activePosition = NULL;
 
   size_t slavesCnt = 1; // This thread is always included
+  Thread* slave;
 
-  for (ThreadPool::iterator it = Threads.begin(); it != Threads.end() && !Fake; ++it)
+  while (    (slave = Threads.available_slave(this)) != NULL
+         && ++slavesCnt <= Threads.maxThreadsPerSplitPoint && !Fake)
   {
-      Thread* slave = *it;
-
-      if (slave->is_available_to(this) && ++slavesCnt <= Threads.maxThreadsPerSplitPoint)
-      {
-          sp.slavesMask |= 1ULL << slave->idx;
-          slave->activeSplitPoint = &sp;
-          slave->searching = true; // Slave leaves idle_loop()
-          slave->notify_one(); // Could be sleeping
-      }
+      sp.slavesMask |= 1ULL << slave->idx;
+      slave->activeSplitPoint = &sp;
+      slave->searching = true; // Slave leaves idle_loop()
+      slave->notify_one(); // Could be sleeping
   }
 
   sp.mutex.unlock();
@@ -318,6 +317,7 @@ void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bes
       // In helpful master concept a master can help only a sub-tree of its split
       // point, and because here is all finished is not possible master is booked.
       assert(!searching);
+      assert(!activePosition);
   }
 
   // We have returned from the idle loop, which means that all threads are
@@ -329,6 +329,7 @@ void Thread::split(Position& pos, Stack* ss, Value alpha, Value beta, Value* bes
   searching = true;
   splitPointsSize--;
   activeSplitPoint = sp.parentSplitPoint;
+  activePosition = &pos;
   pos.set_nodes_searched(pos.nodes_searched() + sp.nodes);
   *bestMove = sp.bestMove;
   *bestValue = sp.bestValue;
index b18170d..8115bc7 100644 (file)
@@ -75,7 +75,6 @@ struct SplitPoint {
 
   // Shared data
   Mutex mutex;
-  Position* slavesPositions[MAX_THREADS];
   volatile uint64_t slavesMask;
   volatile int64_t nodes;
   volatile Value alpha;
@@ -110,6 +109,7 @@ struct Thread {
   Material::Table materialTable;
   Endgames endgames;
   Pawns::Table pawnsTable;
+  Position* activePosition;
   size_t idx;
   int maxPly;
   Mutex mutex;
@@ -149,7 +149,7 @@ struct ThreadPool : public std::vector<Thread*> {
 
   MainThread* main_thread() { return static_cast<MainThread*>((*this)[0]); }
   void read_uci_options();
-  bool slave_available(Thread* master) const;
+  Thread* available_slave(Thread* master) const;
   void wait_for_think_finished();
   void start_thinking(const Position&, const Search::LimitsType&,
                       const std::vector<Move>&, Search::StateStackPtr&);
index 9dbfcb5..f4e5535 100644 (file)
 
 TranspositionTable TT; // Our global transposition table
 
-TranspositionTable::TranspositionTable() {
-
-  size = generation = 0;
-  entries = NULL;
-}
-
-TranspositionTable::~TranspositionTable() {
-
-  delete [] entries;
-}
-
 
 /// TranspositionTable::set_size() sets the size of the transposition table,
-/// measured in megabytes. Transposition table consists of a power of 2 number of
-/// TTCluster and each cluster consists of ClusterSize number of TTEntries. Each
-/// non-empty entry contains information of exactly one position.
+/// measured in megabytes. Transposition table consists of a power of 2 number
+/// of clusters and each cluster consists of ClusterSize number of TTEntry.
 
 void TranspositionTable::set_size(size_t mbSize) {
 
-  size_t newSize = 1ULL << msb((mbSize << 20) / sizeof(TTCluster));
+  assert(msb((mbSize << 20) / sizeof(TTEntry)) < 32);
 
-  if (newSize == size)
+  uint32_t size = ClusterSize << msb((mbSize << 20) / sizeof(TTEntry[ClusterSize]));
+
+  if (hashMask == size - ClusterSize)
       return;
 
-  size = newSize;
-  delete [] entries;
-  entries = new (std::nothrow) TTCluster[size];
+  hashMask = size - ClusterSize;
+  delete [] table;
+  table = new (std::nothrow) TTEntry[size];
 
-  if (!entries)
+  if (!table)
   {
       std::cerr << "Failed to allocate " << mbSize
                 << "MB for transposition table." << std::endl;
@@ -70,7 +60,7 @@ void TranspositionTable::set_size(size_t mbSize) {
 
 void TranspositionTable::clear() {
 
-  memset(entries, 0, size * sizeof(TTCluster));
+  memset(table, 0, (hashMask + ClusterSize) * sizeof(TTEntry));
 }
 
 
@@ -82,23 +72,23 @@ void TranspositionTable::clear() {
 /// more valuable than a TTEntry t2 if t1 is from the current search and t2 is from
 /// a previous search, or if the depth of t1 is bigger than the depth of t2.
 
-void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m, Value statV, Value kingD) {
+void TranspositionTable::store(const Key key, Value v, Bound t, Depth d, Move m, Value statV, Value kingD) {
 
   int c1, c2, c3;
   TTEntry *tte, *replace;
-  uint32_t posKey32 = posKey >> 32; // Use the high 32 bits as key inside the cluster
+  uint32_t key32 = key >> 32; // Use the high 32 bits as key inside the cluster
 
-  tte = replace = first_entry(posKey);
+  tte = replace = first_entry(key);
 
-  for (int i = 0; i < ClusterSize; i++, tte++)
+  for (unsigned i = 0; i < ClusterSize; i++, tte++)
   {
-      if (!tte->key() || tte->key() == posKey32) // Empty or overwrite old
+      if (!tte->key() || tte->key() == key32) // Empty or overwrite old
       {
           // Preserve any existing ttMove
           if (m == MOVE_NONE)
               m = tte->move();
 
-          tte->save(posKey32, v, t, d, m, generation, statV, kingD);
+          tte->save(key32, v, t, d, m, generation, statV, kingD);
           return;
       }
 
@@ -110,7 +100,7 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move
       if (c1 + c2 + c3 > 0)
           replace = tte;
   }
-  replace->save(posKey32, v, t, d, m, generation, statV, kingD);
+  replace->save(key32, v, t, d, m, generation, statV, kingD);
 }
 
 
@@ -118,24 +108,14 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move
 /// transposition table. Returns a pointer to the TTEntry or NULL if
 /// position is not found.
 
-TTEntry* TranspositionTable::probe(const Key posKey) const {
+TTEntry* TranspositionTable::probe(const Key key) const {
 
-  uint32_t posKey32 = posKey >> 32;
-  TTEntry* tte = first_entry(posKey);
+  TTEntry* tte = first_entry(key);
+  uint32_t key32 = key >> 32;
 
-  for (int i = 0; i < ClusterSize; i++, tte++)
-      if (tte->key() == posKey32)
+  for (unsigned i = 0; i < ClusterSize; i++, tte++)
+      if (tte->key() == key32)
           return tte;
 
   return NULL;
 }
-
-
-/// TranspositionTable::new_search() is called at the beginning of every new
-/// search. It increments the "generation" variable, which is used to
-/// distinguish transposition table entries from previous searches from
-/// entries from the current search.
-
-void TranspositionTable::new_search() {
-  generation++;
-}
index f3b0f2a..2db19c8 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -44,7 +44,7 @@
 class TTEntry {
 
 public:
-  void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value statV, Value statM) {
+  void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value ev, Value em) {
 
     key32        = (uint32_t)k;
     move16       = (uint16_t)m;
@@ -52,63 +52,52 @@ public:
     generation8  = (uint8_t)g;
     value16      = (int16_t)v;
     depth16      = (int16_t)d;
-    staticValue  = (int16_t)statV;
-    staticMargin = (int16_t)statM;
+    evalValue    = (int16_t)ev;
+    evalMargin   = (int16_t)em;
   }
   void set_generation(int g) { generation8 = (uint8_t)g; }
 
-  uint32_t key() const              { return key32; }
-  Depth depth() const               { return (Depth)depth16; }
-  Move move() const                 { return (Move)move16; }
-  Value value() const               { return (Value)value16; }
-  Bound type() const                { return (Bound)bound; }
-  int generation() const            { return (int)generation8; }
-  Value static_value() const        { return (Value)staticValue; }
-  Value static_value_margin() const { return (Value)staticMargin; }
+  uint32_t key() const      { return key32; }
+  Depth depth() const       { return (Depth)depth16; }
+  Move move() const         { return (Move)move16; }
+  Value value() const       { return (Value)value16; }
+  Bound type() const        { return (Bound)bound; }
+  int generation() const    { return (int)generation8; }
+  Value eval_value() const  { return (Value)evalValue; }
+  Value eval_margin() const { return (Value)evalMargin; }
 
 private:
   uint32_t key32;
   uint16_t move16;
   uint8_t bound, generation8;
-  int16_t value16, depth16, staticValue, staticMargin;
+  int16_t value16, depth16, evalValue, evalMargin;
 };
 
 
-/// This is the number of TTEntry slots for each cluster
-const int ClusterSize = 4;
-
-
-/// TTCluster consists of ClusterSize number of TTEntries. Size of TTCluster
-/// must not be bigger than a cache line size. In case it is less, it should
-/// be padded to guarantee always aligned accesses.
-
-struct TTCluster {
-  TTEntry data[ClusterSize];
-};
-
-
-/// The transposition table class. This is basically just a huge array containing
-/// TTCluster objects, and a few methods for writing and reading entries.
+/// A TranspositionTable consists of a power of 2 number of clusters and each
+/// cluster consists of ClusterSize number of TTEntry. Each non-empty entry
+/// contains information of exactly one position. Size of a cluster shall not be
+/// bigger than a cache line size. In case it is less, it should be padded to
+/// guarantee always aligned accesses.
 
 class TranspositionTable {
 
-  TranspositionTable(const TranspositionTable&);
-  TranspositionTable& operator=(const TranspositionTable&);
+  static const unsigned ClusterSize = 4; // A cluster is 64 Bytes
 
 public:
-  TranspositionTable();
- ~TranspositionTable();
+ ~TranspositionTable() { delete [] table; }
+  void new_search() { generation++; }
+
+  TTEntry* probe(const Key key) const;
+  TTEntry* first_entry(const Key key) const;
+  void refresh(const TTEntry* tte) const;
   void set_size(size_t mbSize);
   void clear();
-  void store(const Key posKey, Value v, Bound type, Depth d, Move m, Value statV, Value kingD);
-  TTEntry* probe(const Key posKey) const;
-  void new_search();
-  TTEntry* first_entry(const Key posKey) const;
-  void refresh(const TTEntry* tte) const;
+  void store(const Key key, Value v, Bound type, Depth d, Move m, Value statV, Value kingD);
 
 private:
-  size_t size;
-  TTCluster* entries;
+  uint32_t hashMask;
+  TTEntry* table;
   uint8_t generation; // Size must be not bigger then TTEntry::generation8
 };
 
@@ -119,9 +108,9 @@ extern TranspositionTable TT;
 /// a cluster given a position. The lowest order bits of the key are used to
 /// get the index of the cluster.
 
-inline TTEntry* TranspositionTable::first_entry(const Key posKey) const {
+inline TTEntry* TranspositionTable::first_entry(const Key key) const {
 
-  return entries[((uint32_t)posKey) & (size - 1)].data;
+  return table + ((uint32_t)key & hashMask);
 }
 
 
index b7bcb4e..aa1f34f 100644 (file)
@@ -489,21 +489,4 @@ inline const std::string square_to_string(Square s) {
   return ch;
 }
 
-/// Our insertion sort implementation, works with pointers and iterators and is
-/// guaranteed to be stable, as is needed.
-template<typename T, typename K>
-void sort(K begin, K end)
-{
-  T tmp;
-  K p, q;
-
-  for (p = begin + 1; p < end; p++)
-  {
-      tmp = *p;
-      for (q = p; q != begin && *(q-1) < tmp; --q)
-          *q = *(q-1);
-      *q = tmp;
-  }
-}
-
 #endif // !defined(TYPES_H_INCLUDED)
index 5721e93..10519bb 100644 (file)
@@ -44,7 +44,7 @@ namespace {
 
   void set_option(istringstream& up);
   void set_position(Position& pos, istringstream& up);
-  void go(Position& pos, istringstream& up);
+  void go(const Position& pos, istringstream& up);
 }
 
 
@@ -182,7 +182,7 @@ namespace {
   // the thinking time and other parameters from the input string, and starts
   // the search.
 
-  void go(Position& pos, istringstream& is) {
+  void go(const Position& pos, istringstream& is) {
 
     Search::LimitsType limits;
     vector<Move> searchMoves;