I will describe two techniques, then the question will be how I can make an algorithm that is more efficient, if possible.
I want to find an efficient way to determine the squares where the pieces on a chess board can go. I want to start with a simple case, and just find the square where two rooks could move in an otherwise empty board. The two rooks are assumed to be "transparent" to one another, since the conditions for the interaction with other pieces will be added at a later stage.
The boards are represented by a collection of 64
-components boolean numpy.array
.
I start by creating the the board with the two rooks, assumed to be in position 15
and 25
on the 1-D board:
import numpy as np
import time
r_pos=np.zeros(64, dtype=bool)
r_pos[15] = True
r_pos[25] = True
Now I show the first method, which simply consist in setting to True
the squares available making the rows and the columns separately. It can be shown that for this method the simulation time required increases with the number of pieces.
t1=time.time()
attack_r=np.zeros(64, dtype=bool)
for piece in np.where(r_pos)[0]:
attack_r[8 * (piece // 8):8 * (piece // 8 + 1)] = True
attack_r[piece % 8::8] = True
t2=time.time()
print t2-t1
print attack_a
To better visualize the board we can create a function that converts the 1-D array in the 2-D matrix:
def from_array_to_matrix(v):
m=np.zeros((8,8)).astype('int')
for row in range(8):
for column in range(8):
m[row,column]=v[row*8+column]
return m
and thus we can check that we obtained the desired output:
print from_array_to_matrix(attack_r)
The second method creates a certain number of static boards as a template for the moves, and then uses boolean operators to select the proper template on the basis of the rook positions. It is slower, but it has the nice advantage that the simulation time does not depend on the number of pieces:
# create the collection of possible rook
# moves (just all the columns and all
# the rows in separate matrices)
m_rook=np.zeros((16,64), dtype=bool)
for line in range(8):
m_rook[line,line*8:(line+1)*8]=True
col=0
for line in range(8,16):
m_rook[line, col % 8::8]=True
col+=1
% then we use the template to find the available moves
t1=time.time()
attack_r= np.any(m_rook[np.any(np.logical_and(r_pos, m_rook), axis=1)], axis=0)
t2=time.time()
print t2-t1
print from_array_to_matrix(attack_r)
I feel that it should be possible to use some technique that is even faster. Is it possible that using numpy
arrays is actually not the best way to go ?
print
should be the only thing that changes in the particular case of the codes above. \$\endgroup\$