我正在用Python编写一个国际象棋程序,需要生成马的所有动作。对于那些不熟悉国际象棋的人来说,马的移动是 L 形的。
因此,给定
(2, 4)
的位置,骑士可以移动到 (0, 3)
、(0, 5)
、(1, 2)
、(3, 2
)等,总共(最多)八种不同的移动。
我想编写一个名为
knight_moves
的函数来在列表中生成这些元组。在 Python 中执行此操作最简单的方法是什么?
def knight_moves(position):
''' Returns a list of new positions given a knight's current position. '''
pass
好的,感谢 Niall Byrne,我想出了这个:
from itertools import product
def knight_moves(position):
x, y = position
moves = list(product([x-1, x+1],[y-2, y+2])) + list(product([x-2,x+2],[y-1,y+1]))
moves = [(x,y) for x,y in moves if x >= 0 and y >= 0 and x < 8 and y < 8]
return moves
为什么不存储它可以移动的相对对?因此,以你的起点为基础,添加一组可能的移动远离它,然后你只需要进行健全性检查以确保它们仍然在界限内,或者不在另一块上。
即给定您的 (2, 4) 起点,选项为 (-2,-1), (-2,+1), (-1,+2), (+2,+1) 因此,相对位置将始终相同。
def knight_moves(position):
deltas = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
valid_position = lambda x: (8 >= x[0] >= 1) and (8 >= x[1] >= 1)
map_output = map(lambda x: (position[0] + x[0], position[1] + x[1]), deltas)
return list(filter(valid_position, map_output))
我建议您使用位板,而不是使用数组。它们不仅非常容易操作,而且还减少了边界检查的需要。只需 12 个位板,您就可以对整个游戏所需的信息进行编码。
https://www.chessprogramming.org/Bitboards
位板的基本思想是使用 64 位整数,如果位上存在棋子则设置为 1。例如,如果你有一个 64 位整数来代表白骑士,你可以在游戏开始时设置第 2 位和第 6 位,因为它们是白骑士所在的位置。使用这种符号,可以很容易地计算出骑士的动作。计算其他棋子的动作也很容易。
通过这种表示,您可以查看国际象棋引擎的链接,以获取现成的算法来实现骑士的动作。
http://www.mayothi.com/nagaskakichess6.html
如果您不熟悉解析几何(或复数几何),这可能听起来有点矫枉过正,但我想出了一个非常优雅的数学解决方案 我正在对棋子的移动进行验证。
马的动作位于一个圆上,可以定义为 (x-x_0)^2+(y-y_0)^2=5 其中 x_0 和 y_0 是骑士的当前坐标。如果切换到极坐标,您可以使用这个简单的代码获得所有可能的坐标:
import math
def knight_moves(x,y):
new_positions=[]
r=math.sqrt(5) #radius of the circle
for phi in [math.atan(2),math.atan(1/2)]: #angles in radians
for quadrant in range(4):
angle=phi+quadrant*math.pi/2 # add 0, 90, 180, 270 degrees in radians
new_x=round(x+r*math.cos(angle))
new_y=round(y+r*math.sin(angle))
if max(new_x,new_y,7-new_x,7-new_y)<=7: #validation whether the move is in grid
new_positions.append([new_x,new_y])
return(new_positions)
def validate_knight_move(x,y,x_0,y_0):
return((x-x_0)**2+(y-y_0)**2==5)
x_0=2
y_0=4
moves=knight_moves(x_0,y_0)
print(moves)
validation=[validate_knight_move(move[0],move[1],x_0,y_0) for move in moves]
print(validation)
[[3, 6], [0, 5], [1, 2], [4, 3], [4, 5], [1, 6], [0, 3], [3, 2]]
[True, True, True, True, True, True, True, True]
这里需要指出的是,验证仓位比直接构建仓位要简单得多。因此,尝试一下所有可能的移动是否都在圆上可能是个好主意:
def knight_moves2(x,y):
new_positions=[]
for dx in [-2,-1,1,2]:
for dy in [-2,-1,1,2]:
if(validate_knight_move(x+dx,y+dy,x,y)): #is knight move?
if max(x+dx,y+dy,7-(x+dx),7-(y+dy))<=7: #validation whether the move is in grid
new_positions.append([x+dx,y+dy])
return(new_positions)
new_positions=knight_moves2(x_0,y_0)
print(new_positions)
[[0, 3], [0, 5], [1, 2], [1, 6], [3, 2], [3, 6], [4, 3], [4, 5]]
这是一个简单的实现:
def knights_moves():
a = []
b = (1, 2)
while 1:
a.append(b)
b = (-b[0], b[1])
a.append(b)
b = (b[1], b[0])
if b in a:
return a
[(1, 2), (-1, 2), (2, -1), (-2, -1), (-1, -2), (1, -2), (-2, 1), (2, 1)]
从那里您可以简单地将当前位置添加到此列表的每个成员,然后仔细检查有效性。
完成小猫的回答,
possible_places = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
def knight_moves(cur_pos):
onboard = lambda (x, y): x >= 0 and y >= 0 and x<8 and y<8
eval_move = lambda(x,y): (cur_pos[0] + x, cur_pos[1] + y)
return filter(onboard, map(eval_move, possible_places))
对于骑士的动作:
def getAllValidMoves(x0, y0):
deltas = [(-2, -1), (-2, +1), (+2, -1), (+2, +1), (-1, -2), (-1, +2), (+1, -2), (+1, +2)]
validPositions = []
for (x, y) in deltas:
xCandidate = x0 + x
yCandidate = y0 + y
if 0 < xCandidate < 8 and 0 < yCandidate < 8:
validPositions.append([xCandidate, yCandidate])
return validPositions
print getAllValidMoves(3,3)
我只是存储了所有可能的增量,将它们中的每一个应用到“初始位置”并保存了棋盘内的增量
from itertools import product
def moves():
""" The available (relative) moves"""
a = list(product( (1, -1), (2,-2)))
return a + [tuple(reversed(m)) for m in a]
def neighbors(a,b):
# true if x,y belongs in a chess table
in_table = lambda (x, y): all((x < 8, y < 8, x >= 0, y >= 0))
# returns the possible moving positions
return filter(in_table, [(a+x, b+y) for x, y in moves()])
“邻居”是骑士可以从 a,b 出发的可用位置
下面的方法是用python实现的。它接受棋盘(可以是任何 m*n 且值为 0(可用)和 1(占用)以及骑士的当前位置)
def get_knight_moves(board, position):
KNIGHT_STEPS = ((1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1))
knight_moves = []
for (i, j) in KNIGHT_STEPS:
try:
x, y = position[0] + i, position[1] + j
if board[x][y] == 0:
knight_moves.append((x, y))
except IndexError:
pass
print(knight_moves)