I'm writing a chess engine, and am trying to make it as fast as possible, so I'm using bitboards to represent each type of piece. I was printing out the number of different board states at each plie (Plie = 1 person moving) and on plie 4 it gets the wrong number.
Is there any way to figure out what is going wrong without sifting through all 200k 4 plie positions?
Also, note I haven't implemented castling, check, en passent, pawn promotion or any draw rules yet, as none of them should have any affect until after the 4th plie.
(Wikipedia link that gives the number of board states per plie, vs mine: 20, 400, 8902, 197742)
import json
with open('White_Pawn.json', 'r') as f:
white_pawn_table = json.load(f)
white_pawn_table = {int(q):w for q, w in white_pawn_table.items()}
with open('White_Pawn_Captures.json', 'r') as f:
white_pawn_captures_table = json.load(f)
white_pawn_captures_table = {int(q):w for q, w in white_pawn_captures_table.items()}
with open('Black_Pawn.json', 'r') as f:
black_pawn_table = json.load(f)
black_pawn_table = {int(q):w for q, w in black_pawn_table.items()}
with open('Black_Pawn_Captures.json', 'r') as f:
black_pawn_captures_table = json.load(f)
black_pawn_captures_table = {int(q):w for q, w in black_pawn_captures_table.items()}
with open('Knight.json', 'r') as f:
knight_table = json.load(f)
knight_table = {int(q):w for q, w in knight_table.items()}
with open('Bishop.json', 'r') as f:
bishop_table = json.load(f)
bishop_table = {int(q):w for q, w in bishop_table.items()}
with open('Rook.json', 'r') as f:
rook_table = json.load(f)
rook_table = {int(q):w for q, w in rook_table.items()}
string_to_int = lambda x:int(x, 2)
int_to_string = lambda x:'0' * (66 - len(bin(x))) + bin(x)[2:]
x_in_y = lambda x, y:(x & y) != 0
def show(x):
for q in range(8):
print(' '.join([w for w in x[(q * 8):((q + 1) * 8)]]))
print()
class Board:
def __init__(self, args = False):
if args:
self.maps, self.turn = args
else:
self.maps, self.turn = {'White Pawns':65280, 'White Knights':66, 'White Bishops':36, 'White Rooks':129, 'White Queens':16, 'White Kings':8, 'Black Pawns':71776119061217280, 'Black Knights':4755801206503243776, 'Black Bishops':2594073385365405696, 'Black Rooks':9295429630892703744, 'Black Queens':1152921504606846976, 'Black Kings':576460752303423488}, 1
def move(self, colour, not_colour, piece, move):
board = Board(args = (self.maps.copy(), not self.turn))
board.maps[f'{colour} {piece}s'] ^= move[0]
board.maps[f'{colour} {piece}s'] |= move[1]
for q in board.maps:
if not_colour in q:
board.maps[q] &= ~move[1]
return board
def moves(self):
# Get Pieces and Colours
colour, not_colour = ['White', 'Black'][::self.turn if self.turn else -1]
pieces, not_pieces = 0, 0
for q, w in self.maps.items():
if colour in q:
pieces |= w
else:
not_pieces |= w
# Pawn
if colour == 'White':
move_table, capture_table = white_pawn_table, white_pawn_captures_table
else:
move_table, capture_table = black_pawn_table, black_pawn_captures_table
temp_pawns = self.maps[f'{colour} Pawns']
while temp_pawns:
pawn = temp_pawns & -temp_pawns
temp_pawns ^= pawn
for next_pawn in move_table[pawn]:
if x_in_y(next_pawn, pieces | not_pieces):
break
else:
yield self.move(colour, not_colour, 'Pawn', (pawn, next_pawn))
for next_pawn in capture_table[pawn]:
if x_in_y(next_pawn, not_pieces):
yield self.move(colour, not_colour, 'Pawn', (pawn, next_pawn))
# Knight
temp_knights = self.maps[f'{colour} Knights']
while temp_knights:
knight = temp_knights & -temp_knights
temp_knights ^= knight
for next_knight in knight_table[knight]:
if not x_in_y(next_knight, pieces):
yield self.move(colour, not_colour, 'Knight', (knight, next_knight))
# Bishop
temp_bishops = self.maps[f'{colour} Bishops']
while temp_bishops:
bishop = temp_bishops & -temp_bishops
temp_bishops ^= bishop
for direction in bishop_table[bishop]:
for next_bishop in direction:
if x_in_y(next_bishop, pieces): break
yield self.move(colour, not_colour, 'Bishop', (bishop, next_bishop))
if x_in_y(next_bishop, not_pieces): break
# Rook
temp_rooks = self.maps[f'{colour} Rooks']
while temp_rooks:
rook = temp_rooks & -temp_rooks
temp_rooks ^= rook
for direction in rook_table[rook]:
for next_rook in direction:
if x_in_y(next_rook, pieces): break
yield self.move(colour, not_colour, 'Rook', (rook, next_rook))
if x_in_y(next_rook, not_pieces): break
# Queen
temp_queens = self.maps[f'{colour} Queens']
while temp_queens:
queen = temp_queens & -temp_queens
temp_queens ^= queen
for direction in rook_table[queen]:
for next_queen in direction:
if x_in_y(next_queen, pieces): break
yield self.move(colour, not_colour, 'Queen', (queen, next_queen))
if x_in_y(next_queen, not_pieces): break
for direction in bishop_table[queen]:
for next_queen in direction:
if x_in_y(next_queen, pieces): break
yield self.move(colour, not_colour, 'Queen', (queen, next_queen))
if x_in_y(next_queen, not_pieces): break
# King
king = self.maps[f'{colour} Kings']
for direction in rook_table[king]:
next_king = direction[0]
if not x_in_y(next_king, pieces):
yield self.move(colour, not_colour, 'King', (king , next_king))
for direction in bishop_table[king]:
next_king = direction[0]
if not x_in_y(next_king, pieces):
yield self.move(colour, not_colour, 'King', (king, next_king))
def next_states(self):
for q in self.moves():
yield q
def __str__(self):
find = {'Black Kings':'♔ ', 'Black Queens':'♕ ', 'Black Rooks':'♖ ', 'Black Bishops':'♗ ', 'Black Knights':'♘ ', 'Black Pawns':'♙ ', 'White Pawns':'♟ ', 'White Knights':'♞ ', 'White Bishops':'♝ ', 'White Rooks':'♜ ', 'White Queens':'♛ ', 'White Kings':'♚ '}
map = lambda y:([q for q in self.maps if self.maps[q] & (2**y)] + [False])[0]
output = ' A B C D E F G H\n ╔════╤════╤════╤════╤════╤════╤════╤════╗\n'
for q in range(8):
if q % 2 == 0:
output += '%i ║ %s │░%s░│ %s │░%s░│ %s │░%s░│ %s │░%s░║ %i\n ╟────┼────┼────┼────┼────┼────┼────┼────╢\n' % tuple([8 - q] + [find[map(q * 8 + w)] if map(q * 8 + w) else ' ' if w % 2 == 0 else '░░' for w in range(8)] + [8 - q])
else:
output += '%i ║░%s░│ %s │░%s░│ %s │░%s░│ %s │░%s░│ %s ║ %i\n ╟────┼────┼────┼────┼────┼────┼────┼────╢\n' % tuple([8 - q] + [find[map(q * 8 + w)] if map(q * 8 + w) else '░░' if w % 2 == 0 else ' ' for w in range(8)] + [8 - q])
output += '\x1b[1A\x1b[2K' + ' ╚════╧════╧════╧════╧════╧════╧════╧════╝\n A B C D E F G H'
return output
chess = Board()
next_states = [chess]
while True:
current_states, next_states = next_states, []
for state in current_states:
for next_state in state.next_states():
next_states.append(next_state)
print(len(next_states))
The json files are too large to put here but you can assume they're correct. Each file has a dictionary with keys 2^0-2^63 each representing a possible position for the piece the file is named after. The values are the different positions they can go from there.
