File indexing completed on 2024-11-24 03:43:17
0001 /******************************************************************* 0002 * 0003 * Copyright 2009 Pelladi Gabor <pelladigabor@gmail.com> 0004 * 0005 * Bovo is free software; you can redistribute it and/or modify 0006 * it under the terms of the GNU General Public License as published by 0007 * the Free Software Foundation; either version 2, or (at your option) 0008 * any later version. 0009 * 0010 * Bovo is distributed in the hope that it will be useful, 0011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0013 * GNU General Public License for more details. 0014 * 0015 * You should have received a copy of the GNU General Public License 0016 * along with Bovo; see the file COPYING. If not, write to 0017 * the Free Software Foundation, 51 Franklin Street, Fifth Floor, 0018 * Boston, MA 02110-1301, USA. 0019 * 0020 ********************************************************************/ 0021 0022 #include "ai_impl.h" 0023 #include "node.h" 0024 0025 #include <cassert> 0026 #include <cstdio> 0027 #include <cstdlib> 0028 #include <ctime> 0029 #include <memory.h> 0030 0031 #include <QRandomGenerator> 0032 0033 // hash table 0034 static NodeHashData hashData[nodeHashSize]; 0035 0036 const int hashMaxDepth = 8; 0037 const int hashMinRemainingDepth = 2; 0038 0039 AiImpl::AiImpl() 0040 : table_size_x(20) 0041 , table_size_y(20) 0042 , start_depth(6) 0043 , max_depth(6) 0044 , depth_increment(2) 0045 , force_thinking(false) 0046 , heur_seed(normal_heur_seed) 0047 , print_info(true) 0048 , max_branch(100) 0049 , timeOver(nullptr) 0050 , rememberedStanding(table_size_x, table_size_y) 0051 { 0052 memset(hashData, 0, sizeof(hashData)); 0053 } 0054 0055 AiImpl::~AiImpl() = default; 0056 0057 void AiImpl::newGame() 0058 { 0059 Standing::initRefresh(); 0060 previousStandings.clear(); 0061 rememberedStanding = Standing(table_size_x, table_size_y); 0062 } 0063 0064 void AiImpl::step(pos_T x, pos_T y) 0065 { 0066 previousStandings.push_back(rememberedStanding); 0067 rememberedStanding.step(x, y); 0068 if (print_info) { 0069 printf("hval = %d\n", rememberedStanding.hval); 0070 fflush(stdout); 0071 } 0072 } 0073 0074 void AiImpl::stepServer(pos_T x, pos_T y) 0075 { 0076 rememberedStanding.step_server(x, y); 0077 } 0078 0079 void AiImpl::undo() 0080 { 0081 assert(!previousStandings.empty()); 0082 rememberedStanding = previousStandings.back(); 0083 previousStandings.pop_back(); 0084 } 0085 0086 Field AiImpl::think() 0087 { 0088 rememberedStanding.heur_seed = heur_seed; 0089 0090 // opening book 0091 Field f = openingBook(); 0092 if (f.x < table_size_x && f.y < table_size_y && !rememberedStanding.table[f.x][f.y]) { 0093 return f; 0094 } 0095 // global best step 0096 pos_T bestX = max_table_size, bestY = max_table_size; 0097 0098 // alpha-beta pruning 0099 Node *act; 0100 Node *root; 0101 hash_T currentHash; 0102 NodeHashData currentHashData; 0103 0104 // step suggestion in the current depth limit 0105 pos_T suggestedX = max_table_size, suggestedY = max_table_size; 0106 // heuristic value of the search tree root 0107 heur_T rootValue = 0.0; 0108 0109 // do a very fast initial search 0110 depth_limit = 1; 0111 do { 0112 if (print_info) 0113 printf(" depth limit: %2d", depth_limit); 0114 0115 act = root = new Node(new Standing(rememberedStanding), this); 0116 0117 // this prevents the AI from thinking if there is only one good move 0118 if (!force_thinking && root->steps.size() == 1) { 0119 suggestedX = root->steps.front()->lastx; 0120 suggestedY = root->steps.front()->lasty; 0121 rootValue = 0; 0122 act = nullptr; 0123 } 0124 0125 while (act && (timeOver == nullptr || !timeOver->isTimeOver())) { 0126 // if this is a parent whose child has just been evaluated 0127 if (act->child) { 0128 if (act->signum > 0) { 0129 // MAX 0130 if (act->alpha < act->child->beta) { 0131 act->alpha = act->child->beta; 0132 act->is_exact = true; 0133 if (!act->parent) { 0134 suggestedX = act->child->standing->lastx; 0135 suggestedY = act->child->standing->lasty; 0136 rootValue = act->alpha; 0137 } 0138 if (act->alpha >= act->beta || act->alpha >= WinTreshold) { 0139 act->evaluated = true; 0140 currentHashData.entry_type = lower_bound; 0141 currentHashData.value = act->alpha; 0142 } 0143 } 0144 } else { 0145 // MIN 0146 if (act->beta > act->child->alpha) { 0147 act->beta = act->child->alpha; 0148 act->is_exact = true; 0149 if (!act->parent) { 0150 suggestedX = act->child->standing->lastx; 0151 suggestedY = act->child->standing->lasty; 0152 rootValue = act->beta; 0153 } 0154 if (act->alpha >= act->beta || act->beta <= -WinTreshold) { 0155 act->evaluated = true; 0156 currentHashData.entry_type = upper_bound; 0157 currentHashData.value = act->beta; 0158 } 0159 } 0160 } 0161 0162 delete act->child; 0163 act->child = nullptr; 0164 } 0165 0166 // if this parent has no more children to process 0167 if (act->steps.empty()) { 0168 act->evaluated = true; 0169 if (act->signum > 0) { 0170 // MAX 0171 currentHashData.entry_type = act->is_exact ? exact : upper_bound; 0172 currentHashData.value = act->alpha; 0173 } else { 0174 // MIN 0175 currentHashData.entry_type = act->is_exact ? exact : lower_bound; 0176 currentHashData.value = act->beta; 0177 } 0178 } 0179 0180 if (act->evaluated) { 0181 // store the current standing in the hash table 0182 if (act->depth <= hashMaxDepth && depth_limit - act->depth >= hashMinRemainingDepth && heur_seed <= normal_heur_seed) { 0183 act->calcHash(¤tHash, ¤tHashData); 0184 hashData[currentHash] = currentHashData; 0185 } 0186 0187 act = act->parent; 0188 } else { 0189 act->child = new Node(act->steps.front(), act); 0190 act->steps.pop_front(); 0191 act = act->child; 0192 0193 // if this is a leaf 0194 if (act->evaluated) { 0195 act = act->parent; 0196 continue; 0197 } 0198 0199 // check whether we have already evaluated the standing elsewhere 0200 if (act->depth <= hashMaxDepth && depth_limit - act->depth >= hashMinRemainingDepth && heur_seed <= normal_heur_seed) { 0201 act->calcHash(¤tHash, ¤tHashData); 0202 NodeHashData *storedHashData = &hashData[currentHash]; 0203 if (storedHashData->remaining_depth >= depth_limit - act->depth && currentHashData.checksum == storedHashData->checksum) { 0204 if (act->signum > 0) { 0205 // MAX 0206 if (storedHashData->entry_type == exact) 0207 act->alpha = act->beta = storedHashData->value; 0208 if (storedHashData->entry_type == lower_bound && act->alpha < storedHashData->value) 0209 act->alpha = storedHashData->value; 0210 if (storedHashData->entry_type == upper_bound && act->beta > storedHashData->value) 0211 act->beta = storedHashData->value; 0212 } else { 0213 // MIN 0214 if (storedHashData->entry_type == exact) 0215 act->alpha = act->beta = storedHashData->value; 0216 if (storedHashData->entry_type == upper_bound && act->beta > storedHashData->value) 0217 act->beta = storedHashData->value; 0218 if (storedHashData->entry_type == lower_bound && act->alpha < storedHashData->value) 0219 act->alpha = storedHashData->value; 0220 } 0221 if (act->alpha >= act->beta) { 0222 act->evaluated = true; 0223 act = act->parent; 0224 continue; 0225 } 0226 } 0227 } 0228 } 0229 } 0230 0231 // check why we have left the while loop 0232 if (!act) { 0233 bestX = suggestedX; 0234 bestY = suggestedY; 0235 if (print_info) { 0236 printf(" suggestion: (%2d, %2d) score: %6d\n", suggestedX, suggestedY, rootValue); 0237 fflush(stdout); 0238 } 0239 } else { 0240 if (print_info) { 0241 printf(" time is over\n"); 0242 fflush(stdout); 0243 } 0244 } 0245 delete root; 0246 0247 if (depth_limit < start_depth) { 0248 depth_limit = start_depth; 0249 } else { 0250 depth_limit += depth_increment; 0251 } 0252 } while (depth_limit <= max_depth && (timeOver == nullptr || !timeOver->isTimeOver())); 0253 0254 assert((timeOver == nullptr || !timeOver->isTimeOver()) || !rememberedStanding.table[bestX][bestY]); 0255 return {bestX, bestY}; 0256 } 0257 0258 Field AiImpl::openingBook() 0259 { 0260 if (rememberedStanding.stepCount == 0) { 0261 pos_T x, y; 0262 x = table_size_x / 2; 0263 y = table_size_y / 2; 0264 x += QRandomGenerator::global()->bounded(5) - 2; 0265 y += QRandomGenerator::global()->bounded(5) - 2; 0266 while (rememberedStanding.table[x][y]) 0267 x++; 0268 return {x, y}; 0269 } else if (rememberedStanding.stepCount == 1) { 0270 pos_T x, y; 0271 x = rememberedStanding.lastx; 0272 y = rememberedStanding.lasty; 0273 int r = QRandomGenerator::global()->bounded(100); 0274 if (r >= 20) { 0275 if (x < table_size_x / 2) { 0276 x++; 0277 } else { 0278 x--; 0279 } 0280 } 0281 if (r < 80) { 0282 if (y < table_size_y / 2) { 0283 y++; 0284 } else { 0285 y--; 0286 } 0287 } 0288 return {x, y}; 0289 } else if (rememberedStanding.stepCount == 2) { 0290 pos_T x1, y1, x2, y2; 0291 int dx, dy; 0292 x1 = previousStandings.back().lastx; 0293 y1 = previousStandings.back().lasty; 0294 if (!(1 <= x1 && x1 < table_size_x - 1 && 1 <= y1 && y1 < table_size_y - 1)) { 0295 return {max_table_size, max_table_size}; 0296 } 0297 x2 = rememberedStanding.lastx; 0298 y2 = rememberedStanding.lasty; 0299 dx = (int)x1 - (int)x2; 0300 dy = (int)y1 - (int)y2; 0301 if (-1 <= dx && dx <= 1 && -1 <= dy && dy <= 1) { 0302 if (dx == 0) { 0303 return {static_cast<pos_T>((int)x1 + (QRandomGenerator::global()->bounded(2)) * 2 - 1), 0304 static_cast<pos_T>((int)y1 + QRandomGenerator::global()->bounded(3) - 1)}; 0305 } 0306 if (dy == 0) { 0307 return {static_cast<pos_T>((int)x1 + QRandomGenerator::global()->bounded(3) - 1), 0308 static_cast<pos_T>((int)y1 + (QRandomGenerator::global()->bounded(2)) * 2 - 1)}; 0309 } 0310 if (QRandomGenerator::global()->bounded(2)) { 0311 if (QRandomGenerator::global()->bounded(2)) { 0312 return {static_cast<pos_T>((int)x1 + dx), y1}; 0313 } else { 0314 return {x1, static_cast<pos_T>((int)y1 + dy)}; 0315 } 0316 } else { 0317 if (QRandomGenerator::global()->bounded(2)) { 0318 return {static_cast<pos_T>((int)x1 - dx), static_cast<pos_T>((int)y1 + dy)}; 0319 } else { 0320 return {static_cast<pos_T>((int)x1 + dx), static_cast<pos_T>((int)y1 - dy)}; 0321 } 0322 } 0323 } 0324 } 0325 return {max_table_size, max_table_size}; 0326 }