1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <array>
#include <memory>
#include "minimax.h"
using namespace std;
#define LARGE MINIMAX_LARGE
static int win_score[4] = {
[WIN_NONE] = 0,
[WIN_P0] = 1,
[WIN_P1] = -1,
[WIN_DRAW] = -1,
};
struct TransItem {
Board B = Board::empty();
int score = 0;
};
static unique_ptr<array<TransItem, 10000019>> transTable =
make_unique<decltype(transTable)::element_type>();
static void transTableStore(uint64_t index, const Board &B, int score) {
TransItem &entry = (*transTable)[index];
// if (entry.B.isEmpty() || B.numFilled() < entry.B.numFilled()) {
entry.B = B;
entry.score = score;
// }
}
static uint64_t transHits = 0, transTotal = 0;
static uint64_t transHitDepthSum = 0;
template <int player>
int minimax(const Board &B, int alpha, int beta, int depth) {
uint64_t transIndex = B.hash() % transTable->size();
transTotal++;
if (!B.isEmpty() && (*transTable)[transIndex].B == B) {
transHits++;
transHitDepthSum += depth;
return (*transTable)[transIndex].score;
}
win_t win = B.checkWin();
if (win != WIN_NONE) {
transTableStore(transIndex, B, win_score[win]);
return win_score[win];
}
if (depth == 0) return win_score[WIN_NONE];
if (depth >= 42) {
printf("depth=%d alpha=%d beta=%d transHitrate=%lf (avg depth %lf)\n",
depth, alpha, beta,
(double)transHits / transTotal, (double)transHitDepthSum / transTotal);
}
int best = player == 0 ? -LARGE : LARGE;
// Returns true if iteration should be stopped
auto tryMove = [&](int i) {
if (B.stkFull(i)) return false;
Board C(B);
C.drop(i, player);
int sc = minimax<1 - player>(C, alpha, beta, depth - 1);
if constexpr (player == 0) {
best = max(sc, best);
alpha = max(best, alpha);
} else {
best = min(sc, best);
beta = min(best, beta);
}
return beta <= alpha;
};
for (int i = 0; i < 16; i++) {
if (tryMove(i)) break;
}
transTableStore(transIndex, B, best);
return best;
}
template int minimax<0>(const Board &B, int alpha, int beta, int depth);
template int minimax<1>(const Board &B, int alpha, int beta, int depth);
|
