00001
00002
00003 #include "osl/apply_move/applyMove.h"
00004 #include "osl/category/bigramPosition.h"
00005 #include "osl/container/moveLogProbVector.h"
00006 #include "osl/effect_util/neighboring8Direct.h"
00007 #include "osl/oslConfig.h"
00008 #include <iostream>
00009
00010 namespace osl
00011 {
00012 namespace category
00013 {
00014 KingNeighborBigramTable BigramAttack::probTable(OslConfig::home_c_str(), "attack");
00015 KingNeighborBigramTable BigramDefense::probTable(OslConfig::home_c_str(), "defense");
00016 static BigramHelper bigramHelper = BigramHelper();
00017 #ifdef MORE_BIGRAM
00018 BigramTable BigramPosition::probTable(OslConfig::home_c_str(), "prev");
00019 BigramTable SamePlayerBigramPosition::probTable(OslConfig::home_c_str(), "prev-prev");
00020 BigramHistoryTable BigramHistory::probTable(1);
00021 #endif
00022 }
00023 }
00024
00025 osl::category::BigramHelper::
00026 BigramHelper()
00027 {
00028 for (size_t i = 0; i < osl::PieceStand::order.size(); i++)
00029 {
00030 pieceMap[osl::PieceStand::order[i]] = i;
00031 }
00032 }
00033
00034 int osl::category::BigramHelper::
00035 moveToIndex(osl::Move move, bool from) const
00036 {
00037 osl::Position p = from ? move.from() : move.to();
00038
00039 if (p.isPieceStand())
00040 return 100 + pieceMap[osl::unpromote(move.ptype())];
00041 else
00042 return (p.x() * 10) + p.y();
00043 }
00044
00045
00046 int osl::category::BigramHelper::
00047 moveToIndex(osl::Move move, osl::Player player) const
00048 {
00049 assert(move.isNormal());
00050 int value = (moveToIndex(move, true) << 8
00051 | (moveToIndex(move, false)));
00052 if (player == osl::BLACK)
00053 value |= 1 << 31;
00054
00055 return value;
00056 }
00057
00058 int osl::category::BigramHelper::
00059 moveToValue(osl::Move move) const
00060 {
00061 assert(move.isNormal());
00062 int value = (moveToIndex(move, true) << 8
00063 | (moveToIndex(move, false)));
00064 return value;
00065 }
00066
00067 int osl::category::BigramHelper::
00068 toIndex(osl::Position pos, osl::Move move, osl::Player player) const
00069 {
00070 assert(move.isNormal());
00071 int value = ((pos.x() * 10 + pos.y()) << 16
00072 | moveToIndex(move, true) << 8
00073 | (moveToIndex(move, false)));
00074 if (player == osl::BLACK)
00075 value |= 1 << 31;
00076
00077 return value;
00078 }
00079
00080 osl::Move osl::category::BigramHelper::
00081 indexToMove(int value, const CategoryEnv::effect_state_t& state) const
00082 {
00083 int from, to, mask;
00084 mask = (1 << 8) - 1;
00085 from = (value >> 8) & mask;
00086 to = value & mask;
00087 Position toP(to / 10, to % 10);
00088 if (from >= 100)
00089 {
00090 if (!state.getPieceAt(toP).isEmpty())
00091 return Move::INVALID();
00092 Ptype type = PieceStand::order[from - 100];
00093 Move move(toP, type, state.getTurn());
00094 if (! Ptype_Table.canDropTo(state.getTurn(), type, toP))
00095 return Move::INVALID();
00096 if (state.isAlmostValidMove<false>(move))
00097 return move;
00098 else
00099 return Move::INVALID();
00100 }
00101 else
00102 {
00103 Position fromP(from / 10, from % 10);
00104 Piece p = state.getPieceAt(fromP);
00105 Piece toPiece = state.getPieceAt(toP);
00106
00107 if (p.isEmpty() || p.owner() != state.getTurn()
00108 || (!toPiece.isEmpty() && toPiece.owner() == state.getTurn()))
00109 return Move::INVALID();
00110
00111 if (! state.hasEffectByPiece(p, toP))
00112 return Move::INVALID();
00113
00114 Move move = Move(fromP, toP, p.ptype(),
00115 toPiece.ptype(), false, state.getTurn());
00116 if (!isPromoted(p.ptype())
00117 && ! Ptype_Table.canDropTo(state.getTurn(), p.ptype(), toP))
00118 {
00119 move = Move(fromP, toP, promote(p.ptype()),
00120 toPiece.ptype(), true, state.getTurn());
00121 }
00122
00123 if (state.isAlmostValidMove<false>(move))
00124 return move;
00125 else
00126 return Move::INVALID();
00127 }
00128 }
00129
00130 #ifdef MORE_BIGRAM
00131 osl::category::BigramTable::
00132 BigramTable() : table(new map_t)
00133 {
00134 }
00135
00136 osl::category::BigramTable::
00137 BigramTable(const char *oslHome, const char *name) : table(new map_t)
00138 {
00139 std::string path(oslHome);
00140
00141 path += "/data/bigram/";
00142 path += name;
00143 path += ".txt";
00144 init(path.c_str());
00145 }
00146
00147 void osl::category::BigramTable::
00148 init(const char *filename)
00149 {
00150 min = osl::category::CategoryTraits::maxProb();
00151 FILE *fp = fopen(filename, "r");
00152 if (!fp)
00153 {
00154 std::cerr << "Failed to open bigram table " << filename << std::endl;
00155 return;
00156 }
00157
00158 while (true)
00159 {
00160 CArray<char,2> turn;
00161 int from1, to1, from2, to2, value;
00162 int ret;
00163 ret = fscanf(fp, "%1s %d %d %d %d %d\n", &turn[0],
00164 &from1, &to1, &from2, &to2, &value);
00165 if (ret == EOF)
00166 break;
00167 else if (ret < 6)
00168 {
00169 std::cerr << "Unknown Entry " << from1 << " " << to1 << std::endl;
00170 }
00171 min = std::min(min, value);
00172
00173 int key = (from1 << 8) | to1;
00174 int pos = (from2 << 8) | to2;
00175 if (turn[0] == '+')
00176 {
00177 key |= 1 << 31;
00178 }
00179
00180 (*table)[key].push_back(std::make_pair(pos, value));
00181 }
00182 if (fp)
00183 fclose(fp);
00184 }
00185
00186 void osl::category::BigramTable::
00187 generate(const CategoryEnv& env, MoveLogProbVector& out, int back) const
00188 {
00189 assert(back == 1 || back == 2);
00190 const osl::Move key_move = env.history->lastMove(back);
00191 if (!key_move.isNormal())
00192 return;
00193 int index = bigramHelper.moveToIndex(key_move, env.state->getTurn());
00194 if (table->find(index) != table->end())
00195 {
00196 typedef osl::stl::vector<std::pair<int, int> > vector_t;
00197 const vector_t& moves = table->find(index)->second;
00198 for (size_t i = 0; i < moves.size(); i++)
00199 {
00200 if (moves[i].second > env.limit)
00201 break;
00202
00203 const Move move = bigramHelper.indexToMove(moves[i].first, *env.state);
00204 if (move.isInvalid())
00205 continue;
00206 if (!move.from().isPieceStand()
00207 && move.ptype() != KING
00208 && move.ptype() != GOLD
00209 && !isPromoted(move.ptype())
00210 && (move.from().canPromote(move.player())
00211 || move.to().canPromote(move.player())))
00212 {
00213 const Move promoted_move(move.from(), move.to(),
00214 promote(move.ptype()),
00215 move.capturePtype(), true,
00216 move.player());
00217 assert(env.state->isAlmostValidMove(promoted_move));
00218 out.push_back(promoted_move,
00219 moves[i].second);
00220 }
00221 out.push_back(move, moves[i].second);
00222 }
00223 }
00224 }
00225
00226
00227 osl::category::BigramHistoryTable::BigramHistoryTable(int) : table(new map_t)
00228 {
00229 }
00230
00231 void osl::category::BigramHistoryTable::
00232 setupTable(const SimpleState& initialState,
00233 const CategoryEnv::effect_state_t& eState,
00234 const container::MoveStack& history)
00235 {
00236 table->clear();
00237
00238 CategoryEnv::effect_state_t state(initialState);
00239 container::MoveStack genHistory;
00240
00241 for (size_t i = 0; ; i++)
00242 {
00243 const int decay = DECAY_VALUE * (history.size() - i) / 2;
00244 if (eState.getTurn() == state.getTurn()
00245 && RETAIN_REALIZATION_PROBABILITY > decay)
00246 {
00247 CategoryEnv env(&state, 200, &genHistory);
00248 container::MoveLogProbVector moves;
00249 BigramPosition::generate(env, moves);
00250 SamePlayerBigramPosition::generate(env, moves);
00251
00252 for (size_t i = 0; i < moves.size(); i++)
00253 {
00254 assert(!moves[i].getMove().isInvalid());
00255 int index = bigramHelper.moveToIndex(moves[i].getMove(),
00256 eState.getTurn());
00257 if (moves[i].getLogProb() + decay < RETAIN_REALIZATION_PROBABILITY
00258 && (table->find(index) == table->end()
00259 || (*table)[index] > moves[i].getLogProb() + decay)
00260 && !bigramHelper.indexToMove(index, eState).isInvalid())
00261 {
00262 (*table)[index] = moves[i].getLogProb() + decay;
00263 }
00264 }
00265 }
00266
00267 if (i == history.size())
00268 break;
00269 const Move move = history.lastMove(history.size() - i);
00270 apply_move::ApplyMoveOfTurn::doMove(state, move);
00271 genHistory.push(move);
00272 }
00273 }
00274
00275 void osl::category::BigramHistoryTable::
00276 generate(const CategoryEnv& env, MoveLogProbVector& out) const
00277 {
00278 if (env.depth > 3 || env.depth == 0)
00279 return;
00280
00281 for (map_t::iterator it = table->begin();
00282 it != table->end();
00283 ++it)
00284 {
00285 const Move move = bigramHelper.indexToMove(it->first, *env.state);
00286 if (move.isInvalid())
00287 {
00288 continue;
00289 }
00290 if (it->second <= env.limit)
00291 {
00292 assert(env.state->isAlmostValidMove(move));
00293 out.push_back(move, it->second);
00294 if (!move.from().isPieceStand()
00295 && move.ptype() != KING
00296 && move.ptype() != GOLD
00297 && !isPromoted(move.ptype())
00298 && (move.from().canPromote(move.player())
00299 || move.to().canPromote(move.player())))
00300 {
00301 Move promoted_move(move.from(), move.to(), promote(move.ptype()),
00302 move.capturePtype(), true, move.player());
00303 assert(env.state->isAlmostValidMove(promoted_move));
00304 out.push_back(promoted_move, it->second);
00305 }
00306 }
00307 }
00308 }
00309 #endif
00310
00311 osl::category::KingNeighborBigramTable::
00312 KingNeighborBigramTable() : table(new map_t)
00313 {
00314 }
00315
00316 osl::category::KingNeighborBigramTable::
00317 KingNeighborBigramTable(const char *oslHome, const char *name) : table(new map_t)
00318 {
00319 std::string path(oslHome);
00320
00321 path += "/data/bigram/";
00322 path += name;
00323 path += ".txt";
00324 init(path.c_str());
00325 }
00326
00327 void osl::category::KingNeighborBigramTable::
00328 init(const char *filename)
00329 {
00330 min = osl::category::CategoryTraits::maxProb();
00331 FILE *fp = fopen(filename, "r");
00332 if (!fp)
00333 {
00334 std::cerr << "Failed to open bigram table " << filename << std::endl;
00335 return;
00336 }
00337
00338 while (true)
00339 {
00340 CArray<char,2> turn;
00341 int king, from1, to1, from2, to2, value;
00342 int ret;
00343 ret = fscanf(fp, "%1s %d %d %d %d %d %d\n", &turn[0],
00344 &king, &from1, &to1, &from2, &to2, &value);
00345 if (ret == EOF)
00346 break;
00347 else if (ret < 7)
00348 {
00349 std::cerr << "Unknown Entry " << from1 << " " << to1 << std::endl;
00350 }
00351 min = std::min(min, value);
00352
00353 int key = (king << 16) | (from1 << 8) | to1;
00354 int pos = (from2 << 8) | to2;
00355 if (turn[0] == '+')
00356 {
00357 key |= 1 << 31;
00358 }
00359
00360 (*table)[key].push_back(std::make_pair(pos, value));
00361 }
00362 if (fp)
00363 fclose(fp);
00364 }
00365
00366 bool osl::category::KingNeighborBigramTable::
00367 isIn5x5(const osl::Position kingPosition,
00368 const osl::Position targetPosition) const
00369 {
00370 int x = kingPosition.x();
00371 int y = kingPosition.y();
00372
00373
00374 if (x < 3)
00375 x = 3;
00376 if (x > 7)
00377 x = 7;
00378
00379 return ((x - 2 <= targetPosition.x() && targetPosition.x() <= x + 2)
00380 && (y - 2 <= targetPosition.y() && targetPosition.y() <= y + 2));
00381 }
00382
00383
00384 bool osl::category::KingNeighborBigramTable::
00385 isAttackByMajorPiece(const osl::category::CategoryEnv::effect_state_t& state,
00386 const osl::Position pos,
00387 const osl::Ptype ptype,
00388 const osl::Player turn) const
00389 {
00390 return ((unpromote(ptype) == osl::ROOK
00391 && pos.canPromote(alt(turn)))
00392 || (unpromote(ptype) == osl::BISHOP
00393 && osl::effect_util::Neighboring8Direct::hasEffect(state,
00394 osl::newPtypeO(state.getTurn(), ptype),
00395 pos, state.getKingPosition(turn))));
00396 }
00397
00398 void osl::category::KingNeighborBigramTable::
00399 generate(const CategoryEnv& env, MoveLogProbVector& out,
00400 int back) const
00401 {
00402 assert(back == 1 || back == 2);
00403 const osl::Move key_move = env.history->lastMove(back);
00404
00405 if (!key_move.isNormal())
00406 return;
00407 const osl::Player kingTurn = back == 2 ? alt(env.state->getTurn()) : env.state->getTurn();
00408 const osl::Position kingPosition = env.state->getKingPosition(kingTurn);
00409
00410 if (!isIn5x5(kingPosition, key_move.to())
00411 && !isAttackByMajorPiece(*env.state, key_move.to(), key_move.ptype(),
00412 kingTurn))
00413 return;
00414 int index = bigramHelper.toIndex(kingPosition, key_move, env.state->getTurn());
00415 if (table->find(index) != table->end())
00416 {
00417 typedef osl::stl::vector<std::pair<int, int> > vector_t;
00418 const vector_t& moves = table->find(index)->second;
00419 for (size_t i = 0; i < moves.size(); i++)
00420 {
00421 if (moves[i].second > env.limit)
00422 break;
00423
00424
00425 const Move move = bigramHelper.indexToMove(moves[i].first, *env.state);
00426 if (move.isInvalid())
00427 continue;
00428 out.push_back(move, moves[i].second);
00429 if (!move.from().isPieceStand()
00430 && move.ptype() != KING
00431 && move.ptype() != GOLD
00432 && !isPromoted(move.ptype())
00433 && (move.from().canPromote(move.player())
00434 || move.to().canPromote(move.player())))
00435 {
00436 const Move promoted_move(move.from(), move.to(),
00437 promote(move.ptype()),
00438 move.capturePtype(), true,
00439 move.player());
00440 assert(env.state->isAlmostValidMove(promoted_move));
00441 out.push_back(promoted_move,
00442 moves[i].second);
00443 }
00444 }
00445 }
00446 }
00447
00448 int osl::category::KingNeighborBigramTable::
00449 probability(const CategoryEnv& env, Move move, int back) const
00450 {
00451 assert(back == 1 || back == 2);
00452 const osl::Move key_move = env.history->lastMove(back);
00453
00454 if (!key_move.isNormal())
00455 return env.limit+1;
00456 const osl::Player kingTurn = back == 2 ? alt(env.state->getTurn()) : env.state->getTurn();
00457 const osl::Position kingPosition = env.state->getKingPosition(kingTurn);
00458
00459 if (!isIn5x5(kingPosition, key_move.to())
00460 && !isAttackByMajorPiece(*env.state, key_move.to(), key_move.ptype(),
00461 kingTurn))
00462 return env.limit+1;
00463 int index = bigramHelper.toIndex(kingPosition, key_move, env.state->getTurn());
00464 map_t::const_iterator p=table->find(index);
00465 if (p != table->end()) {
00466 typedef osl::stl::vector<std::pair<int, int> > vector_t;
00467 const vector_t& moves = p->second;
00468 const int value = bigramHelper.moveToValue(move);
00469 for (size_t i = 0; i < moves.size(); i++) {
00470 if (moves[i].first == value)
00471 return moves[i].second;
00472 if (moves[i].second > env.limit)
00473 break;
00474 }
00475 }
00476 return env.limit+1;
00477 }
00478
00479
00480
00481
00482
00483