diff options
author | Tom Smeding <tom.smeding@gmail.com> | 2018-07-02 00:07:13 +0200 |
---|---|---|
committer | Tom Smeding <tom.smeding@gmail.com> | 2018-07-02 00:07:13 +0200 |
commit | 4a2389a8a97874393d48237ac638bdb51ebbe768 (patch) | |
tree | 03ddb8a3c3b15eb176b4ab1717c53fabfa7e00a7 /ai_mc.cpp | |
parent | e45da4cdddcaa6465243f4f2c77f4b1e3bcfb306 (diff) |
Add monte carlo player
Diffstat (limited to 'ai_mc.cpp')
-rw-r--r-- | ai_mc.cpp | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/ai_mc.cpp b/ai_mc.cpp new file mode 100644 index 0000000..7fbb9e0 --- /dev/null +++ b/ai_mc.cpp @@ -0,0 +1,82 @@ +#include <climits> +#include "ai_mc.h" + + +static const int mc_ngames = 500; + + +static int playout(Board &bd, int player) { + Move poss[N * N * N]; + + while (true) { + int nposs = 0; + int winidx = -1; + bd.forEachMove(player, [&bd, &poss, &nposs, &winidx, player](Move mv) { + Board bd2 = bd; + int win = bd2.applyCW(mv); + if (win * player >= 0) { + poss[nposs++] = mv; + if (win != 0) { + winidx = nposs - 1; + return true; + } + } + return false; + }); + + if (nposs == 0) return -player; + + int index = winidx == -1 ? rand() % nposs : winidx; + + int win = bd.applyCW(poss[index]); + if (win != 0) return win; + + player = -player; + } +} + +Move AI::MC::findMove(const Board &bd, int player) { + // 'maxscore' and 'score' below have high values for 'player'. + int maxscore = INT_MIN; + Move maxmove = Move(-1, -1); + + cerr << '['; + + bd.forEachMove(player, [&bd, &maxscore, &maxmove, player](Move mv) { + int score = 0; + + Board bd2 = bd; + int win = bd2.applyCW(mv); + if (win == player) { + maxscore = INT_MAX; + maxmove = mv; + cerr << "Found winning move!"; + return true; + } else if (win == -player) { + return false; + } + + for (int i = 0; i < mc_ngames; i++) { + Board bd3 = bd; + bd3.apply(mv); + score += playout(bd3, -player); + } + + score *= player; // fix sign + + cerr << score << ','; + + if (score > maxscore) { + maxscore = score; + maxmove = mv; + } + + return false; + }); + + cerr << ']' << endl; + + cerr << "Chose move with score " << maxscore << endl; + + return maxmove; +} |