-
Notifications
You must be signed in to change notification settings - Fork 27
/
ai.py
201 lines (166 loc) · 6.92 KB
/
ai.py
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
import board, pieces, numpy
class Heuristics:
# The tables denote the points scored for the position of the chess pieces on the board.
PAWN_TABLE = numpy.array([
[ 0, 0, 0, 0, 0, 0, 0, 0],
[ 5, 10, 10,-20,-20, 10, 10, 5],
[ 5, -5,-10, 0, 0,-10, -5, 5],
[ 0, 0, 0, 20, 20, 0, 0, 0],
[ 5, 5, 10, 25, 25, 10, 5, 5],
[10, 10, 20, 30, 30, 20, 10, 10],
[50, 50, 50, 50, 50, 50, 50, 50],
[ 0, 0, 0, 0, 0, 0, 0, 0]
])
KNIGHT_TABLE = numpy.array([
[-50, -40, -30, -30, -30, -30, -40, -50],
[-40, -20, 0, 5, 5, 0, -20, -40],
[-30, 5, 10, 15, 15, 10, 5, -30],
[-30, 0, 15, 20, 20, 15, 0, -30],
[-30, 5, 15, 20, 20, 15, 0, -30],
[-30, 0, 10, 15, 15, 10, 0, -30],
[-40, -20, 0, 0, 0, 0, -20, -40],
[-50, -40, -30, -30, -30, -30, -40, -50]
])
BISHOP_TABLE = numpy.array([
[-20, -10, -10, -10, -10, -10, -10, -20],
[-10, 5, 0, 0, 0, 0, 5, -10],
[-10, 10, 10, 10, 10, 10, 10, -10],
[-10, 0, 10, 10, 10, 10, 0, -10],
[-10, 5, 5, 10, 10, 5, 5, -10],
[-10, 0, 5, 10, 10, 5, 0, -10],
[-10, 0, 0, 0, 0, 0, 0, -10],
[-20, -10, -10, -10, -10, -10, -10, -20]
])
ROOK_TABLE = numpy.array([
[ 0, 0, 0, 5, 5, 0, 0, 0],
[-5, 0, 0, 0, 0, 0, 0, -5],
[-5, 0, 0, 0, 0, 0, 0, -5],
[-5, 0, 0, 0, 0, 0, 0, -5],
[-5, 0, 0, 0, 0, 0, 0, -5],
[-5, 0, 0, 0, 0, 0, 0, -5],
[ 5, 10, 10, 10, 10, 10, 10, 5],
[ 0, 0, 0, 0, 0, 0, 0, 0]
])
QUEEN_TABLE = numpy.array([
[-20, -10, -10, -5, -5, -10, -10, -20],
[-10, 0, 5, 0, 0, 0, 0, -10],
[-10, 5, 5, 5, 5, 5, 0, -10],
[ 0, 0, 5, 5, 5, 5, 0, -5],
[ -5, 0, 5, 5, 5, 5, 0, -5],
[-10, 0, 5, 5, 5, 5, 0, -10],
[-10, 0, 0, 0, 0, 0, 0, -10],
[-20, -10, -10, -5, -5, -10, -10, -20]
])
@staticmethod
def evaluate(board):
material = Heuristics.get_material_score(board)
pawns = Heuristics.get_piece_position_score(board, pieces.Pawn.PIECE_TYPE, Heuristics.PAWN_TABLE)
knights = Heuristics.get_piece_position_score(board, pieces.Knight.PIECE_TYPE, Heuristics.KNIGHT_TABLE)
bishops = Heuristics.get_piece_position_score(board, pieces.Bishop.PIECE_TYPE, Heuristics.BISHOP_TABLE)
rooks = Heuristics.get_piece_position_score(board, pieces.Rook.PIECE_TYPE, Heuristics.ROOK_TABLE)
queens = Heuristics.get_piece_position_score(board, pieces.Queen.PIECE_TYPE, Heuristics.QUEEN_TABLE)
return material + pawns + knights + bishops + rooks + queens
# Returns the score for the position of the given type of piece.
# A piece type can for example be: pieces.Pawn.PIECE_TYPE.
# The table is the 2d numpy array used for the scoring. Example: Heuristics.PAWN_TABLE
@staticmethod
def get_piece_position_score(board, piece_type, table):
white = 0
black = 0
for x in range(8):
for y in range(8):
piece = board.chesspieces[x][y]
if (piece != 0):
if (piece.piece_type == piece_type):
if (piece.color == pieces.Piece.WHITE):
white += table[x][y]
else:
black += table[7 - x][y]
return white - black
@staticmethod
def get_material_score(board):
white = 0
black = 0
for x in range(8):
for y in range(8):
piece = board.chesspieces[x][y]
if (piece != 0):
if (piece.color == pieces.Piece.WHITE):
white += piece.value
else:
black += piece.value
return white - black
class AI:
INFINITE = 10000000
@staticmethod
def get_ai_move(chessboard, invalid_moves):
best_move = 0
best_score = AI.INFINITE
for move in chessboard.get_possible_moves(pieces.Piece.BLACK):
if (AI.is_invalid_move(move, invalid_moves)):
continue
copy = board.Board.clone(chessboard)
copy.perform_move(move)
score = AI.alphabeta(copy, 2, -AI.INFINITE, AI.INFINITE, True)
if (score < best_score):
best_score = score
best_move = move
# Checkmate.
if (best_move == 0):
return 0
copy = board.Board.clone(chessboard)
copy.perform_move(best_move)
if (copy.is_check(pieces.Piece.BLACK)):
invalid_moves.append(best_move)
return AI.get_ai_move(chessboard, invalid_moves)
return best_move
@staticmethod
def is_invalid_move(move, invalid_moves):
for invalid_move in invalid_moves:
if (invalid_move.equals(move)):
return True
return False
@staticmethod
def minimax(board, depth, maximizing):
if (depth == 0):
return Heuristics.evaluate(board)
if (maximizing):
best_score = -AI.INFINITE
for move in board.get_possible_moves(pieces.Piece.WHITE):
copy = board.Board.clone(board)
copy.perform_move(move)
score = AI.minimax(copy, depth-1, False)
best_score = max(best_score, score)
return best_score
else:
best_score = AI.INFINITE
for move in board.get_possible_moves(pieces.Piece.BLACK):
copy = board.Board.clone(board)
copy.perform_move(move)
score = AI.minimax(copy, depth-1, True)
best_score = min(best_score, score)
return best_score
@staticmethod
def alphabeta(chessboard, depth, a, b, maximizing):
if (depth == 0):
return Heuristics.evaluate(chessboard)
if (maximizing):
best_score = -AI.INFINITE
for move in chessboard.get_possible_moves(pieces.Piece.WHITE):
copy = board.Board.clone(chessboard)
copy.perform_move(move)
best_score = max(best_score, AI.alphabeta(copy, depth-1, a, b, False))
a = max(a, best_score)
if (b <= a):
break
return best_score
else:
best_score = AI.INFINITE
for move in chessboard.get_possible_moves(pieces.Piece.BLACK):
copy = board.Board.clone(chessboard)
copy.perform_move(move)
best_score = min(best_score, AI.alphabeta(copy, depth-1, a, b, True))
b = min(b, best_score)
if (b <= a):
break
return best_score