2
\$\begingroup\$

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 ?

\$\endgroup\$
3
  • 4
    \$\begingroup\$ Python2 has reached its end of life. It's recommended to use Python3. \$\endgroup\$
    – Linny
    Commented Jul 18, 2020 at 3:37
  • \$\begingroup\$ Ok, TY. I think that the print should be the only thing that changes in the particular case of the codes above. \$\endgroup\$
    – 3sm1r
    Commented Jul 18, 2020 at 3:43
  • \$\begingroup\$ There are web sites that go into detail about programming chess games. Here is a page on using bitboards, 64-bit values, to represent boards, pieces, moves, etc \$\endgroup\$
    – RootTwo
    Commented Jul 18, 2020 at 23:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.