Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 99 | pmbaty | 1 | /* |
| 2 | Texel - A UCI chess engine. |
||
| 3 | Copyright (C) 2012-2014 Peter Österlund, peterosterlund2@gmail.com |
||
| 4 | |||
| 5 | This program is free software: you can redistribute it and/or modify |
||
| 6 | it under the terms of the GNU General Public License as published by |
||
| 7 | the Free Software Foundation, either version 3 of the License, or |
||
| 8 | (at your option) any later version. |
||
| 9 | |||
| 10 | This program is distributed in the hope that it will be useful, |
||
| 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
| 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
| 13 | GNU General Public License for more details. |
||
| 14 | |||
| 15 | You should have received a copy of the GNU General Public License |
||
| 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
||
| 17 | */ |
||
| 18 | |||
| 19 | /* |
||
| 20 | * transpositionTable.cpp |
||
| 21 | * |
||
| 22 | * Created on: Feb 25, 2012 |
||
| 23 | * Author: petero |
||
| 24 | */ |
||
| 25 | |||
| 26 | #include "transpositionTable.hpp" |
||
| 27 | #include "position.hpp" |
||
| 28 | #include "moveGen.hpp" |
||
| 29 | #include "textio.hpp" |
||
| 30 | |||
| 31 | #include <iostream> |
||
| 32 | #include <iomanip> |
||
| 33 | |||
| 34 | using namespace std; |
||
| 35 | |||
| 36 | |||
| 37 | void |
||
| 38 | TranspositionTable::reSize(int log2Size) { |
||
| 39 | const size_t numEntries = ((size_t)1) << log2Size; |
||
| 40 | table.resize(numEntries); |
||
| 41 | generation = 0; |
||
| 42 | } |
||
| 43 | |||
| 44 | void |
||
| 45 | TranspositionTable::insert(U64 key, const Move& sm, int type, int ply, int depth, int evalScore) { |
||
| 46 | if (depth < 0) depth = 0; |
||
| 47 | size_t idx0 = getIndex(key); |
||
| 48 | U64 key2 = getStoredKey(key); |
||
| 49 | TTEntry ent0, ent1; |
||
| 50 | ent0.load(table[idx0]); |
||
| 51 | size_t idx = idx0; |
||
| 52 | TTEntry* ent = &ent0; |
||
| 53 | if (ent0.getKey() != key2) { |
||
| 54 | size_t idx1 = idx0 ^ 1; |
||
| 55 | ent1.load(table[idx1]); |
||
| 56 | idx = idx1; |
||
| 57 | ent = &ent1; |
||
| 58 | if (ent1.getKey() != key2) |
||
| 59 | if (ent1.betterThan(ent0, generation)) { |
||
| 60 | idx = idx0; |
||
| 61 | ent = &ent0; |
||
| 62 | } |
||
| 63 | } |
||
| 64 | bool doStore = true; |
||
| 65 | if ((ent->getKey() == key2) && (ent->getDepth() > depth) && (ent->getType() == type)) { |
||
| 66 | if (type == TType::T_EXACT) |
||
| 67 | doStore = false; |
||
| 68 | else if ((type == TType::T_GE) && (sm.score() <= ent->getScore(ply))) |
||
| 69 | doStore = false; |
||
| 70 | else if ((type == TType::T_LE) && (sm.score() >= ent->getScore(ply))) |
||
| 71 | doStore = false; |
||
| 72 | } |
||
| 73 | if (doStore) { |
||
| 74 | if ((ent->getKey() != key2) || (sm.from() != sm.to())) |
||
| 75 | ent->setMove(sm); |
||
| 76 | ent->setKey(key2); |
||
| 77 | ent->setScore(sm.score(), ply); |
||
| 78 | ent->setDepth(depth); |
||
| 79 | ent->setGeneration((S8)generation); |
||
| 80 | ent->setType(type); |
||
| 81 | ent->setEvalScore(evalScore); |
||
| 82 | ent->store(table[idx]); |
||
| 83 | } |
||
| 84 | } |
||
| 85 | |||
| 86 | void |
||
| 87 | TranspositionTable::extractPVMoves(const Position& rootPos, const Move& mFirst, std::vector<Move>& pv) { |
||
| 88 | Position pos(rootPos); |
||
| 89 | Move m(mFirst); |
||
| 90 | UndoInfo ui; |
||
| 91 | std::vector<U64> hashHistory; |
||
| 92 | while (true) { |
||
| 93 | pv.push_back(m); |
||
| 94 | pos.makeMove(m, ui); |
||
| 95 | if (contains(hashHistory, pos.zobristHash())) |
||
| 96 | break; |
||
| 97 | hashHistory.push_back(pos.zobristHash()); |
||
| 98 | TTEntry ent; |
||
| 99 | ent.clear(); |
||
| 100 | probe(pos.historyHash(), ent); |
||
| 101 | if (ent.getType() == TType::T_EMPTY) |
||
| 102 | break; |
||
| 103 | ent.getMove(m); |
||
| 104 | MoveList moves; |
||
| 105 | MoveGen::pseudoLegalMoves(pos, moves); |
||
| 106 | MoveGen::removeIllegal(pos, moves); |
||
| 107 | bool contains = false; |
||
| 108 | for (int mi = 0; mi < moves.size; mi++) |
||
| 109 | if (moves[mi].equals(m)) { |
||
| 110 | contains = true; |
||
| 111 | break; |
||
| 112 | } |
||
| 113 | if (!contains) |
||
| 114 | break; |
||
| 115 | } |
||
| 116 | } |
||
| 117 | |||
| 118 | /** Extract the PV starting from posIn, using hash entries, both exact scores and bounds. */ |
||
| 119 | std::string |
||
| 120 | TranspositionTable::extractPV(const Position& posIn) { |
||
| 121 | std::string ret; |
||
| 122 | Position pos(posIn); |
||
| 123 | bool first = true; |
||
| 124 | TTEntry ent; |
||
| 125 | ent.clear(); |
||
| 126 | probe(pos.historyHash(), ent); |
||
| 127 | UndoInfo ui; |
||
| 128 | std::vector<U64> hashHistory; |
||
| 129 | bool repetition = false; |
||
| 130 | while (ent.getType() != TType::T_EMPTY) { |
||
| 131 | Move m; |
||
| 132 | ent.getMove(m); |
||
| 133 | MoveList moves; |
||
| 134 | MoveGen::pseudoLegalMoves(pos, moves); |
||
| 135 | MoveGen::removeIllegal(pos, moves); |
||
| 136 | bool valid = false; |
||
| 137 | for (int mi = 0; mi < moves.size; mi++) |
||
| 138 | if (moves[mi].equals(m)) { |
||
| 139 | valid = true; |
||
| 140 | break; |
||
| 141 | } |
||
| 142 | if (!valid) |
||
| 143 | break; |
||
| 144 | if (repetition) |
||
| 145 | break; |
||
| 146 | if (!first) |
||
| 147 | ret += ' '; |
||
| 148 | if (ent.getType() == TType::T_LE) |
||
| 149 | ret += '<'; |
||
| 150 | else if (ent.getType() == TType::T_GE) |
||
| 151 | ret += '>'; |
||
| 152 | std::string moveStr = TextIO::moveToString(pos, m, false); |
||
| 153 | ret += moveStr; |
||
| 154 | pos.makeMove(m, ui); |
||
| 155 | if (contains(hashHistory, pos.zobristHash())) |
||
| 156 | repetition = true; |
||
| 157 | hashHistory.push_back(pos.zobristHash()); |
||
| 158 | probe(pos.historyHash(), ent); |
||
| 159 | first = false; |
||
| 160 | } |
||
| 161 | return ret; |
||
| 162 | } |
||
| 163 | |||
| 164 | void |
||
| 165 | TranspositionTable::printStats() const { |
||
| 166 | int unused = 0; |
||
| 167 | int thisGen = 0; |
||
| 168 | std::vector<int> depHist; |
||
| 169 | const int maxDepth = 20*8; |
||
| 170 | depHist.resize(maxDepth); |
||
| 171 | for (size_t i = 0; i < table.size(); i++) { |
||
| 172 | TTEntry ent; |
||
| 173 | ent.load(table[i]); |
||
| 174 | if (ent.getType() == TType::T_EMPTY) { |
||
| 175 | unused++; |
||
| 176 | } else { |
||
| 177 | if (ent.getGeneration() == generation) |
||
| 178 | thisGen++; |
||
| 179 | if (ent.getDepth() < maxDepth) |
||
| 180 | depHist[ent.getDepth()]++; |
||
| 181 | } |
||
| 182 | } |
||
| 183 | double w = 100.0 / table.size(); |
||
| 184 | std::stringstream ss; |
||
| 185 | ss.precision(2); |
||
| 186 | ss << std::fixed << "hstat: size:" << table.size() |
||
| 187 | << " unused:" << unused << " (" << (unused*w) << "%)" |
||
| 188 | << " thisGen:" << thisGen << " (" << (thisGen*w) << "%)" << std::endl; |
||
| 189 | cout << ss.str(); |
||
| 190 | for (int i = 0; i < maxDepth; i++) { |
||
| 191 | int c = depHist[i]; |
||
| 192 | if (c > 0) { |
||
| 193 | std::stringstream ss; |
||
| 194 | ss.precision(2); |
||
| 195 | ss << std::setw(4) << i |
||
| 196 | << ' ' << std::setw(8) << c |
||
| 197 | << " " << std::setw(6) << std::fixed << (c*w); |
||
| 198 | std::cout << "hstat:" << ss.str() << std::endl; |
||
| 199 | } |
||
| 200 | } |
||
| 201 | } |