Connect4/Solver.cpp at main · tonyyu2170/Connect4 · GitHub

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
#include "Solver.h"

Solver::Solver() : TT(8388593) {
    nodeCount = 0;
    TT.reset();
}

int Solver::negamax(Board &board, int alpha, int beta) {
    nodeCount++;

    if (board.isDraw())
        return 0;

    for (int c = 0; c < 7; ++c) {
        if (board.canMove(c) && board.isWinningMove(c)) {
            return (43 - board.getNumMoves()) / 2;
        }
    }

    int bestScore = (41 - board.getNumMoves()) / 2;

    if (int val = TT.get(board.key())) {
        bestScore = val - 19;
    }

    if (beta > bestScore) {
        beta = bestScore;
        if (alpha >= beta){
            return beta;
        }
    }

    static const int order[7] = {3, 4, 2, 5, 1, 0, 6};

    for (int i = 0; i < 7; ++i) {
        int col = order[i];
        if (!board.canMove(col)) continue;

        uint64_t savedCurrent = board.getCurrent();
        uint64_t savedMask = board.getMask();
        int savedNumMoves = board.getNumMoves();

        board.play(col);
        int score = -negamax(board, -beta, -alpha);
        board.setState(savedCurrent, savedMask, savedNumMoves);

        if (score >= beta) {
            return score;
        }
        if (score > alpha) {
            alpha = score;
        }
    }

    TT.put(board.key(), alpha + 19);
    return alpha;
}

int Solver::solve(Board &board) {
    int minScore = -((41 - board.getNumMoves())/2);
    int maxScore = ((41 - board.getNumMoves())/2);

    int guess = 0;

    while (minScore < maxScore) {
        int mid = minScore + (maxScore - minScore) / 2;

        if (mid <= 0 && minScore/2 < mid) {
            mid = minScore/2;
        } else if (mid >= 0 && maxScore/2 > mid) {
            mid = maxScore/2;
        }

        int r = negamax(board, mid, mid+1);

        if (r <= mid) {
            maxScore = r;
        } else {
            minScore = r;
        }
    }

    return minScore;
}

unsigned long long Solver::getNodeCount() {
    return nodeCount;
}