· 5 years ago · Feb 03, 2020, 08:24 AM
1# 15-112: Principles of Programming and Computer Science
2# Project: Chess Program
3# Name : Muhammad Nahin Khan
4# AndrewID : mnk1
5# File Created: 07/11/2016
6# Modification History:
7# Start End
8# 07/11 12:52 07/11 13:20
9# 07/11 18:00 07/11 21:06
10# 09/11 03:13 09/11 05:49
11# 09/11 15:38 09/11 16:19
12# 10/11 15:51 10/11 16:31
13# 10/11 20:17 10/11 21:34
14# 11/11 23:50 12/11 05:19
15# 13/11 00:01 13/11 01:34
16# 15/11 16:19 15/11 17:00
17# 16/11 01:00 16/11 01:49
18# 16/11 12:50 16/11 13:31
19# 17/11 21:20 17/11 22:21
20# 18/11 00:15 18/11 01:15
21# 18/11 19:01 19/11 20:20
22# 21/11 00:56 21/11 02:01
23# 21/11 19:36 21/11 20:30
24# 22/11 18:10 22/11 20:02
25# 23/11 01:00 23/11 02:30
26# 23/11 18:05 23/11 20:03
27# 25/11 04:10 25/11 04:50
28# 25/11 13:00 25/11 14:35
29# 25/11 18:35 25/11 19:25
30# 26/11 08:04 26/11 08:31
31# 26/11 21:44 26/11 23:31
32# 27/11 02:24 27/11 03:08
33#
34
35#Ensure that Pygame is installed
36
37#GUI inspired by:
38#https://en.lichess.org/
39
40#Chess board image was taken from lichess website as well.
41#The images for the pieces came from:
42#https://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Chess_Pieces_Sprite.svg/2000px-Chess_Pieces_Sprite.svg.png
43
44#AI ideas from:
45#https://chessprogramming.wikispaces.com/
46
47# An online lecture that helped me understand alpha-beta pruning:
48# Winston, P. [MIT OpenCourseWare]. (2010) 6. Search: Games, Minimax,
49# and Alpha-Beta. [Video File]. Retrieved from https://www.youtube.com/watch?v=STjW3eH0Cik
50
51#Special thanks to professor Saquib for being so amazing.
52
53# This program is a chess game. The user may play against a friend or the
54# computer.
55#
56# The game state is mainly stored as a 2D list of strings, and most of the
57# processing is thus done on a list of strings.
58#
59# The GUI takes the current state and displays it on the screen. The GUI allows
60# drag and drop movement of pieces as well as click-click movement.
61#
62# The AI that plays against the human evaluates all possible moves made by either
63# player up to a certain level of depth. The AI evaluates each position by giving
64# it a score. The higher the value of the score, the more favourable a position
65# is for white and the lower the value of the score, the more favourable the
66# position is for black. Knowing that white will try to get the score to be higher
67# and black will try and get the score to be lower, the AI assumes best play from
68# either side as it traverses up the search tree and chooses the best move to be
69# played. A problem that may arise is the number of postions that need to be
70# evaulated. Even at 3 levels of depth, thousands of positions have to be
71# evaluatd.
72# Several methods are used in this program to reduce positions that are searched:
73# 1. Alpha-beta pruning: As a result of evaluating a position it can be found
74# that a portion of the search tree can be ignored as no further evaluations can
75# guarantee better results. This can happen because white and black area against
76# one another. White plays what is best for it and black plays what is best for it,
77# so it would make sense for white to ignore any portion of the tree where black
78# has a clear upperhand that it can choose to play.
79# 2. Transposition table: Often, two different pathways in a search tree can result
80# in the same board being evaluated. Instead of evaluating the same board several
81# times, the program stores a table of values in a dictionary where the keys are
82# the positions. This way, repeated positions can have their evaluations looked up
83# fairly quickly, as the board state is hashed.
84# 3. Opening Book - The opening book is again a dictionary that stores board
85# positions often seen in the beginning few moves in chess. Appropraite moves that
86# can be played at such positions is stored in the dictionary. A random move is
87# selected and played from the list of suggested moves wihtout searching if the AI
88# finds itself confronting a such a board postion. Note that this opening book was
89# recorded by myself and so it does not have many positions stored in it.
90#
91# In order to traverse the search tree as above, the AI needs to know how to evaluate the
92# board at any position to decide if white or black has the advantage. My evaluation
93# function currently looks at three main things when evaluating the board:
94# a) Material for white and black. Each piece has a value and the more pieces you have,
95# the better off your position is likely to be. For example, if white has an extra
96# queen, it has an advantage over black.
97# b) Piece-square table values - for each piece, there is a table that stores the best
98# squares that the particular piece should occupy. So if white has a knight at a
99# good square that controls the centre of the board, whereas black has a knight
100# at the corner of the board, the situation is evaluated as being more favourable
101# for white.
102# c) Reduction in points for doubled pawns, isolated pawns, and blocked pawns. If any
103# side has a set of pawns with the above features their points are slightly lower
104# to indicate a slight disadvantage in such a position.
105# d) A checkmate: a position where this has occured gets a very high point, so that the
106# AI moves towards this if it can. (or avoids it).
107#
108# There are also several ways in which this program may be improved:
109# 1. Move ordering: Given a certain position and the AI needs to search a few layers
110# deep from it, somehow pre-sorting each move by ranking them in their likelihood of
111# being good moves allows for earlier cut-offs to be made by alpha-beta pruning.
112# 2. Iterative Deepening: Instead of going directly to a given depth when searching,
113# the A.I. may evaluate the best move at depth 1, then depth 2, then depth 3, etc.
114# until it reaches the final depth it needed to calculate at depth n. The reason for
115# this is that it may be mathematically shown that this does not dignificantly increase
116# computation and allows the A.I. to make its best move if it needs to abide by a
117# time limit.
118# 3. Better data structure - I believe the structure I have used to keep the state of
119# the board (list of a list) may be slowing down accessing its elements or assigning
120# its elements. Improvement in efficiency of my code by changing data structures may
121# potentially improve the speed at which my AI makes its move.
122# 4. Import of large opening tables: There are databases available online that store
123# the best moves played by grandmasters at various key opening positions of the chess
124# game. Although my AI does make use of an opening table that I recorded for it myself,
125# it is not able to respond to many opening positions using the table since the table
126# only convers few positions. If an opening table with millions of positions could be
127# imported to this program, the AI's moves would improve in the beginning. It would also
128# give it more variety in terms of the move it plays. Furthermore, using good openings
129# allows the AI to make the best moves in the field it is best at: middle game tactics.
130# 5. Better evaluation of positions - The current features evaluated by the evaluation
131# function when judging a positoin to give it a score allows for good opening games and
132# tactics that often allow it to gain advantage over the opponents that I have tested it
133# against. However, there are many aspects of playing good chess that it does not
134# consider: like having good mobility of your pieces (eg a trapped bishop should be bad
135# for the AI but it doesn't know that). Other aspects include king safety, pawn structure,
136# etc. It could also use different evaluation for each game phase. For example, a pawn is
137# not worth much at the opening phase of the game but in the endgame it is very important
138# and so should be evaulated as a valuable piece.
139# 6. Endgame tables - As good as my AI may be in middle games, given a queen and a king to
140# attempt checkmate against a lone king, it would be unlikely for it to succeed. This is
141# because such checkmates, despite being simple, require a large number of combination of
142# moves to occur, the depth of which my AI would not be able to see. So endgame table allows
143# it to know (for a very large number of endgame positions) the best move to play in order
144# to attempt a win or a draw (or try its best to avoid a loss).
145
146
147#Note about coordinates:
148#Normally, algebraic notation is used to specify a box on a chess board. In this
149#program, coordinates will be index referecnes to the 2_D array that stores the
150#state of the board. Thus, e4 in algebraic notation would be expressed as (4,4)
151#in this program.
152
153#Import dependencies:
154import pygame #Game library
155from pygame.locals import * #For useful variables
156import copy #Library used to make exact copies of lists.
157import pickle #Library used to store dictionaries in a text file and read them from text files.
158import random #Used for making random selections
159from collections import defaultdict #Used for giving dictionary values default data types.
160from collections import Counter #For counting elements in a list effieciently.
161import threading #To allow for AI to think simultaneously while the GUI is coloring the board.
162
163
164
165########################################################
166#Class Definitions:
167#####################################################
168#There are three classes used in this program:
169# 1. GamePosition - This class stores a chess position. A chess position constitutes several
170# features that specify the state of the game, such as the the player that has to play next,
171# castling rights of the players, number of irreversible moves played so far, the positions of
172# pieces on the board, etc.
173# 2. Shades - This is used for GUI. A shade is a transparent colored image that is displayed on
174# a specific square of the chess board, in order to show various things to the user such as
175# the squares to which a piece may move, the square that is currently selected, etc. The class
176# stores a reference to the image that the instance of the class should display when needed. It
177# also stores the coordinates at which the shade would be applied.
178# 3. Piece - This is also used for GUI. A Piece object stores the information about the image
179# that a piece should display (pawn, queen, etc.) and the coordinate at which it should be
180# displayed on thee chess board.
181##########################################################
182class GamePosition:
183 def __init__(self,board,player,castling_rights,EnP_Target,HMC,history = {}):
184 self.board = board #A 2D array containing information about piece postitions. Check main
185 #function to see an example of such a representation.
186 self.player = player #Stores the side to move. If white to play, equals 0. If black to
187 #play, stores 1.
188 self.castling = castling_rights #A list that contains castling rights for white and
189 #black. Each castling right is a list that contains right to castle kingside and queenside.
190 self.EnP = EnP_Target #Stores the coordinates of a square that can be targeted by en passant capture.
191 self.HMC = HMC #Half move clock. Stores the number of irreversible moves made so far, in order to help
192 #detect draw by 50 moves without any capture or pawn movement.
193 self.history = history #A dictionary that stores as key a position (hashed) and the value of each of
194 #these keys represents the number of times each of these positions was repeated in order for this
195 #position to be reached.
196
197 def getboard(self):
198 return self.board
199 def setboard(self,board):
200 self.board = board
201 def getplayer(self):
202 return self.player
203 def setplayer(self,player):
204 self.player = player
205 def getCastleRights(self):
206 return self.castling
207 def setCastleRights(self,castling_rights):
208 self.castling = castling_rights
209 def getEnP(self):
210 return self.EnP
211 def setEnP(self, EnP_Target):
212 self.EnP = EnP_Target
213 def getHMC(self):
214 return self.HMC
215 def setHMC(self,HMC):
216 self.HMC = HMC
217 def checkRepition(self):
218 #Returns True if any of of the values in the history dictionary is greater than 3.
219 #This would mean a position had been repeated at least thrice in order to reach the
220 #current position in this game.
221 return any(value>=3 for value in self.history.itervalues())
222 def addtoHistory(self,position):
223 #Generate a unique key out of the current position:
224 key = pos2key(position)
225 #Add it to the history dictionary.
226 self.history[key] = self.history.get(key,0) + 1
227 def gethistory(self):
228 return self.history
229 def clone(self):
230 #This method returns another instance of the current object with exactly the same
231 #parameters but independent of the current object.
232 clone = GamePosition(copy.deepcopy(self.board), #Independent copy
233 self.player,
234 copy.deepcopy(self.castling), #Independent copy
235 self.EnP,
236 self.HMC)
237 return clone
238class Shades:
239 #Self explanatory:
240 def __init__(self,image,coord):
241 self.image = image
242 self.pos = coord
243 def getInfo(self):
244 return [self.image,self.pos]
245class Piece:
246 def __init__(self,pieceinfo,chess_coord):
247 #pieceinfo is a string such as 'Qb'. The Q represents Queen and b
248 #shows the fact that it is black:
249 piece = pieceinfo[0]
250 color = pieceinfo[1]
251 #Get the information about where the image for this piece is stored
252 #on the overall sprite image with all the pieces. Note that
253 #square_width and square_height represent the size of a square on the
254 #chess board.
255 if piece=='K':
256 index = 0
257 elif piece=='Q':
258 index = 1
259 elif piece=='B':
260 index = 2
261 elif piece == 'N':
262 index = 3
263 elif piece == 'R':
264 index = 4
265 elif piece == 'P':
266 index = 5
267 left_x = square_width*index
268 if color == 'w':
269 left_y = 0
270 else:
271 left_y = square_height
272
273 self.pieceinfo = pieceinfo
274 #subsection defines the part of the sprite image that represents our
275 #piece:
276 self.subsection = (left_x,left_y,square_width,square_height)
277 #There are two ways that the position of a piece is defined on the
278 #board. The default one used is the chess_coord, which stores something
279 #like (3,2). It represents the chess coordinate where our piece image should
280 #be blitted. On the other hand, is pos does not hold the default value
281 #of (-1,-1), it will hold pixel coordinates such as (420,360) that represents
282 #the location in the window that the piece should be blitted on. This is
283 #useful for example if our piece is transitioning from a square to another:
284 self.chess_coord = chess_coord
285 self.pos = (-1,-1)
286
287 #The methods are self explanatory:
288 def getInfo(self):
289 return [self.chess_coord, self.subsection,self.pos]
290 def setpos(self,pos):
291 self.pos = pos
292 def getpos(self):
293 return self.pos
294 def setcoord(self,coord):
295 self.chess_coord = coord
296 def __repr__(self):
297 #useful for debugging
298 return self.pieceinfo+'('+str(chess_coord[0])+','+str(chess_coord[1])+')'
299
300
301########################################################
302#Function Definitions:
303#####################################################
304
305# The functions in this file may be classified into three main groups:
306# 1. Chess Processing Functions - these are the functions that work with variables
307# that hold the information about game state.
308# 2. GUI Functions - These are the functions that work together to display the
309# chess board to the user and get the user's input as well, so that they may be
310# passed on to the Chess Processing Functions.
311# 3. AI related functions - These are the functions involved in helping the
312# computer make decisions in terms of what should be played.
313
314#///////////////////////////////CHESS PROCESSING FUNCTIONS////////////////////
315#
316# drawText(board) - This function is not called in this program. It is useful for debugging
317# purposes, as it allows a board to be printed to the screen in a readable format.
318#
319# isOccupied(board,x,y) - Returns true if a given coordinate on the board is not empty, and
320# false otherwise.
321#
322# isOccupiedby(board,x,y,color) - Same as above, but only returns true if the square
323# specified by the coordinates is of the specifc color inputted.
324#
325# filterbyColor(board,listofTuples,color) - This function takes the board state, a list
326# of coordinates, and a color as input. It will return the same list, but without
327# coordinates that are out of bounds of the board and also without those occupied by the
328# pieces of the particular color passed to this function as an argument. In other words,
329# if 'white' is passed in, it will not return any white occupied square.
330#
331# lookfor(board,piece) - This functions takes the 2D array that represents a board and finds
332# the indices of all the locations that is occupied by the specified piece. The list of
333# indices is returned.
334#
335# isAttackedby(position,target_x,target_y,color) - This function checks if the square specified
336# by (target_x,target_y) coordinates is being attacked by any of a specific colored set of pieces.
337#
338# findPossibleSquares(position,x,y,AttackSearch=False) - This function takes as its input the
339# current state of the chessboard, and a particular x and y coordinate. It will return for the
340# piece on that board a list of possible coordinates it could move to, including captures and
341# excluding illegal moves (eg moves that leave a king under check). AtttackSearch is an
342# argument used to ensure infinite recursions do not occur.
343#
344# makemove(position,x,y,x2,y2) - This function makes a move on the board. The position object
345# gets updated here with new information. (x,y) are coordinates of the piece to be moved, and
346# (x2,y2) are coordinates of the destination. (x2,y2) being correct destination (ie the move
347# a valid one) is not checked for and is assumed to be the case.
348#
349# opp(color) - Returns the complimentary color to the one passed. So inputting 'black' returns
350# 'w', for example.
351#
352# isCheck(position,color) - This function takes a position as its input and checks if the
353# King of the specified color is under attack by the enemy. Returns true if that is the case,
354# and false otherwise.
355#
356# isCheckmate(position,color=-1) - This function tells you if a position is a checkmate.
357# Color is an optional argument that may be passed to specifically check for mate against a
358# specific color.
359#
360# isStalemate(position) - This function checks if a particular position is a stalemate.
361# If it is, it returns true, otherwise it returns false.
362#
363# getallpieces(position,color) - This function returns a list of positions of all the pieces on
364# the board of a particular color.
365#
366# allMoves(position, color) - This function takes as its argument a position and a color/colorsign
367# that represents a side. It generates a list of all possible moves for that side and returns it.
368#
369# pos2key(position) - This function takes a position as input argument. For this particular
370# position, it will generate a unique key that can be used in a dictionary by making it hashable.
371#
372
373##/////////////////////////////////////////////GUI FUNCTIONS////////////////////////////////
374# chess_coord_to_pixels(chess_coord) - This function takes as input a chess coordinate such as
375# (4,7). It returns the top left corner pixel at which a piece of the given size should be
376# placed on the board for it to appear at the correct square.
377#
378# pixel_coord_to_chess(pixel_coord) - Does the exact opposite of above, namely taking the
379# pixel coordinate and giving back the chess coordinate of a particular square.
380#
381# getPiece(chess_coord) - Gives back the reference to the Piece object that occupies
382# a particular chess coordinate.
383#
384# createPieces(board) - Loops through all the pieces in the inputted board array
385# and creates an instance of Piece class for each of them. Returns a list of two
386# lists: one that contains all the references to the white pieces, and the other
387# for black.
388#
389# createShades(listofTuples) - This will modify the global list listofShades. It
390# will create instance of class Shade for all the specified coordinates given in
391# listofTuples (the input argument). These squares are ones that are attacked by
392# a particular piece. Furthermore, it will append other appropriate shades as well,
393# such as shades used to show checkmate or stalemate.
394#
395# drawBoard() - Blits to the screen the board, the pieces, and the shades needed
396# to make the game look nice.
397#
398
399##//////////////////////////////////////AI RELATED FUNCTIONS////////////////////////////////
400#
401# negamax(position,depth,alpha,beta,colorsign,bestMoveReturn,root=True) - This
402# function takes as its inputs a position, and a depth to which moves should be
403# analysed. It will generate moves and analyse resulting positions to decide the
404# best move to be played for the AI. Alpha and beta are lower and upper bounds to
405# a position's possible
406# score values and allows for alpha-beta pruning. Colorsign indicates the player
407# to move. bestMoveReturn is a list that will be assigned the move to be played.
408# Returning is not possible in this case because threading is used. root is a
409# variable that keeps track of whether the original node is processing now or a
410# lower node. Alpha beta pruning is not explained in detail here so I recommend
411# learning more about it if the code does not make sense.
412# Note that the function does not always traverse a tree to give back the move
413# to be played by the AI. It also checks the opening table to see if there is a
414# prerecorded move that it can play without searching. Scoring of each position
415# is also stored in a global dictionary to allow for time-saving if the same
416# position occurs elsewhere in the tree. The code used here is adapted from the
417# pseudocode provided at Wikipidea:
418# https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning
419#
420# evaluate(position) - This function takes as input a position to be analysed.
421# It will look at the positioning of pieces on the board to judge whether white
422# has an advantage or black. If it returns zero, it means it considers the
423# position to be equal for both sides. A positive value is an advantage to the
424# white side and a negative value is an advantage to the black side.
425#
426# pieceSquareTable(flatboard,gamephase) - Gives a position a score based solely
427# on tables that define points for each position for each piece type.
428#
429# doubledPawns(board,color) - This function counts the number of doubled pawns
430# for a player and returns it. Doubled pawns are those that are on the same file.
431#
432# blockedPawns(board,color) - This function counts the number of blocked pawns
433# for a player and returns it. Blocked pawns are those that have a piece in front
434# of them and so cannot advance forward.
435#
436# isolatedPawns(board,color) - This function counts the number of isolated pawns
437# for a player. These are pawns that do not have supporting pawns on adjacent files
438# and so are difficult to protect.
439#
440#
441##################################/////CHESS PROCESSING FUNCTIONS\\\\########################
442def drawText(board):
443 for i in range(len(board)):
444 for k in range(len(board[i])):
445 if board[i][k]==0:
446 board[i][k] = 'Oo'
447 print (board[i])
448 for i in range(len(board)):
449 for k in range(len(board[i])):
450 if board[i][k]=='Oo':
451 board[i][k] = 0
452def isOccupied(board,x,y):
453 if board[y][x] == 0:
454 #The square has nothing on it.
455 return False
456 return True
457def isOccupiedby(board,x,y,color):
458 if board[y][x]==0:
459 #the square has nothing on it.
460 return False
461 if board[y][x][1] == color[0]:
462 #The square has a piece of the color inputted.
463 return True
464 #The square has a piece of the opposite color.
465 return False
466def filterbyColor(board,listofTuples,color):
467 filtered_list = []
468 #Go through each coordinate:
469 for pos in listofTuples:
470 x = pos[0]
471 y = pos[1]
472 if x>=0 and x<=7 and y>=0 and y<=7 and not isOccupiedby(board,x,y,color):
473 #coordinates are on-board and no same-color piece is on the square.
474 filtered_list.append(pos)
475 return filtered_list
476def lookfor(board,piece):
477 listofLocations = []
478 for row in range(8):
479 for col in range(8):
480 if board[row][col] == piece:
481 x = col
482 y = row
483 listofLocations.append((x,y))
484 return listofLocations
485def isAttackedby(position,target_x,target_y,color):
486 #Get board
487 board = position.getboard()
488 #Get b from black or w from white
489 color = color[0]
490 #Get all the squares that are attacked by the particular side:
491 listofAttackedSquares = []
492 for x in range(8):
493 for y in range(8):
494 if board[y][x]!=0 and board[y][x][1]==color:
495 listofAttackedSquares.extend(
496 findPossibleSquares(position,x,y,True)) #The true argument
497 #prevents infinite recursion.
498 #Check if the target square falls under the range of attack by the specified
499 #side, and return it:
500 return (target_x,target_y) in listofAttackedSquares
501def findPossibleSquares(position,x,y,AttackSearch=False):
502 #Get individual component data from the position object:
503 board = position.getboard()
504 player = position.getplayer()
505 castling_rights = position.getCastleRights()
506 EnP_Target = position.getEnP()
507 #In case something goes wrong:
508 if len(board[y][x])!=2: #Unexpected, return empty list.
509 return []
510 piece = board[y][x][0] #Pawn, rook, etc.
511 color = board[y][x][1] #w or b.
512 #Have the complimentary color stored for convenience:
513 enemy_color = opp(color)
514 listofTuples = [] #Holds list of attacked squares.
515
516 if piece == 'P': #The piece is a pawn.
517 if color=='w': #The piece is white
518 if not isOccupied(board,x,y-1) and not AttackSearch:
519 #The piece immediately above is not occupied, append it.
520 listofTuples.append((x,y-1))
521
522 if y == 6 and not isOccupied(board,x,y-2):
523 #If pawn is at its initial position, it can move two squares.
524 listofTuples.append((x,y-2))
525
526 if x!=0 and isOccupiedby(board,x-1,y-1,'black'):
527 #The piece diagonally up and left of this pawn is a black piece.
528 #Also, this is not an 'a' file pawn (left edge pawn)
529 listofTuples.append((x-1,y-1))
530 if x!=7 and isOccupiedby(board,x+1,y-1,'black'):
531 #The piece diagonally up and right of this pawn is a black one.
532 #Also, this is not an 'h' file pawn.
533 listofTuples.append((x+1,y-1))
534 if EnP_Target!=-1: #There is a possible en pasant target:
535 if EnP_Target == (x-1,y-1) or EnP_Target == (x+1,y-1):
536 #We're at the correct location to potentially perform en
537 #passant:
538 listofTuples.append(EnP_Target)
539
540 elif color=='b': #The piece is black, same as above but opposite side.
541 if not isOccupied(board,x,y+1) and not AttackSearch:
542 listofTuples.append((x,y+1))
543 if y == 1 and not isOccupied(board,x,y+2):
544 listofTuples.append((x,y+2))
545 if x!=0 and isOccupiedby(board,x-1,y+1,'white'):
546 listofTuples.append((x-1,y+1))
547 if x!=7 and isOccupiedby(board,x+1,y+1,'white'):
548 listofTuples.append((x+1,y+1))
549 if EnP_Target == (x-1,y+1) or EnP_Target == (x+1,y+1):
550 listofTuples.append(EnP_Target)
551
552 elif piece == 'R': #The piece is a rook.
553 #Get all the horizontal squares:
554 for i in [-1,1]:
555 #i is -1 then +1. This allows for searching right and left.
556 kx = x #This variable stores the x coordinate being looked at.
557 while True: #loop till break.
558 kx = kx + i #Searching left or right
559 if kx<=7 and kx>=0: #Making sure we're still in board.
560
561 if not isOccupied(board,kx,y):
562 #The square being looked at it empty. Our rook can move
563 #here.
564 listofTuples.append((kx,y))
565 else:
566 #The sqaure being looked at is occupied. If an enemy
567 #piece is occupying it, it can be captured so its a valid
568 #move.
569 if isOccupiedby(board,kx,y,enemy_color):
570 listofTuples.append((kx,y))
571 #Regardless of the occupying piece color, the rook cannot
572 #jump over. No point continuing search beyond in this
573 #direction:
574 break
575
576 else: #We have exceeded the limits of the board
577 break
578 #Now using the same method, get the vertical squares:
579 for i in [-1,1]:
580 ky = y
581 while True:
582 ky = ky + i
583 if ky<=7 and ky>=0:
584 if not isOccupied(board,x,ky):
585 listofTuples.append((x,ky))
586 else:
587 if isOccupiedby(board,x,ky,enemy_color):
588 listofTuples.append((x,ky))
589 break
590 else:
591 break
592
593 elif piece == 'N': #The piece is a knight.
594 #The knight can jump across a board. It can jump either two or one
595 #squares in the x or y direction, but must jump the complimentary amount
596 #in the other. In other words, if it jumps 2 sqaures in the x direction,
597 #it must jump one square in the y direction and vice versa.
598 for dx in [-2,-1,1,2]:
599 if abs(dx)==1:
600 sy = 2
601 else:
602 sy = 1
603 for dy in [-sy,+sy]:
604 listofTuples.append((x+dx,y+dy))
605 #Filter the list of tuples so that only valid squares exist.
606 listofTuples = filterbyColor(board,listofTuples,color)
607 elif piece == 'B': # A bishop.
608 #A bishop moves diagonally. This means a change in x is accompanied by a
609 #change in y-coordiante when the piece moves. The changes are exactly the
610 #same in magnitude and direction.
611 for dx in [-1,1]: #Allow two directions in x.
612 for dy in [-1,1]: #Similarly, up and down for y.
613 kx = x #These varibales store the coordinates of the square being
614 #observed.
615 ky = y
616 while True: #loop till broken.
617 kx = kx + dx #change x
618 ky = ky + dy #change y
619 if kx<=7 and kx>=0 and ky<=7 and ky>=0:
620 #square is on the board
621 if not isOccupied(board,kx,ky):
622 #The square is empty, so our bishop can go there.
623 listofTuples.append((kx,ky))
624 else:
625 #The square is not empty. If it has a piece of the
626 #enemy,our bishop can capture it:
627 if isOccupiedby(board,kx,ky,enemy_color):
628 listofTuples.append((kx,ky))
629 #Bishops cannot jump over other pieces so terminate
630 #the search here:
631 break
632 else:
633 #Square is not on board. Stop looking for more in this
634 #direction:
635 break
636
637 elif piece == 'Q': #A queen
638 #A queen's possible targets are the union of all targets that a rook and
639 #a bishop could have made from the same location
640 #Temporarily pretend there is a rook on the spot:
641 board[y][x] = 'R' + color
642 list_rook = findPossibleSquares(position,x,y,True)
643 #Temporarily pretend there is a bishop:
644 board[y][x] = 'B' + color
645 list_bishop = findPossibleSquares(position,x,y,True)
646 #Merge the lists:
647 listofTuples = list_rook + list_bishop
648 #Change the piece back to a queen:
649 board[y][x] = 'Q' + color
650 elif piece == 'K': # A king!
651 #A king can make one step in any direction:
652 for dx in [-1,0,1]:
653 for dy in [-1,0,1]:
654 listofTuples.append((x+dx,y+dy))
655 #Make sure the targets aren't our own piece or off-board:
656 listofTuples = filterbyColor(board,listofTuples,color)
657 if not AttackSearch:
658 #Kings can potentially castle:
659 right = castling_rights[player]
660 #Kingside
661 if (right[0] and #has right to castle
662 board[y][7]!=0 and #The rook square is not empty
663 board[y][7][0]=='R' and #There is a rook at the appropriate place
664 not isOccupied(board,x+1,y) and #The square on its right is empty
665 not isOccupied(board,x+2,y) and #The second square beyond is also empty
666 not isAttackedby(position,x,y,enemy_color) and #The king isn't under atack
667 not isAttackedby(position,x+1,y,enemy_color) and #Or the path through which
668 not isAttackedby(position,x+2,y,enemy_color)):#it will move
669 listofTuples.append((x+2,y))
670 #Queenside
671 if (right[1] and #has right to castle
672 board[y][0]!=0 and #The rook square is not empty
673 board[y][0][0]=='R' and #The rook square is not empty
674 not isOccupied(board,x-1,y)and #The square on its left is empty
675 not isOccupied(board,x-2,y)and #The second square beyond is also empty
676 not isOccupied(board,x-3,y) and #And the one beyond.
677 not isAttackedby(position,x,y,enemy_color) and #The king isn't under atack
678 not isAttackedby(position,x-1,y,enemy_color) and #Or the path through which
679 not isAttackedby(position,x-2,y,enemy_color)):#it will move
680 listofTuples.append((x-2,y)) #Let castling be an option.
681
682 #Make sure the king is not under attack as a result of this move:
683 if not AttackSearch:
684 new_list = []
685 for tupleq in listofTuples:
686 x2 = tupleq[0]
687 y2 = tupleq[1]
688 temp_pos = position.clone()
689 makemove(temp_pos,x,y,x2,y2)
690 if not isCheck(temp_pos,color):
691 new_list.append(tupleq)
692 listofTuples = new_list
693 return listofTuples
694def makemove(position,x,y,x2,y2):
695 #Get data from the position:
696 board = position.getboard()
697 piece = board[y][x][0]
698 color = board[y][x][1]
699 #Get the individual game components:
700 player = position.getplayer()
701 castling_rights = position.getCastleRights()
702 EnP_Target = position.getEnP()
703 half_move_clock = position.getHMC()
704 #Update the half move clock:
705 if isOccupied(board,x2,y2) or piece=='P':
706 #Either a capture was made or a pawn has moved:
707 half_move_clock = 0
708 else:
709 #An irreversible move was played:
710 half_move_clock += 1
711
712 #Make the move:
713 board[y2][x2] = board[y][x]
714 board[y][x] = 0
715
716 #Special piece requirements:
717 #King:
718 if piece == 'K':
719 #Ensure that since a King is moved, the castling
720 #rights are lost:
721 castling_rights[player] = [False,False]
722 #If castling occured, place the rook at the appropriate location:
723 if abs(x2-x) == 2:
724 if color=='w':
725 l = 7
726 else:
727 l = 0
728
729 if x2>x:
730 board[l][5] = 'R'+color
731 board[l][7] = 0
732 else:
733 board[l][3] = 'R'+color
734 board[l][0] = 0
735 #Rook:
736 if piece=='R':
737 #The rook moved. Castling right for this rook must be removed.
738 if x==0 and y==0:
739 #Black queenside
740 castling_rights[1][1] = False
741 elif x==7 and y==0:
742 #Black kingside
743 castling_rights[1][0] = False
744 elif x==0 and y==7:
745 #White queenside
746 castling_rights[0][1] = False
747 elif x==7 and y==7:
748 #White kingside
749 castling_rights[0][0] = False
750 #Pawn:
751 if piece == 'P':
752 #If an en passant kill was made, the target enemy must die:
753 if EnP_Target == (x2,y2):
754 if color=='w':
755 board[y2+1][x2] = 0
756 else:
757 board[y2-1][x2] = 0
758 #If a pawn moved two steps, there is a potential en passant
759 #target. Otherise, there isn't. Update the variable:
760 if abs(y2-y)==2:
761 EnP_Target = (x,(y+y2)/2)
762 else:
763 EnP_Target = -1
764 #If a pawn moves towards the end of the board, it needs to
765 #be promoted. Note that in this game a pawn is being promoted
766 #to a queen regardless of user choice.
767 if y2==0:
768 board[y2][x2] = 'Qw'
769 elif y2 == 7:
770 board[y2][x2] = 'Qb'
771 else:
772 #If a pawn did not move, the en passsant target is gone as well,
773 #since a turn has passed:
774 EnP_Target = -1
775
776 #Since a move has been made, the other player
777 #should be the 'side to move'
778 player = 1 - player
779 #Update the position data:
780 position.setplayer(player)
781 position.setCastleRights(castling_rights)
782 position.setEnP(EnP_Target)
783 position.setHMC(half_move_clock)
784def opp(color):
785 color = color[0]
786 if color == 'w':
787 oppcolor = 'b'
788 else:
789 oppcolor = 'w'
790 return oppcolor
791def isCheck(position,color):
792 #Get data:
793 board = position.getboard()
794 color = color[0]
795 enemy = opp(color)
796 piece = 'K' + color
797 #Get the coordinates of the king:
798 x,y = lookfor(board,piece)[0]
799 #Check if the position of the king is attacked by
800 #the enemy and return the result:
801 return isAttackedby(position,x,y,enemy)
802def isCheckmate(position,color=-1):
803
804 if color==-1:
805 return isCheckmate(position,'white') or isCheckmate(position,'b')
806 color = color[0]
807 if isCheck(position,color) and allMoves(position,color)==[]:
808 #The king is under attack, and there are no possible moves for this side to make:
809 return True
810 #Either the king is not under attack or there are possible moves to be played:
811 return False
812def isStalemate(position):
813 #Get player to move:
814 player = position.getplayer()
815 #Get color:
816 if player==0:
817 color = 'w'
818 else:
819 color = 'b'
820 if not isCheck(position,color) and allMoves(position,color)==[]:
821 #The player to move is not under check yet cannot make a move.
822 #It is a stalemate.
823 return True
824 return False
825def getallpieces(position,color):
826 #Get the board:
827 board = position.getboard()
828 listofpos = []
829 for j in range(8):
830 for i in range(8):
831 if isOccupiedby(board,i,j,color):
832 listofpos.append((i,j))
833 return listofpos
834def allMoves(position, color):
835 #Find if it is white to play or black:
836 if color==1:
837 color = 'white'
838 elif color ==-1:
839 color = 'black'
840 color = color[0]
841 #Get all pieces controlled by this side:
842 listofpieces = getallpieces(position,color)
843 moves = []
844 #Loop through each piece:
845 for pos in listofpieces:
846 #For each piece, find all the targets it can attack:
847 targets = findPossibleSquares(position,pos[0],pos[1])
848 for target in targets:
849 #Save them all as possible moves:
850 moves.append([pos,target])
851 return moves
852def pos2key(position):
853 #Get board:
854 board = position.getboard()
855 #Convert the board into a tuple so it is hashable:
856 boardTuple = []
857 for row in board:
858 boardTuple.append(tuple(row))
859 boardTuple = tuple(boardTuple)
860 #Get castling rights:
861 rights = position.getCastleRights()
862 #Convert to a tuple:
863 tuplerights = (tuple(rights[0]),tuple(rights[1]))
864 #Generate the key, which is a tuple that also takes into account the side to play:
865 key = (boardTuple,position.getplayer(),
866 tuplerights)
867 #Return the key:
868 return key
869
870##############################////////GUI FUNCTIONS\\\\\\\\\\\\\#############################
871def chess_coord_to_pixels(chess_coord):
872 x,y = chess_coord
873 #There are two sets of coordinates that this function could choose to return.
874 #One is the coordinates that would be usually returned, the other is one that
875 #would be returned if the board were to be flipped.
876 #Note that square width and height variables are defined in the main function and
877 #so are accessible here as global variables.
878 if isAI:
879 if AIPlayer==0:
880 #This means you're playing against the AI and are playing as black:
881 return ((7-x)*square_width, (7-y)*square_height)
882 else:
883 return (x*square_width, y*square_height)
884 #Being here means two player game is being played.
885 #If the flipping mode is enabled, and the player to play is black,
886 #the board should flip, but not until the transition animation for
887 #white movement is complete:
888 if not isFlip or player==0 ^ isTransition:
889 return (x*square_width, y*square_height)
890 else:
891 return ((7-x)*square_width, (7-y)*square_height)
892def pixel_coord_to_chess(pixel_coord):
893 x,y = pixel_coord[0]/square_width, pixel_coord[1]/square_height
894 #See comments for chess_coord_to_pixels() for an explanation of the
895 #conditions seen here:
896 if isAI:
897 if AIPlayer==0:
898 return (7-x,7-y)
899 else:
900 return (x,y)
901 if not isFlip or player==0 ^ isTransition:
902 return (x,y)
903 else:
904 return (7-x,7-y)
905def getPiece(chess_coord):
906 for piece in listofWhitePieces+listofBlackPieces:
907 #piece.getInfo()[0] represents the chess coordinate occupied
908 #by piece.
909 if piece.getInfo()[0] == chess_coord:
910 return piece
911def createPieces(board):
912 #Initialize containers:
913 listofWhitePieces = []
914 listofBlackPieces = []
915 #Loop through all squares:
916 for i in range(8):
917 for k in range(8):
918 if board[i][k]!=0:
919 #The square is not empty, create a piece object:
920 p = Piece(board[i][k],(k,i))
921 #Append the reference to the object to the appropriate
922 #list:
923 if board[i][k][1]=='w':
924 listofWhitePieces.append(p)
925 else:
926 listofBlackPieces.append(p)
927 #Return both:
928 return [listofWhitePieces,listofBlackPieces]
929def createShades(listofTuples):
930 global listofShades
931 #Empty the list
932 listofShades = []
933 if isTransition:
934 #Nothing should be shaded when a piece is being animated:
935 return
936 if isDraw:
937 #The game ended with a draw. Make yellow circle shades for
938 #both the kings to show this is the case:
939 coord = lookfor(board,'Kw')[0]
940 shade = Shades(circle_image_yellow,coord)
941 listofShades.append(shade)
942 coord = lookfor(board,'Kb')[0]
943 shade = Shades(circle_image_yellow,coord)
944 listofShades.append(shade)
945 #There is no need to go further:
946 return
947 if chessEnded:
948 #The game has ended, with a checkmate because it cannot be a
949 #draw if the code reached here.
950 #Give the winning king a green circle shade:
951 coord = lookfor(board,'K'+winner)[0]
952 shade = Shades(circle_image_green_big,coord)
953 listofShades.append(shade)
954 #If either king is under attack, give them a red circle:
955 if isCheck(position,'white'):
956 coord = lookfor(board,'Kw')[0]
957 shade = Shades(circle_image_red,coord)
958 listofShades.append(shade)
959 if isCheck(position,'black'):
960 coord = lookfor(board,'Kb')[0]
961 shade = Shades(circle_image_red,coord)
962 listofShades.append(shade)
963 #Go through all the target squares inputted:
964 for pos in listofTuples:
965 #If the target square is occupied, it can be captured.
966 #For a capturable square, there is a different shade.
967 #Create the appropriate shade for each target square:
968 if isOccupied(board,pos[0],pos[1]):
969 img = circle_image_capture
970 else:
971 img = circle_image_green
972 shade = Shades(img,pos)
973 #Append:
974 listofShades.append(shade)
975def drawBoard():
976 #Blit the background:
977 screen.blit(background,(0,0))
978 #Choose the order in which to blit the pieces.
979 #If black is about to play for example, white pieces
980 #should be blitted first, so that when black is capturing,
981 #the piece appears above:
982 if player==1:
983 order = [listofWhitePieces,listofBlackPieces]
984 else:
985 order = [listofBlackPieces,listofWhitePieces]
986 if isTransition:
987 #If a piece is being animated, the player info is changed despite
988 #white still capturing over black, for example. Reverse the order:
989 order = list(reversed(order))
990 #The shades which appear during the following three conditions need to be
991 #blitted first to appear under the pieces:
992 if isDraw or chessEnded or isAIThink:
993 #Shades
994 for shade in listofShades:
995 img,chess_coord = shade.getInfo()
996 pixel_coord = chess_coord_to_pixels(chess_coord)
997 screen.blit(img,pixel_coord)
998 #Make shades to show what the previous move played was:
999 if prevMove[0]!=-1 and not isTransition:
1000 x,y,x2,y2 = prevMove
1001 screen.blit(yellowbox_image,chess_coord_to_pixels((x,y)))
1002 screen.blit(yellowbox_image,chess_coord_to_pixels((x2,y2)))
1003
1004 #Blit the Pieces:
1005 #Notw that one side has to be below the green circular shades to show
1006 #that they are being targeted, and the other side if dragged to such
1007 # a square should be blitted on top to show that it is capturing:
1008
1009 #Potentially captured pieces:
1010 for piece in order[0]:
1011
1012 chess_coord,subsection,pos = piece.getInfo()
1013 pixel_coord = chess_coord_to_pixels(chess_coord)
1014 if pos==(-1,-1):
1015 #Blit to default square:
1016 screen.blit(pieces_image,pixel_coord,subsection)
1017 else:
1018 #Blit to the specific coordinates:
1019 screen.blit(pieces_image,pos,subsection)
1020 #Blit the shades in between:
1021 if not (isDraw or chessEnded or isAIThink):
1022 for shade in listofShades:
1023 img,chess_coord = shade.getInfo()
1024 pixel_coord = chess_coord_to_pixels(chess_coord)
1025 screen.blit(img,pixel_coord)
1026 #Potentially capturing pieces:
1027 for piece in order[1]:
1028 chess_coord,subsection,pos = piece.getInfo()
1029 pixel_coord = chess_coord_to_pixels(chess_coord)
1030 if pos==(-1,-1):
1031 #Default square
1032 screen.blit(pieces_image,pixel_coord,subsection)
1033 else:
1034 #Specifc pixels:
1035 screen.blit(pieces_image,pos,subsection)
1036
1037###########################////////AI RELATED FUNCTIONS\\\\\\\\\\############################
1038
1039def negamax(position,depth,alpha,beta,colorsign,bestMoveReturn,root=True):
1040 #First check if the position is already stored in the opening database dictionary:
1041 if root:
1042 #Generate key from current position:
1043 key = pos2key(position)
1044 if key in openings:
1045 #Return the best move to be played:
1046 bestMoveReturn[:] = random.choice(openings[key])
1047 return
1048 #Access global variable that will store scores of positions already evaluated:
1049 global searched
1050 #If the depth is zero, we are at a leaf node (no more depth to be analysed):
1051 if depth==0:
1052 return colorsign*evaluate(position)
1053 #Generate all the moves that can be played:
1054 moves = allMoves(position, colorsign)
1055 #If there are no moves to be played, just evaluate the position and return it:
1056 if moves==[]:
1057 return colorsign*evaluate(position)
1058 #Initialize a best move for the root node:
1059 if root:
1060 bestMove = moves[0]
1061 #Initialize the best move's value:
1062 bestValue = -100000
1063 #Go through each move:
1064 for move in moves:
1065 #Make a clone of the current move and perform the move on it:
1066 newpos = position.clone()
1067 makemove(newpos,move[0][0],move[0][1],move[1][0],move[1][1])
1068 #Generate the key for the new resulting position:
1069 key = pos2key(newpos)
1070 #If this position was already searched before, retrieve its node value.
1071 #Otherwise, calculate its node value and store it in the dictionary:
1072 if key in searched:
1073 value = searched[key]
1074 else:
1075 value = -negamax(newpos,depth-1, -beta,-alpha,-colorsign,[],False)
1076 searched[key] = value
1077 #If this move is better than the best so far:
1078 if value>bestValue:
1079 #Store it
1080 bestValue = value
1081 #If we're at root node, store the move as the best move:
1082 if root:
1083 bestMove = move
1084 #Update the lower bound for this node:
1085 alpha = max(alpha,value)
1086 if alpha>=beta:
1087 #If our lower bound is higher than the upper bound for this node, there
1088 #is no need to look at further moves:
1089 break
1090 #If this is the root node, return the best move:
1091 if root:
1092 searched = {}
1093 bestMoveReturn[:] = bestMove
1094 return
1095 #Otherwise, return the bestValue (i.e. value for this node.)
1096 return bestValue
1097def evaluate(position):
1098 if isCheckmate(position,'white'):
1099 #Major advantage to black
1100 return -20000
1101 if isCheckmate(position,'black'):
1102 #Major advantage to white
1103 return 20000
1104 #Get the board:
1105 board = position.getboard()
1106 #Flatten the board to a 1D array for faster calculations:
1107 flatboard = [x for row in board for x in row]
1108 #Create a counter object to count number of each pieces:
1109 c = Counter(flatboard)
1110 Qw = c['Qw']
1111 Qb = c['Qb']
1112 Rw = c['Rw']
1113 Rb = c['Rb']
1114 Bw = c['Bw']
1115 Bb = c['Bb']
1116 Nw = c['Nw']
1117 Nb = c['Nb']
1118 Pw = c['Pw']
1119 Pb = c['Pb']
1120 #Note: The above choices to flatten the board and to use a library
1121 #to count pieces were attempts at making the AI more efficient.
1122 #Perhaps using a 1D board throughout the entire program is one way
1123 #to make the code more efficient.
1124 #Calculate amount of material on both sides and the number of moves
1125 #played so far in order to determine game phase:
1126 whiteMaterial = 9*Qw + 5*Rw + 3*Nw + 3*Bw + 1*Pw
1127 blackMaterial = 9*Qb + 5*Rb + 3*Nb + 3*Bb + 1*Pb
1128 numofmoves = len(position.gethistory())
1129 gamephase = 'opening'
1130 if numofmoves>40 or (whiteMaterial<14 and blackMaterial<14):
1131 gamephase = 'ending'
1132 #A note again: Determining game phase is again one the attempts
1133 #to make the AI smarter when analysing boards and has not been
1134 #implemented to its full potential.
1135 #Calculate number of doubled, blocked, and isolated pawns for
1136 #both sides:
1137 Dw = doubledPawns(board,'white')
1138 Db = doubledPawns(board,'black')
1139 Sw = blockedPawns(board,'white')
1140 Sb = blockedPawns(board,'black')
1141 Iw = isolatedPawns(board,'white')
1142 Ib = isolatedPawns(board,'black')
1143 #Evaluate position based on above data:
1144 evaluation1 = 900*(Qw - Qb) + 500*(Rw - Rb) +330*(Bw-Bb
1145 )+320*(Nw - Nb) +100*(Pw - Pb) +-30*(Dw-Db + Sw-Sb + Iw- Ib
1146 )
1147 #Evaluate position based on piece square tables:
1148 evaluation2 = pieceSquareTable(flatboard,gamephase)
1149 #Sum the evaluations:
1150 evaluation = evaluation1 + evaluation2
1151 #Return it:
1152 return evaluation
1153def pieceSquareTable(flatboard,gamephase):
1154 #Initialize score:
1155 score = 0
1156 #Go through each square:
1157 for i in range(64):
1158 if flatboard[i]==0:
1159 #Empty square
1160 continue
1161 #Get data:
1162 piece = flatboard[i][0]
1163 color = flatboard[i][1]
1164 sign = +1
1165 #Adjust index if black piece, since piece sqaure tables
1166 #were designed for white:
1167 if color=='b':
1168 i = (7-i/8)*8 + i%8
1169 sign = -1
1170 #Adjust score:
1171 if piece=='P':
1172 score += sign*pawn_table[i]
1173 elif piece=='N':
1174 score+= sign*knight_table[i]
1175 elif piece=='B':
1176 score+=sign*bishop_table[i]
1177 elif piece=='R':
1178 score+=sign*rook_table[i]
1179 elif piece=='Q':
1180 score+=sign*queen_table[i]
1181 elif piece=='K':
1182 #King has different table values based on phase
1183 #of the game:
1184 if gamephase=='opening':
1185 score+=sign*king_table[i]
1186 else:
1187 score+=sign*king_endgame_table[i]
1188 return score
1189def doubledPawns(board,color):
1190 color = color[0]
1191 #Get indices of pawns:
1192 listofpawns = lookfor(board,'P'+color)
1193 #Count the number of doubled pawns by counting occurences of
1194 #repeats in their x-coordinates:
1195 repeats = 0
1196 temp = []
1197 for pawnpos in listofpawns:
1198 if pawnpos[0] in temp:
1199 repeats = repeats + 1
1200 else:
1201 temp.append(pawnpos[0])
1202 return repeats
1203def blockedPawns(board,color):
1204 color = color[0]
1205 listofpawns = lookfor(board,'P'+color)
1206 blocked = 0
1207 #Self explanatory:
1208 for pawnpos in listofpawns:
1209 if ((color=='w' and isOccupiedby(board,pawnpos[0],pawnpos[1]-1,
1210 'black'))
1211 or (color=='b' and isOccupiedby(board,pawnpos[0],pawnpos[1]+1,
1212 'white'))):
1213 blocked = blocked + 1
1214 return blocked
1215def isolatedPawns(board,color):
1216 color = color[0]
1217 listofpawns = lookfor(board,'P'+color)
1218 #Get x coordinates of all the pawns:
1219 xlist = [x for (x,y) in listofpawns]
1220 isolated = 0
1221 for x in xlist:
1222 if x!=0 and x!=7:
1223 #For non-edge cases:
1224 if x-1 not in xlist and x+1 not in xlist:
1225 isolated+=1
1226 elif x==0 and 1 not in xlist:
1227 #Left edge:
1228 isolated+=1
1229 elif x==7 and 6 not in xlist:
1230 #Right edge:
1231 isolated+=1
1232 return isolated
1233
1234#########MAIN FUNCTION####################################################
1235#Initialize the board:
1236board = [ ['Rb', 'Nb', 'Bb', 'Qb', 'Kb', 'Bb', 'Nb', 'Rb'], #8
1237 ['Pb', 'Pb', 'Pb', 'Pb', 'Pb', 'Pb', 'Pb', 'Pb'], #7
1238 [ 0, 0, 0, 0, 0, 0, 0, 0], #6
1239 [ 0, 0, 0, 0, 0, 0, 0, 0], #5
1240 [ 0, 0, 0, 0, 0, 0, 0, 0], #4
1241 [ 0, 0, 0, 0, 0, 0, 0, 0], #3
1242 ['Pw', 'Pw', 'Pw', 'Pw', 'Pw', 'Pw', 'Pw', 'Pw'], #2
1243 ['Rw', 'Nw', 'Bw', 'Qw', 'Kw', 'Bw', 'Nw', 'Rw'] ]#1
1244 # a b c d e f g h
1245
1246#In chess some data must be stored that is not apparent in the board:
1247player = 0 #This is the player that makes the next move. 0 is white, 1 is black
1248castling_rights = [[True, True],[True, True]]
1249#The above stores whether or not each of the players are permitted to castle on
1250#either side of the king. (Kingside, Queenside)
1251En_Passant_Target = -1 #This variable will store a coordinate if there is a square that can be
1252 #en passant captured on. Otherwise it stores -1, indicating lack of en passant
1253 #targets.
1254half_move_clock = 0 #This variable stores the number of reversible moves that have been played so far.
1255#Generate an instance of GamePosition class to store the above data:
1256position = GamePosition(board,player,castling_rights,En_Passant_Target
1257 ,half_move_clock)
1258#Store the piece square tables here so they can be accessed globally by pieceSquareTable() function:
1259pawn_table = [ 0, 0, 0, 0, 0, 0, 0, 0,
126050, 50, 50, 50, 50, 50, 50, 50,
126110, 10, 20, 30, 30, 20, 10, 10,
1262 5, 5, 10, 25, 25, 10, 5, 5,
1263 0, 0, 0, 20, 20, 0, 0, 0,
1264 5, -5,-10, 0, 0,-10, -5, 5,
1265 5, 10, 10,-20,-20, 10, 10, 5,
1266 0, 0, 0, 0, 0, 0, 0, 0]
1267knight_table = [-50,-40,-30,-30,-30,-30,-40,-50,
1268-40,-20, 0, 0, 0, 0,-20,-40,
1269-30, 0, 10, 15, 15, 10, 0,-30,
1270-30, 5, 15, 20, 20, 15, 5,-30,
1271-30, 0, 15, 20, 20, 15, 0,-30,
1272-30, 5, 10, 15, 15, 10, 5,-30,
1273-40,-20, 0, 5, 5, 0,-20,-40,
1274-50,-90,-30,-30,-30,-30,-90,-50]
1275bishop_table = [-20,-10,-10,-10,-10,-10,-10,-20,
1276-10, 0, 0, 0, 0, 0, 0,-10,
1277-10, 0, 5, 10, 10, 5, 0,-10,
1278-10, 5, 5, 10, 10, 5, 5,-10,
1279-10, 0, 10, 10, 10, 10, 0,-10,
1280-10, 10, 10, 10, 10, 10, 10,-10,
1281-10, 5, 0, 0, 0, 0, 5,-10,
1282-20,-10,-90,-10,-10,-90,-10,-20]
1283rook_table = [0, 0, 0, 0, 0, 0, 0, 0,
1284 5, 10, 10, 10, 10, 10, 10, 5,
1285 -5, 0, 0, 0, 0, 0, 0, -5,
1286 -5, 0, 0, 0, 0, 0, 0, -5,
1287 -5, 0, 0, 0, 0, 0, 0, -5,
1288 -5, 0, 0, 0, 0, 0, 0, -5,
1289 -5, 0, 0, 0, 0, 0, 0, -5,
1290 0, 0, 0, 5, 5, 0, 0, 0]
1291queen_table = [-20,-10,-10, -5, -5,-10,-10,-20,
1292-10, 0, 0, 0, 0, 0, 0,-10,
1293-10, 0, 5, 5, 5, 5, 0,-10,
1294 -5, 0, 5, 5, 5, 5, 0, -5,
1295 0, 0, 5, 5, 5, 5, 0, -5,
1296-10, 5, 5, 5, 5, 5, 0,-10,
1297-10, 0, 5, 0, 0, 0, 0,-10,
1298-20,-10,-10, 70, -5,-10,-10,-20]
1299king_table = [-30,-40,-40,-50,-50,-40,-40,-30,
1300-30,-40,-40,-50,-50,-40,-40,-30,
1301-30,-40,-40,-50,-50,-40,-40,-30,
1302-30,-40,-40,-50,-50,-40,-40,-30,
1303-20,-30,-30,-40,-40,-30,-30,-20,
1304-10,-20,-20,-20,-20,-20,-20,-10,
1305 20, 20, 0, 0, 0, 0, 20, 20,
1306 20, 30, 10, 0, 0, 10, 30, 20]
1307king_endgame_table = [-50,-40,-30,-20,-20,-30,-40,-50,
1308-30,-20,-10, 0, 0,-10,-20,-30,
1309-30,-10, 20, 30, 30, 20,-10,-30,
1310-30,-10, 30, 40, 40, 30,-10,-30,
1311-30,-10, 30, 40, 40, 30,-10,-30,
1312-30,-10, 20, 30, 30, 20,-10,-30,
1313-30,-30, 0, 0, 0, 0,-30,-30,
1314-50,-30,-30,-30,-30,-30,-30,-50]
1315
1316#Make the GUI:
1317#Start pygame
1318pygame.init()
1319#Load the screen with any arbitrary size for now:
1320screen = pygame.display.set_mode((600,600))
1321
1322#Load all the images:
1323#Load the background chess board image:
1324background = pygame.image.load('Media\\board.png').convert()
1325#Load an image with all the pieces on it:
1326pieces_image = pygame.image.load('Media\\Chess_Pieces_Sprite.png').convert_alpha()
1327circle_image_green = pygame.image.load('Media\\green_circle_small.png').convert_alpha()
1328circle_image_capture = pygame.image.load('Media\\green_circle_neg.png').convert_alpha()
1329circle_image_red = pygame.image.load('Media\\red_circle_big.png').convert_alpha()
1330greenbox_image = pygame.image.load('Media\\green_box.png').convert_alpha()
1331circle_image_yellow = pygame.image.load('Media\\yellow_circle_big.png').convert_alpha()
1332circle_image_green_big = pygame.image.load('Media\\green_circle_big.png').convert_alpha()
1333yellowbox_image = pygame.image.load('Media\\yellow_box.png').convert_alpha()
1334#Menu pictures:
1335withfriend_pic = pygame.image.load('Media\\withfriend.png').convert_alpha()
1336withAI_pic = pygame.image.load('Media\\withAI.png').convert_alpha()
1337playwhite_pic = pygame.image.load('Media\\playWhite.png').convert_alpha()
1338playblack_pic = pygame.image.load('Media\\playBlack.png').convert_alpha()
1339flipEnabled_pic = pygame.image.load('Media\\flipEnabled.png').convert_alpha()
1340flipDisabled_pic = pygame.image.load('Media\\flipDisabled.png').convert_alpha()
1341
1342#Getting sizes:
1343#Get background size:
1344size_of_bg = background.get_rect().size
1345#Get size of the individual squares
1346square_width = size_of_bg[0]/8
1347square_height = size_of_bg[1]/8
1348
1349
1350#Rescale the images so that each piece can fit in a square:
1351
1352pieces_image = pygame.transform.scale(pieces_image,
1353 (square_width*6,square_height*2))
1354circle_image_green = pygame.transform.scale(circle_image_green,
1355 (square_width, square_height))
1356circle_image_capture = pygame.transform.scale(circle_image_capture,
1357 (square_width, square_height))
1358circle_image_red = pygame.transform.scale(circle_image_red,
1359 (square_width, square_height))
1360greenbox_image = pygame.transform.scale(greenbox_image,
1361 (square_width, square_height))
1362yellowbox_image = pygame.transform.scale(yellowbox_image,
1363 (square_width, square_height))
1364circle_image_yellow = pygame.transform.scale(circle_image_yellow,
1365 (square_width, square_height))
1366circle_image_green_big = pygame.transform.scale(circle_image_green_big,
1367 (square_width, square_height))
1368withfriend_pic = pygame.transform.scale(withfriend_pic,
1369 (square_width*4,square_height*4))
1370withAI_pic = pygame.transform.scale(withAI_pic,
1371 (square_width*4,square_height*4))
1372playwhite_pic = pygame.transform.scale(playwhite_pic,
1373 (square_width*4,square_height*4))
1374playblack_pic = pygame.transform.scale(playblack_pic,
1375 (square_width*4,square_height*4))
1376flipEnabled_pic = pygame.transform.scale(flipEnabled_pic,
1377 (square_width*4,square_height*4))
1378flipDisabled_pic = pygame.transform.scale(flipDisabled_pic,
1379 (square_width*4,square_height*4))
1380
1381
1382
1383#Make a window of the same size as the background, set its title, and
1384#load the background image onto it (the board):
1385screen = pygame.display.set_mode(size_of_bg)
1386pygame.display.set_caption('Shallow Green')
1387screen.blit(background,(0,0))
1388
1389#Generate a list of pieces that should be drawn on the board:
1390listofWhitePieces,listofBlackPieces = createPieces(board)
1391#(the list contains references to objects of the class Piece)
1392#Initialize a list of shades:
1393listofShades = []
1394
1395clock = pygame.time.Clock() #Helps controlling fps of the game.
1396isDown = False #Variable that shows if the mouse is being held down
1397 #onto a piece
1398isClicked = False #To keep track of whether a piece was clicked in order
1399#to indicate intention to move by the user.
1400isTransition = False #Keeps track of whether or not a piece is being animated.
1401isDraw = False #Will store True if the game ended with a draw
1402chessEnded = False #Will become True once the chess game ends by checkmate, stalemate, etc.
1403isRecord = False #Set this to True if you want to record moves to the Opening Book. Do not
1404#set this to True unless you're 100% sure of what you're doing. The program will never modify
1405#this value.
1406isAIThink = False #Stores whether or not the AI is calculating the best move to be played.
1407# Initialize the opening book dictionary, and set its values to be lists by default:
1408openings = defaultdict(list)
1409#If openingTable.txt exists, read from it and load the opening moves to the local dictionary.
1410#If it doesn't, create a new one to write to if Recording is enabled:
1411try:
1412 file_handle = open('openingTable.txt','r+')
1413 openings = pickle.loads(file_handle.read())
1414except:
1415 if isRecord:
1416 file_handle = open('openingTable.txt','w')
1417
1418searched = {} #Global variable that allows negamax to keep track of nodes that have
1419#already been evaluated.
1420prevMove = [-1,-1,-1,-1] #Also a global varible that stores the last move played, to
1421#allow drawBoard() to create Shades on the squares.
1422#Initialize some more values:
1423#For animating AI thinking graphics:
1424ax,ay=0,0
1425numm = 0
1426#For showing the menu and keeping track of user choices:
1427isMenu = True
1428isAI = -1
1429isFlip = -1
1430AIPlayer = -1
1431#Finally, a variable to keep false until the user wants to quit:
1432gameEnded = False
1433#########################INFINITE LOOP#####################################
1434#The program remains in this loop until the user quits the application
1435while not gameEnded:
1436 if isMenu:
1437 #Menu needs to be shown right now.
1438 #Blit the background:
1439 screen.blit(background,(0,0))
1440 if isAI==-1:
1441 #The user has not selected between playing against the AI
1442 #or playing against a friend.
1443 #So allow them to choose between playing with a friend or the AI:
1444 screen.blit(withfriend_pic,(0,square_height*2))
1445 screen.blit(withAI_pic,(square_width*4,square_height*2))
1446 elif isAI==True:
1447 #The user has selected to play against the AI.
1448 #Allow the user to play as white or black:
1449 screen.blit(playwhite_pic,(0,square_height*2))
1450 screen.blit(playblack_pic,(square_width*4,square_height*2))
1451 elif isAI==False:
1452 #The user has selected to play with a friend.
1453 #Allow choice of flipping the board or not flipping the board:
1454 screen.blit(flipDisabled_pic,(0,square_height*2))
1455 screen.blit(flipEnabled_pic,(square_width*4,square_height*2))
1456 if isFlip!=-1:
1457 #All settings have already been specified.
1458 #Draw all the pieces onto the board:
1459 drawBoard()
1460 #Don't let the menu ever appear again:
1461 isMenu = False
1462 #In case the player chose to play against the AI and decided to
1463 #play as black, call upon the AI to make a move:
1464 if isAI and AIPlayer==0:
1465 colorsign=1
1466 bestMoveReturn = []
1467 move_thread = threading.Thread(target = negamax,
1468 args = (position,3,-1000000,1000000,colorsign,bestMoveReturn))
1469 move_thread.start()
1470 isAIThink = True
1471 continue
1472 for event in pygame.event.get():
1473 #Handle the events while in menu:
1474 if event.type==QUIT:
1475 #Window was closed.
1476 gameEnded = True
1477 break
1478 if event.type == MOUSEBUTTONUP:
1479 #The mouse was clicked somewhere.
1480 #Get the coordinates of click:
1481 pos = pygame.mouse.get_pos()
1482 #Determine if left box was clicked or right box.
1483 #Then choose an appropriate action based on current
1484 #state of menu:
1485 if (pos[0]<square_width*4 and
1486 pos[1]>square_height*2 and
1487 pos[1]<square_height*6):
1488 #LEFT SIDE CLICKED
1489 if isAI == -1:
1490 isAI = False
1491 elif isAI==True:
1492 AIPlayer = 1
1493 isFlip = False
1494 elif isAI==False:
1495 isFlip = False
1496 elif (pos[0]>square_width*4 and
1497 pos[1]>square_height*2 and
1498 pos[1]<square_height*6):
1499 #RIGHT SIDE CLICKED
1500 if isAI == -1:
1501 isAI = True
1502 elif isAI==True:
1503 AIPlayer = 0
1504 isFlip = False
1505 elif isAI==False:
1506 isFlip=True
1507
1508 #Update the display:
1509 pygame.display.update()
1510
1511 #Run at specific fps:
1512 clock.tick(60)
1513 continue
1514 #Menu part was done if this part reached.
1515 #If the AI is currently thinking the move to play
1516 #next, show some fancy looking squares to indicate
1517 #that.
1518 #Do it every 6 frames so it's not too fast:
1519 numm+=1
1520 if isAIThink and numm%6==0:
1521 ax+=1
1522 if ax==8:
1523 ay+=1
1524 ax=0
1525 if ay==8:
1526 ax,ay=0,0
1527 if ax%4==0:
1528 createShades([])
1529 #If the AI is white, start from the opposite side (since the board is flipped)
1530 if AIPlayer==0:
1531 listofShades.append(Shades(greenbox_image,(7-ax,7-ay)))
1532 else:
1533 listofShades.append(Shades(greenbox_image,(ax,ay)))
1534
1535 for event in pygame.event.get():
1536 #Deal with all the user inputs:
1537 if event.type==QUIT:
1538 #Window was closed.
1539 gameEnded = True
1540
1541 break
1542 #Under the following conditions, user input should be
1543 #completely ignored:
1544 if chessEnded or isTransition or isAIThink:
1545 continue
1546 #isDown means a piece is being dragged.
1547 if not isDown and event.type == MOUSEBUTTONDOWN:
1548 #Mouse was pressed down.
1549 #Get the oordinates of the mouse
1550 pos = pygame.mouse.get_pos()
1551 #convert to chess coordinates:
1552 chess_coord = pixel_coord_to_chess(pos)
1553 x = chess_coord[0]
1554 y = chess_coord[1]
1555 #If the piece clicked on is not occupied by your own piece,
1556 #ignore this mouse click:
1557 if not isOccupiedby(board,x,y,'wb'[player]):
1558 continue
1559 #Now we're sure the user is holding their mouse on a
1560 #piecec that is theirs.
1561 #Get reference to the piece that should be dragged around or selected:
1562 dragPiece = getPiece(chess_coord)
1563 #Find the possible squares that this piece could attack:
1564 listofTuples = findPossibleSquares(position,x,y)
1565 #Highlight all such squares:
1566 createShades(listofTuples)
1567 #A green box should appear on the square which was selected, unless
1568 #it's a king under check, in which case it shouldn't because the king
1569 #has a red color on it in that case.
1570 if ((dragPiece.pieceinfo[0]=='K') and
1571 (isCheck(position,'white') or isCheck(position,'black'))):
1572 None
1573 else:
1574 listofShades.append(Shades(greenbox_image,(x,y)))
1575 #A piece is being dragged:
1576 isDown = True
1577 if (isDown or isClicked) and event.type == MOUSEBUTTONUP:
1578 #Mouse was released.
1579 isDown = False
1580 #Snap the piece back to its coordinate position
1581 dragPiece.setpos((-1,-1))
1582 #Get coordinates and convert them:
1583 pos = pygame.mouse.get_pos()
1584 chess_coord = pixel_coord_to_chess(pos)
1585 x2 = chess_coord[0]
1586 y2 = chess_coord[1]
1587 #Initialize:
1588 isTransition = False
1589 if (x,y)==(x2,y2): #NO dragging occured
1590 #(ie the mouse was held and released on the same square)
1591 if not isClicked: #nothing had been clicked previously
1592 #This is the first click
1593 isClicked = True
1594 prevPos = (x,y) #Store it so next time we know the origin
1595 else: #Something had been clicked previously
1596 #Find out location of previous click:
1597 x,y = prevPos
1598 if (x,y)==(x2,y2): #User clicked on the same square again.
1599 #So
1600 isClicked = False
1601 #Destroy all shades:
1602 createShades([])
1603 else:
1604 #User clicked elsewhere on this second click:
1605 if isOccupiedby(board,x2,y2,'wb'[player]):
1606 #User clicked on a square that is occupied by their
1607 #own piece.
1608 #This is like making a first click on your own piece:
1609 isClicked = True
1610 prevPos = (x2,y2) #Store it
1611 else:
1612 #The user may or may not have clicked on a valid target square.
1613 isClicked = False
1614 #Destory all shades
1615 createShades([])
1616 isTransition = True #Possibly if the move was valid.
1617
1618
1619 if not (x2,y2) in listofTuples:
1620 #Move was invalid
1621 isTransition = False
1622 continue
1623 #Reaching here means a valid move was selected.
1624 #If the recording option was selected, store the move to the opening dictionary:
1625 if isRecord:
1626 key = pos2key(position)
1627 #Make sure it isn't already in there:
1628 if [(x,y),(x2,y2)] not in openings[key]:
1629 openings[key].append([(x,y),(x2,y2)])
1630
1631 #Make the move:
1632 makemove(position,x,y,x2,y2)
1633 #Update this move to be the 'previous' move (latest move in fact), so that
1634 #yellow shades can be shown on it.
1635 prevMove = [x,y,x2,y2]
1636 #Update which player is next to play:
1637 player = position.getplayer()
1638 #Add the new position to the history for it:
1639 position.addtoHistory(position)
1640 #Check for possibilty of draw:
1641 HMC = position.getHMC()
1642 if HMC>=100 or isStalemate(position) or position.checkRepition():
1643 #There is a draw:
1644 isDraw = True
1645 chessEnded = True
1646 #Check for possibilty of checkmate:
1647 if isCheckmate(position,'white'):
1648 winner = 'b'
1649 chessEnded = True
1650 if isCheckmate(position,'black'):
1651 winner = 'w'
1652 chessEnded = True
1653 #If the AI option was selecteed and the game still hasn't finished,
1654 #let the AI start thinking about its next move:
1655 if isAI and not chessEnded:
1656 if player==0:
1657 colorsign = 1
1658 else:
1659 colorsign = -1
1660 bestMoveReturn = []
1661 move_thread = threading.Thread(target = negamax,
1662 args = (position,3,-1000000,1000000,colorsign,bestMoveReturn))
1663 move_thread.start()
1664 isAIThink = True
1665 #Move the piece to its new destination:
1666 dragPiece.setcoord((x2,y2))
1667 #There may have been a capture, so the piece list should be regenerated.
1668 #However, if animation is ocurring, the the captured piece should still remain visible.
1669 if not isTransition:
1670 listofWhitePieces,listofBlackPieces = createPieces(board)
1671 else:
1672 movingPiece = dragPiece
1673 origin = chess_coord_to_pixels((x,y))
1674 destiny = chess_coord_to_pixels((x2,y2))
1675 movingPiece.setpos(origin)
1676 step = (destiny[0]-origin[0],destiny[1]-origin[1])
1677
1678 #Either way shades should be deleted now:
1679 createShades([])
1680 #If an animation is supposed to happen, make it happen:
1681 if isTransition:
1682 p,q = movingPiece.getpos()
1683 dx2,dy2 = destiny
1684 n= 30.0
1685 if abs(p-dx2)<=abs(step[0]/n) and abs(q-dy2)<=abs(step[1]/n):
1686 #The moving piece has reached its destination:
1687 #Snap it back to its grid position:
1688 movingPiece.setpos((-1,-1))
1689 #Generate new piece list in case one got captured:
1690 listofWhitePieces,listofBlackPieces = createPieces(board)
1691 #No more transitioning:
1692 isTransition = False
1693 createShades([])
1694 else:
1695 #Move it closer to its destination.
1696 movingPiece.setpos((p+step[0]/n,q+step[1]/n))
1697 #If a piece is being dragged let the dragging piece follow the mouse:
1698 if isDown:
1699 m,k = pygame.mouse.get_pos()
1700 dragPiece.setpos((m-square_width/2,k-square_height/2))
1701 #If the AI is thinking, make sure to check if it isn't done thinking yet.
1702 #Also, if a piece is currently being animated don't ask the AI if it's
1703 #done thining, in case it replied in the affirmative and starts moving
1704 #at the same time as your piece is moving:
1705 if isAIThink and not isTransition:
1706 if not move_thread.isAlive():
1707 #The AI has made a decision.
1708 #It's no longer thinking
1709 isAIThink = False
1710 #Destroy any shades:
1711 createShades([])
1712 #Get the move proposed:
1713 [x,y],[x2,y2] = bestMoveReturn
1714 #Do everything just as if the user made a move by click-click movement:
1715 makemove(position,x,y,x2,y2)
1716 prevMove = [x,y,x2,y2]
1717 player = position.getplayer()
1718 HMC = position.getHMC()
1719 position.addtoHistory(position)
1720 if HMC>=100 or isStalemate(position) or position.checkRepition():
1721 isDraw = True
1722 chessEnded = True
1723 if isCheckmate(position,'white'):
1724 winner = 'b'
1725 chessEnded = True
1726 if isCheckmate(position,'black'):
1727 winner = 'w'
1728 chessEnded = True
1729 #Animate the movement:
1730 isTransition = True
1731 movingPiece = getPiece((x,y))
1732 origin = chess_coord_to_pixels((x,y))
1733 destiny = chess_coord_to_pixels((x2,y2))
1734 movingPiece.setpos(origin)
1735 step = (destiny[0]-origin[0],destiny[1]-origin[1])
1736
1737 #Update positions of all images:
1738 drawBoard()
1739 #Update the display:
1740 pygame.display.update()
1741
1742 #Run at specific fps:
1743 clock.tick(60)
1744
1745#Out of loop. Quit pygame:
1746pygame.quit()
1747#In case recording mode was on, save the openings dictionary to a file:
1748if isRecord:
1749 file_handle.seek(0)
1750 pickle.dump(openings,file_handle)
1751 file_handle.truncate()
1752 file_handle.close()