/
ai2_negamax.cpp
83 lines (74 loc) · 2.02 KB
/
ai2_negamax.cpp
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
#include <iostream>
#include "board.hpp"
#include "cell_evaluation.hpp"
using namespace std;
#define inf 100000000 // 大きな値
// 初期化
inline void init() {
board_init();
evaluate_init();
}
// 標準入力からボードの状態を配列に受け取る
inline void input_board(int arr[]) {
char elem;
for (int i = 0; i < hw2; ++i) {
cin >> elem;
if (elem == '0')
arr[i] = black;
else if (elem == '1')
arr[i] = white;
else
arr[i] = vacant;
}
}
// negamax法
int nega_max(board b, int depth, bool passed) {
// 葉ノードでは評価関数を実行する
if (depth == 0)
return evaluate(b);
// 葉ノードでなければ子ノード全部に対して再帰する
int coord, max_score = -inf;
for (coord = 0; coord < hw2; ++coord) {
if (b.legal(coord))
max_score = max(max_score, -nega_max(b.move(coord), depth - 1, false));
}
// パスの処理 手番を交代して同じ深さで再帰する
if (max_score == -inf) {
// 2回連続パスなら評価関数を実行
if (passed)
return evaluate(b);
b.player = 1 - b.player;
return -nega_max(b, depth, true);
}
return max_score;
}
// depth手読みの探索
int search(board b, int depth) {
int coord, max_score = -inf, res = -1, score;
for (coord = 0; coord < hw2; ++coord) {
if (b.legal(coord)) {
score = -nega_max(b.move(coord), depth - 1, false);
if (max_score < score) {
max_score = score;
res = coord;
}
}
}
return res;
}
int main() {
init();
int arr[64];
board b;
int ai_player, policy;
cin >> ai_player;
while (true) {
input_board(arr);
b.translate_from_arr(arr, ai_player);
cerr << evaluate(b) << endl;
b.print();
policy = search(b, 4);
cout << policy / hw << " " << policy % hw << endl;
}
return 0;
}