summaryrefslogtreecommitdiff
path: root/ai_mm.cpp
blob: eb49f4ab568a8b2bc33c5b23ffc476b8565ef155 (plain)
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
92
93
94
95
96
97
98
99
100
101
102
103
#include <climits>
#include <cassert>
#include "ai_mm.h"


static const int mm_depth = 4;


// Positive scores for white
static int evaluate(const Board &bd, int win) {
	const int large = 10000;

	int score = -large;  // to counteract the +=large for KING
	score += 8;  // to counteract the imbalance in white/black stones

	for (int i = 0; i < N * N; i++) {
		switch (bd.cells[i]) {
			case EMPTY: break;
			case WHITE: score += 1; break;
			case KING: score += large; break;
			case BLACK: score -= 1; break;
		}
	}

	if (win == 1) score += large;

	return score;
}

static int minimaxBlack(const Board &bd, int depth, int alpha, int beta, int win);

static int minimaxWhite(const Board &bd, int depth, int alpha, int beta, int win) {
	if (depth == 0 || win != 0) {
		return evaluate(bd, win);
	}

	int bestValue = INT_MIN;

	bd.forEachMove(1, [&bd, depth, &alpha, &beta, &bestValue](Move mv) {
		Board bd2 = bd;
		int win = bd2.applyCW(mv);
		int value = minimaxBlack(bd2, depth - 1, alpha, beta, win);
		// cerr << string(6 - 2 * depth, ' ') << "mmW: " << mv << ": " << value << endl;
		bestValue = max(bestValue, value);
		alpha = max(alpha, bestValue);
		if (beta <= alpha) return true;
		return false;
	});

	return bestValue;
}

static int minimaxBlack(const Board &bd, int depth, int alpha, int beta, int win) {
	if (depth == 0 || win != 0) {
		return evaluate(bd, win);
	}

	int bestValue = INT_MAX;

	bd.forEachMove(-1, [&bd, depth, &alpha, &beta, &bestValue](Move mv) {
		Board bd2 = bd;
		int win = bd2.applyCW(mv);
		int value = minimaxWhite(bd2, depth - 1, alpha, beta, win);
		// cerr << string(6 - 2 * depth, ' ') << "mmB: " << mv << ": " << value << endl;
		bestValue = min(bestValue, value);
		beta = min(beta, bestValue);
		if (beta <= alpha) return true;
		return false;
	});

	return bestValue;
}

static int minimaxGeneric(const Board &bd, int depth, int alpha, int beta, int win, int player) {
	if (player == 1) return minimaxWhite(bd, depth, alpha, beta, win);
	else return minimaxBlack(bd, depth, alpha, beta, win);
}

Move AI::MM::findMove(const Board &bd, int player) {
	Move bestMove(-1, -1);
	int bestScore = INT_MIN;
	// 'bestScore', and 'score' below, have positive values good for 'player'.

	// cerr << "MM::findMove(player=" << player << "):" << endl;
	cerr << '[';

	bd.forEachMove(player, [&bd, player, &bestScore, &bestMove](Move mv) {
		Board bd2 = bd;
		int win = bd2.applyCW(mv);
		int score = player * minimaxGeneric(bd2, mm_depth, INT_MIN, INT_MAX, win, -player);
		// cerr << "fM: " << mv << ": " << score << endl;
		cerr << score << ',';
		if (score > bestScore) {
			bestScore = score;
			bestMove = mv;
		}
		return false;
	});

	cerr << ']' << endl;

	return bestMove;
}