DeepestBlue/AI.java at master · TrainerRed151/DeepestBlue · 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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
//Brian Pomerantz

import java.util.*;

public class AI {
	private boolean side;
	private int depth;

	public AI(boolean si, int dep) {
		side = si;
		depth = dep;
	}

	//Calculates the best move using a MinMax algorithm with ALphaBeta Pruning
	//Input: ArrayList of legal moves
	//Output: The particular legal move which maximizes (or minimizes) the engine's score
	public String move(Board bd) {
		ArrayList<String> moves = bd.legalMoves(side);

		//Stalemate
		if (moves.size() == 0) {
			return '\u00AB' + "-" + '\u00AB';
		}

		byte alpha = Byte.MIN_VALUE, beta = Byte.MAX_VALUE;

		byte best = -1, val, bestVal;
		if (side) {bestVal = Byte.MIN_VALUE;}
		else {bestVal = Byte.MAX_VALUE;}

		for (byte i = 0; i < moves.size(); i++) {
			Board nBD = new Board(bd.getBoard());
			val = alphabeta(nBD.move(moves.get(i), side), depth, alpha, beta, !side);
			//System.out.println(moves.get(i) + ": " + val);

			if (side && val > bestVal) {
				bestVal = val;
				best = i;
				alpha = (byte) Math.max(alpha, val);
			}

			if (!side && val < bestVal) {
				bestVal = val;
				best = i;
				beta = (byte) Math.min(beta, val);
			}

			if (beta <= alpha) {
    			break;
    		}
		}

		//Resign if opponent has forced mate within depth
		//Alternatively, the engine could chose a random move
		if (best == -1) {
			if (side){return "0-1";}
			else{return "1-0";}
		}

		return moves.get(best);
	}

	//Old MinMax function.  Superseded by AlphaBeta function
//	private byte minmax(Board bd, int dep, boolean maxPlayer) {
//		byte bestValue, val;
//
//		if (dep == 0) {
//        	return bd.score();
//		}
//
//    	if (maxPlayer) {
//    		bestValue = Byte.MIN_VALUE;
//
//    		for (String s : bd.legalMoves(maxPlayer)) {
//    			Board nBD = new Board(bd.getBoard());
//    			val = minmax(nBD.move(s, maxPlayer), dep - 1, false);
//    			bestValue = (byte) Math.max(bestValue, val);
//    		}
//
//			return bestValue;
//		}
//
//    	else {
//			bestValue = Byte.MAX_VALUE;
//
//			for (String s : bd.legalMoves(!maxPlayer)) {
//				Board nBD = new Board(bd.getBoard());
//				val = minmax(nBD.move(s, maxPlayer), dep - 1, true);
//    			bestValue = (byte) Math.min(bestValue, val);
//    		}
//
//			return bestValue;
//		}
//	}

	//AlphaBeta function
	//Recursively determines best possible move assuming perfect play within given depth
	//Discontinues branch of search tree if necessarily worse than previously calculated branch
	//More efficient than MinMax
	private byte alphabeta(Board bd, int dep, byte alpha, byte beta, boolean maxPlayer) {
		if (dep == 0) {
        	return bd.score();
		}

    	if (maxPlayer) {
    		ArrayList<String> list = bd.legalMoves(true);

    		//Checkmate
    		if (bd.checkmate(false)) {
    			return Byte.MIN_VALUE;
    		}

    		//Stalemate
    		if (list.size() == 0) {
    			return 0;
    		}

    		for (String s : list) {
    			Board nBD = new Board(bd.getBoard());
    			alpha = (byte) Math.max(alpha, alphabeta(nBD.move(s, true), dep-1, alpha, beta, false));

    			if (beta <= alpha) {
    				break;
    			}
    		}

			return alpha;
		}

    	else {
    		ArrayList<String> list = bd.legalMoves(false);

    		//Checkmate
    		if (bd.checkmate(true)) {
    			return Byte.MAX_VALUE;
    		}

    		//Stalemate
    		if (list.size() == 0) {
    			return 0;
    		}

			for (String s : list) {
				Board nBD = new Board(bd.getBoard());
    			beta = (byte) Math.min(beta, alphabeta(nBD.move(s, false), dep-1, alpha, beta, true));

    			if (beta <= alpha) {
    				break;
    			}
    		}

			return beta;
		}
	}
}