-
Notifications
You must be signed in to change notification settings - Fork 0
/
negamaxab.py
133 lines (111 loc) · 6.2 KB
/
negamaxab.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
import chess
import chess.svg
import chess.polyglot
import chess.pgn
import chess.engine
import piece_tables
class NegamaxAbEngine:
def __init__(self, board, depth):
self.board = board
self.depth = depth
def evaluation(self):
"""
evaluate current position.
:return: node score.
"""
if self.board.is_checkmate():
if self.board.turn:
return -9999
else:
return 9999
if self.board.is_stalemate():
return 0
if self.board.is_insufficient_material():
return 0
# Quantity of remaining pieces:
wp = len(self.board.pieces(chess.PAWN, chess.WHITE))
bp = len(self.board.pieces(chess.PAWN, chess.BLACK))
wn = len(self.board.pieces(chess.KNIGHT, chess.WHITE))
bn = len(self.board.pieces(chess.KNIGHT, chess.BLACK))
wb = len(self.board.pieces(chess.BISHOP, chess.WHITE))
bb = len(self.board.pieces(chess.BISHOP, chess.BLACK))
wr = len(self.board.pieces(chess.ROOK, chess.WHITE))
br = len(self.board.pieces(chess.ROOK, chess.BLACK))
wq = len(self.board.pieces(chess.QUEEN, chess.WHITE))
bq = len(self.board.pieces(chess.QUEEN, chess.BLACK))
# Piece val was: 100, 320, 330, 500, 900
material = 100 * (wp - bp) + 300 * (wn - bn) + 330 * (wb - bb) + 550 * (wr - br) + 1000 * (wq - bq)
pawn_sq = sum([piece_tables.TABLE_PAWN_MAIN[i] for i in self.board.pieces(chess.PAWN, chess.WHITE)])
pawn_sq += sum([-piece_tables.TABLE_PAWN_MAIN[chess.square_mirror(i)]
for i in self.board.pieces(chess.PAWN, chess.BLACK)])
knight_sq = sum([piece_tables.TABLE_KNIGHT_MAIN[i] for i in self.board.pieces(chess.KNIGHT, chess.WHITE)])
knight_sq += sum([-piece_tables.TABLE_KNIGHT_MAIN[chess.square_mirror(i)]
for i in self.board.pieces(chess.KNIGHT, chess.BLACK)])
bishop_sq = sum([piece_tables.TABLE_BISHOP_MAIN[i] for i in self.board.pieces(chess.BISHOP, chess.WHITE)])
bishop_sq += sum([-piece_tables.TABLE_BISHOP_MAIN[chess.square_mirror(i)]
for i in self.board.pieces(chess.BISHOP, chess.BLACK)])
rook_sq = sum([piece_tables.TABLE_ROOK_MAIN[i] for i in self.board.pieces(chess.ROOK, chess.WHITE)])
rook_sq += sum([-piece_tables.TABLE_ROOK_MAIN[chess.square_mirror(i)]
for i in self.board.pieces(chess.ROOK, chess.BLACK)])
queen_sq = sum([piece_tables.TABLE_QUEEN_MAIN[i] for i in self.board.pieces(chess.QUEEN, chess.WHITE)])
queen_sq += sum([-piece_tables.TABLE_QUEEN_MAIN[chess.square_mirror(i)]
for i in self.board.pieces(chess.QUEEN, chess.BLACK)])
king_sq = sum([piece_tables.TABLE_KING_MAIN[i] for i in self.board.pieces(chess.KING, chess.WHITE)])
king_sq += sum([-piece_tables.TABLE_KING_MAIN[chess.square_mirror(i)]
for i in self.board.pieces(chess.KING, chess.BLACK)])
evaluation = material + pawn_sq + knight_sq + bishop_sq + rook_sq + queen_sq + king_sq
return evaluation if self.board.turn else -evaluation
def alpha_beta(self, alpha, beta, depth_left):
"""
Searches the best move using NegaMax and Alpha-Beta Pruning.
:param alpha: current Alpha score.
:param beta: current Beta score.
:param depth_left: search depth remaining.
:return: best score found.
"""
best_score = -9999
b = beta
if depth_left == 0: # If max-depth or terminal-node reached:
return self.evaluation() # Return current leaf eval.
for move in self.board.legal_moves: # Loop over all possible moves
self.board.push(move) # Get current move
score = -self.alpha_beta(-b, -alpha, depth_left - 1) # Negamax implementation of Minimax
self.board.pop() # Undo move
best_score = max(score, best_score) # Compare returned and existing values, storing highest
alpha = max(score, alpha) # Adjust search window
if alpha >= beta: # Alpha Beta Pruning condition
return alpha # Prune branch
b = alpha + 1
return best_score
def search_controller(self):
"""
Controls the NegaMax with Alpha-Beta Pruning search.
:return: best move found.
"""
best_move = chess.Move.null()
best_value = -99999 # Set as INF (essentially)
alpha = -100000 # Set as INF (essentially)
beta = 100000 # Set as INF (essentially)
for move in self.board.legal_moves:
self.board.push(move)
board_value = -self.alpha_beta(-beta, -alpha, self.depth - 1)
if board_value > best_value:
best_value = board_value
best_move = move
alpha = max(board_value, alpha)
self.board.pop()
return best_move
"""
Gaikwad, A. (2020). Let’s create a Chess AI. [ONLINE] Medium.
Available at: https://medium.com/dscvitpune/lets-create-a-chess-ai-8542a12afef. [Accessed 25 May. 2021].
This source provided the basis for the evaluation functions.
This was an area where only a basic evaluator was required that could function across multiple algorithms,
with this being an ideal example to use as a foundation.
Elnaggar, A., Aziem, M., Gadallah, M., and El-Deeb, H., (2014).
A Comparative Study of Game Tree Searching Methods.
International Journal of Advanced Computer Science and Applications, 5(5). [ONLINE]
Available at: https://www.researchgate.net/publication/262672371_A_Comparative_Study_of_Game_Tree_Searching_Methods.
[Accessed 21 Feb. 2021].
This research paper provided excellent resources for all the algorithms used in the software.
The pseudocode provided formed the basis of all four chess algorithms.
"""