Saat ini saya sedang mengerjakan mesin catur, yang sejauh ini bekerja tetapi membutuhkan waktu lama untuk menghasilkan gerakan. Deteksi pemeriksaan memakan waktu paling lama karena banyak gerakan yang harus dihasilkan.

Saya terjebak setelah mencoba banyak hal dan tidak dapat menemukan cara untuk membuatnya lebih efisien. Inilah cara saya melakukannya:

Untuk memeriksa apakah suatu langkah diperbolehkan/legal, saya periksa, apakah pihak yang melakukan langkah itu dicentang sesudahnya:

    def allowed_move(self, board, pos, move, colour):

    copy_board = copy.deepcopy(board)

    (x, y) = pos
    (new_x, new_y) = move

    if copy_board[x][y] == "k_w":
        self.white_king = (new_x, new_y)
        copy_board[new_x][new_y] = copy_board[x][y]
        copy_board[x][y] = " "
        self.in_check(colour, copy_board)
        self.white_king = (x, y)

    elif copy_board[x][y] == "k_b":
        self.black_king = (new_x, new_y)
        copy_board[new_x][new_y] = copy_board[x][y]
        copy_board[x][y] = " "
        self.in_check(colour, copy_board)
        self.black_king = (x, y)

    else:
        copy_board[new_x][new_y] = copy_board[x][y]
        copy_board[x][y] = " "
        self.in_check(colour, copy_board)


    if colour == "_w" and self.white_check:
        return False

    if colour == "_b" and self.black_check:
        return False

    return True

Untuk menentukan apakah ada sisi yang diperiksa, saya membuat setiap gerakan dari sisi lawan dan memeriksa apakah mereka dapat menangkap raja pada langkah berikutnya. (Ini adalah bagian yang buruk)

  • sq[1:] hanya menentukan warna kotak saat ini

  • diri.(warna).king adalah posisi raja saat ini

  • move adalah tupel yang berisi koordinat kuadrat ujung setiap gerakan

     def in_check(self, colour, board):
    
     self.white_check = False
     self.black_check = False
     for x, line in enumerate(board):
         for y, sq in enumerate(line):
             if sq[1:] == "_w":
                 for (move, _, _) in self.get_all_moves(board, (x, y)):
                     if move == self.black_king:
                         self.black_check = True
    
             if sq[1:] == "_b":
                 for (move, _, _) in self.get_all_moves(board, (x, y)):
                     if move == self.white_king:
                         self.white_check = True
    

Sejauh ini, ini adalah operasi paling mahal di mesin saya dan saya ingin tahu apakah saya bisa menyederhanakannya. Pseudo-legal-moves dihitung menggunakan file ini, bagi siapa saja yang tertarik. Untuk menyelesaikan semua gerakan, en-passant, casting, dan promosi dihasilkan secara terpisah. Saya juga membuat daftar kemungkinan, gerakan legal per sisi setelah setiap gerakan yang dieksekusi, tetapi karena deteksi pemeriksaan menggunakan gerakan potensial, daftar itu tidak dapat digunakan.

    class Rook:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos

    def moves(self):
        pos_caps = []
        (x, y) = self.pos
        clr = self.board[x][y][1:]
        for i in range(- 1, - y - 1, -1):
            if self.board[x][y + i][1:] != clr:  
                pos_caps.append((x, y + i))
                for v in range(- 1, i, - 1):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(1, 8 - y):
            if self.board[x][y + i][1:] != clr:  
                pos_caps.append((x, y + i))
                for v in range(1, i):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(- 1, - x - 1, -1):
            if self.board[x + i][y][1:] != clr:  
                pos_caps.append((x + i, y))
                for v in range(- 1, i, - 1):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        for i in range(1, 8 - x):
            if self.board[x + i][y][1:] != clr:  
                pos_caps.append((x + i, y))
                for v in range(1, i):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        return pos_caps


class Knight:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = self.board[self.x_pos][self.y_pos][1:]

    def moves(self):
        pos_moves = []
        (x, y) = self.pos
        if x < 6 and y < 7:
            pos_moves.append((x + 2, y + 1))
        if x < 6 and y > 0:
            pos_moves.append((x + 2, y - 1))
        if x > 1 and y < 7:
            pos_moves.append((x - 2, y + 1))
        if x > 1 and y > 0:
            pos_moves.append((x - 2, y - 1))
        if x < 7 and y < 6:
            pos_moves.append((x + 1, y + 2))
        if x < 7 and y > 1:
            pos_moves.append((x + 1, y - 2))
        if x > 0 and y < 6:
            pos_moves.append((x - 1, y + 2))
        if x > 0 and y > 1:
            pos_moves.append((x - 1, y - 2))
            
        for mv in reversed(pos_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                pos_moves.remove(mv)

        return pos_moves


class King:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = self.board[self.x_pos][self.y_pos][1:]

    def moves(self):
        all_moves = []
        (x, y) = self.pos
        if x > 0:
            all_moves.append((x - 1, y))
            if y > 0:
                all_moves.append((x - 1, y - 1))
            if y < 7:
                all_moves.append((x - 1, y + 1))

        if x < 7:
            all_moves.append((x + 1, y))
            if y > 0:
                all_moves.append((x + 1, y - 1))
            if y < 7:
                all_moves.append((x + 1, y + 1))

        if y > 0:
            all_moves.append((x, y - 1))

        if y < 7:
            all_moves.append((x, y + 1))

        for mv in reversed(all_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                all_moves.remove(mv)

        return all_moves


class Queen:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = self.board[self.x_pos][self.y_pos][1:]

    def moves(self):
        pos_caps = []
        (x, y) = self.pos
        clr = self.board[x][y][1:]
        for i in range(- 1, - y - 1, -1):
            if self.board[x][y + i][1:] != clr:   
                pos_caps.append((x, y + i))
                for v in range(- 1, i, - 1):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(1, 8 - y):
            if self.board[x][y + i][1:] != clr:   
                pos_caps.append((x, y + i))
                for v in range(1, i):
                    if self.board[x][y + v] != " ":
                        pos_caps.remove((x, y + i))
                        break

        for i in range(- 1, - x - 1, -1):
            if self.board[x + i][y][1:] != clr:   
                pos_caps.append((x + i, y))
                for v in range(- 1, i, - 1):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        for i in range(1, 8 - x):
            if self.board[x + i][y][1:] != clr:  
                pos_caps.append((x + i, y))
                for v in range(1, i):
                    if self.board[x + v][y] != " ":
                        pos_caps.remove((x + i, y))
                        break

        com = min(x, y)
        for i in range(1, com + 1):
            if self.board[x - i][y - i][1:] != clr:
                pos_caps.append((x - i, y - i))
                for v in range(1, i):
                    if self.board[x - v][y - v] != " ":
                        pos_caps.remove((x - i, y - i))
                        break

        com = min(7 - x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x + i][y + i][1:] != clr:
                pos_caps.append((x + i, y + i))
                for v in range(1, i):
                    if self.board[x + v][y + v] != " ":
                        pos_caps.remove((x + i, y + i))
                        break

        com = min(7 - x, y)
        for i in range(1, com + 1):
            if self.board[x + i][y - i][1:] != clr:
                # print(str((x + i, y - i)) + "Appending")
                pos_caps.append((x + i, y - i))
                for v in range(1, i):
                    if self.board[x + v][y - v] != " ":
                        # print(str((x + i, y - i)) + "Removing")
                        pos_caps.remove((x + i, y - i))
                        break

        com = min(x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x - i][y + i][1:] != clr:
                pos_caps.append((x - i, y + i))
                for v in range(1, i):
                    if self.board[x - v][y + v] != " ":
                        pos_caps.remove((x - i, y + i))
                        break

        return pos_caps


class Pawn_white:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = "_w"

    def moves(self):        
        all_moves = []
        (x, y) = self.pos
        if y > 0:
            if y == 6:
                all_moves.append((x, y - 1))
                all_moves.append((x, y - 2))

            else:
                all_moves.append((x, y - 1))

            if x > 0:
                if self.board[x - 1][y - 1][1:] != self.clr:
                    all_moves.append((x - 1, y - 1))
            if x < 7:
                if self.board[x + 1][y - 1][1:] != self.clr:
                    all_moves.append((x + 1, y - 1))

        for mv in reversed(all_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                all_moves.remove(mv)

        return all_moves


class Pawn_black:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos
        (self.x_pos, self.y_pos) = self.pos
        self.clr = "_b"

    def moves(self):
        all_moves = []
        (x, y) = self.pos

        if y == 1:
            all_moves.append((x, y + 1))
            all_moves.append((x, y + 2))

        elif y < 7:
            all_moves.append((x, y + 1))

            if x > 0:
                if self.board[x - 1][y + 1] != self.clr:
                    all_moves.append((x - 1, y + 1))
            if x < 7:
                if self.board[x + 1][y + 1] != self.clr:
                    all_moves.append((x + 1, y + 1))
                    
        for mv in reversed(all_moves):
            (x, y) = mv
            if self.board[x][y][1:] == self.clr:
                all_moves.remove(mv)

        return all_moves


class Bishop:
    def __init__(self, pos, brd):
        self.board = brd
        self.pos = pos

    def moves(self):
        pos_caps = []
        (x, y) = self.pos
        clr = self.board[x][y][1:]

        com = min(x, y)
        for i in range(1, com + 1):
            if self.board[x - i][y - i][1:] != clr:
                pos_caps.append((x - i, y - i))
                for v in range(1, i):
                    if self.board[x - v][y - v] != " ":
                        pos_caps.remove((x - i, y - i))
                        break

        com = min(7 - x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x + i][y + i][1:] != clr:
                pos_caps.append((x + i, y + i))
                for v in range(1, i):
                    if self.board[x + v][y + v] != " ":
                        pos_caps.remove((x + i, y + i))
                        break

        com = min(7 - x, y)
        for i in range(1, com + 1):
            if self.board[x + i][y - i][1:] != clr:
                pos_caps.append((x + i, y - i))
                for v in range(1, i):
                    if self.board[x + v][y - v] != " ":
                        pos_caps.remove((x + i, y - i))
                        break

        com = min(x, 7 - y)
        for i in range(1, com + 1):
            if self.board[x - i][y + i][1:] != clr:
                pos_caps.append((x - i, y + i))
                for v in range(1, i):
                    if self.board[x - v][y + v] != " ":
                        pos_caps.remove((x - i, y + i))
                        break

        return pos_caps

Saya harap saya menjelaskan semuanya tentang masalah/kode saya. Bantuan apa pun dihargai.

10
Honn 8 Januari 2021, 16:29

2 jawaban

Jawaban Terbaik

Ada banyak yang harus dilakukan dengan struktur data yang telah dihitung sebelumnya. Misalnya, Anda dapat menyiapkan kamus dengan kemungkinan tujuan dari posisi mana pun untuk setiap jenis dan orientasi bagian. Dengan itu, Anda tidak perlu kode rumit untuk memeriksa gerakan yang tersedia.

[LIHAT JAWABAN KEDUA SAYA UNTUK KODE KONSOLIDASI DAN PENYESUAIAN]

Anda juga dapat menggunakannya untuk melakukan verifikasi pertama untuk pemeriksaan!. Anda akan melakukannya dengan memeriksa posisi yang bisa dicapai raja jika itu adalah bidak lain. Misalnya jika Anda menemukan benteng di posisi di mana benteng bisa berpindah dari posisi raja maka ada potensi untuk diperiksa!. Melakukan ini untuk setiap jenis bidak akan memungkinkan Anda untuk mengetahui apakah mengevaluasi gerakan yang sebenarnya diperlukan.

from collections import defaultdict
targets   = dict()
positions = [ (r,c) for r in range(8) for c in range(8) ]
def valid(positions): 
    return [(r,c) for r,c in positions if r in range(8) and c in range(8)]

Mulai dengan lintasan dasar ...

targets["up"]    = { (r,c):valid( (r+v,c) for v in range(1,8))
                           for r,c in positions }
targets["down"]  = { (r,c):valid( (r-v,c) for v in range(1,8))
                           for r,c in positions }
targets["vertical"]  = { (r,c):targets["up"][r,c]+targets["down"][r,c]
                           for r,c in positions }

targets["left"]  = { (r,c):valid( (r,c+h) for h in range(1,8))
                           for r,c in positions }
targets["right"] = { (r,c):valid( (r,c+h) for h in range(1,8))
                           for r,c in positions }
targets["horizontal"] = { (r,c):targets["left"][r,c]+targets["right"][r,c]
                           for r,c in positions }

targets["upleft"]  = { (r,c):[(ru,cl) for (ru,_),(_,cl) in zip(targets["up"][r,c],targets["left"][r,c])]
                           for r,c in positions }

targets["upright"] = { (r,c):[(ru,cr) for (ru,_),(_,cr) in zip(targets["up"][r,c],targets["right"][r,c])]
                           for r,c in positions }

targets["downleft"] = { (r,c):[(rd,cl) for (rd,_),(_,cl) in zip(targets["down"][r,c],targets["left"][r,c])]
                           for r,c in positions }

targets["downright"] = { (r,c):[(rd,cr) for (rd,_),(_,cr) in zip(targets["down"][r,c],targets["right"][r,c])]
                           for r,c in positions }

targets["diagUL"] = { (r,c):targets["upleft"][r,c]+targets["downright"][r,c]
                           for r,c in positions }
targets["diagDL"] = { (r,c):targets["downleft"][r,c]+targets["upright"][r,c]
                           for r,c in positions }

Kemudian gabungkan untuk setiap jenis bagian ...

targets["king"]    = { (r,c):valid( (r+v,c+h) for v in (-1,0,1) for h in (-1,0,1) if v or h)
                           for r,c in positions }
targets["rook"]    = { (r,c):targets["horizontal"][r,c]+targets["vertical"][r,c]
                           for r,c in positions }
targets["bishop"]  = { (r,c):targets["diagUL"][r,c]+targets["diagDL"][r,c]
                           for r,c in positions }
targets["queen"]   = { (r,c):targets["rook"][r,c]+targets["bishop"][r,c]
                           for r,c in positions }
targets["knight"]  = { (r,c):valid((r+v,c+h) for v,h in [(2,1),(2,-1),(1,2),(1,-2),(-2,1),(-2,-1),(-1,2),(-1,-2)])
                           for r,c in positions } 
targets["wpawn"]   = { (r,c):valid([(r+1,c)]*(r>0) + [(r+2,c)]*(r==1))
                           for r,c in positions }
targets["bpawn"]   = { (r,c):valid([(r-1,c)]*(r<7) + [(r-2,c)]*(r==6))
                           for r,c in positions }
targets["wptake"]  = { (r,c):valid([(r+1,c+1),(r+1,c-1)]*(r>0))
                           for r,c in positions }
targets["bptake"]  = { (r,c):valid([(r-1,c+1),(r-1,c-1)]*(r<7))
                           for r,c in positions }
targets["wcastle"] = defaultdict(list,{ (0,4):[(0,2),(0,6)] })
targets["bcastle"] = defaultdict(list,{ (7,4):[(7,2),(7,6)] }) 

Ini akan memungkinkan Anda untuk langsung mendapatkan daftar posisi pergerakan potensial untuk bagian mana pun di papan tulis.

Sebagai contoh:

 targets["bishop"][5,4]
 # [(6, 3), (7, 2), (4, 5), (3, 6), (2, 7), (4, 3), (3, 2), (2, 1), (1, 0), (6, 5), (7, 6)]

Untuk mengetahui apakah ada potensi cek pada raja putih di 5,4, Anda dapat melakukan verifikasi cepat sebelum masuk ke simulasi langkah:

 kingPos = (5,4)
 checkByQueen  = any(board[r][c]=="q_b" for r,c in targets["queen"][kingPos])
 checkByKnight = any(board[r][c]=="n_b" for r,c in targets["knight"][kingPos])
 checkByRook   = any(board[r][c]=="r_b" for r,c in targets["rook"][kingPos])
 checkByBishop = any(board[r][c]=="b_b" for r,c in targets["bishop"][kingPos])
 checkByPawn   = any(board[r][c]=="p_b" for r,c in targets["wptake"][kingPos])

Jika tidak ada yang Benar, maka tidak ada ancaman bagi raja kulit putih. Jika checkByQueen, checkByRook atau checkByBishop adalah True, maka Anda harus memverifikasi oklusi dengan bagian lain di antaranya tetapi itu akan mengurangi jumlah kasus secara signifikan.

Anda juga dapat meningkatkan kamus untuk memberi Anda posisi di antara dua kotak di papan menggunakan posisi sebagai kunci (bukan string).

for r,c in positions:
    targets[(r,c)] = defaultdict(list)
    for direction in ("up","down","left","right","upleft","upright","downleft","downright"):
        path = targets[direction][r,c]
        for i,(tr,tc) in enumerate(path):
            targets[(r,c)][tr,tc]=path[:i]

Ini akan memungkinkan Anda untuk dengan mudah memeriksa apakah ada bagian di antara dua posisi. Misalnya, jika Anda menemukan ratu di (5,0) Anda dapat memeriksa apakah raja sejajar dengan menggunakan ini:

queenPos = next((r,c) for r,c in targets["queen"][kingPos] 
                      if board[r][c]=="q_b") # (5,0)

targets[kingPos][queenPos] # [(5, 3), (5, 2), (5, 1)]

lineOfSight = all(board[r][c]=="" for r,c in targets[kingPos][queenPos])

Ini dapat digabungkan ke dalam kondisi di atas untuk memberikan verifikasi yang komprehensif:

def lineOfSight(A,B): 
    return all(board[r][c]=="" for r,c in targets[A][B])

checkByQueen  = any(board[r][c]=="q_b" and lineOfSight(kingPos,(r,c))
                    for r,c in targets["queen"][kingPos] )
checkByRook   = any(board[r][c]=="r_b" and lineOfSight(kingPos,(r,c))
                    for r,c in targets["rook"][kingPos]  )
checkByBishop = any(board[r][c]=="b_b" and lineOfSight(kingPos,(r,c))
                    for r,c in targets["bishop"][kingPos])

Dengan menggunakan semua ini, Anda tidak perlu mensimulasikan gerakan sama sekali untuk mendeteksi tanda centang!, Anda dapat melakukannya dalam satu baris:

isCheck = any( board[r][c]==opponent and lineOfSight(kingPos,(r,c))
               for opponent,piece in [("q_b","queen"),("r_b","rook"),("b_b","bishop"),("n_b","knight"),("p_b","wptake")]
               for r,c in target[piece][kingPos] )    
  

Konten sampel:

for r,c in positions:
    print("FROM",(r,c))
    for piece in targets:
        print(f"  {piece:10}:",*targets[piece][r,c])

...

FROM (2, 4)
  up        : (3, 4) (4, 4) (5, 4) (6, 4) (7, 4)
  down      : (1, 4) (0, 4)
  vertical  : (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4)
  left      : (2, 3) (2, 2) (2, 1) (2, 0)
  right     : (2, 5) (2, 6) (2, 7)
  horizontal: (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7)
  upleft    : (3, 3) (4, 2) (5, 1) (6, 0)
  upright   : (3, 5) (4, 6) (5, 7)
  downleft  : (1, 3) (0, 2)
  downright : (1, 5) (0, 6)
  diagUL    : (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6)
  diagDL    : (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
  king      : (1, 4) (1, 5) (2, 3) (2, 5) (3, 3) (3, 4)
  rook      : (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7) (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4)
  bishop    : (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6) (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
  queen     : (2, 3) (2, 2) (2, 1) (2, 0) (2, 5) (2, 6) (2, 7) (3, 4) (4, 4) (5, 4) (6, 4) (7, 4) (1, 4) (0, 4) (3, 3) (4, 2) (5, 1) (6, 0) (1, 5) (0, 6) (1, 3) (0, 2) (3, 5) (4, 6) (5, 7)
  wpawn     : (3, 4)
  bpawn     : (1, 4)
  wptake    : (3, 5) (3, 3)
  bptake    : (1, 5) (1, 3)
  knight    : (4, 5) (4, 3) (3, 6) (3, 2) (0, 5) (0, 3) (1, 6) (1, 2)    
...

[EDIT]

Untuk memanfaatkan ini untuk generasi bergerak, Anda masih harus menambahkan beberapa kondisi tetapi saya yakin kamus harus membuat logika lebih sederhana dan lebih cepat:

# add to setup ...
targets["bishop"]["paths"] = ["upleft","upright","downleft","downright"]
targets["rook"]["paths"]   = ["up","down","left","right"]
targets["queen"]["paths"]  = targets["bishop"]["paths"]+targets["rook"]["paths"]

def linearMoves(position,opponent,piece):
    if position in pinnedPositions: return # see below
    for direction in targets[piece]["paths"]
        for r,c in targets[direction][position]:
              if board[r][c]=="": yield (position,(r,c)); continue
              if board[r][c].endswith(opponent): yield(position,(r,c))
              break

... inisialisasi siklus generasi bergerak

# flag white pieces that are pinned 
# (do this before each move generation)

pinnedPositions = set()
for piece,path in [("q_b","queen"),("r_b","rook"),("b_b","bishop"):
    for T in targets[path][kingPos]:
        if board[T] != piece: continue
        pinned = [[board[r][c][-1:] for r,c in targets[T][kingPos]]
        if pinned.count("w")==1 and "b" not in pinned:
            pinnedPositions.add(targets[T][kingPos][pinned.index("w")])

... untuk setiap bagian di papan ...

moves = []
# Move white bishop from position bishosPos ...
moves += linearMoves(bishopPos,"b","bishop")

# Move white rook from position rookPos ...
moves += linearMoves(rookPos,"b","rook")

# Move white queen from position queenPos ...
moves += linearMoves(queenPos,"b","queen")

# Move white knight from position knightPos ...
moves += ( (knightPos,(r,c)) for r,c in targets["knight"][knightPos]
           if board[r][c][-1:]!="w" )    

# Move white pawn from position pawnPos ...
moves += ( (pawnPos,(r,c)) for r,c in targets["wpawn"][pawnPos]
           if board[r][c][-1:]=="" and lineOfSight(pawnPos,(r,c)) )    
moves += ( (pawnPos,(r,c)) for r,c in targets["wptake"][pawnPos]
           if board[r][c][-1:]=="b" )    

# Move white king from position kingPos ... 
# (need to filter this so king doesn't place itself in check!)
moves += ( (kingPos,(r,c)) for r,c in targets["king"][kingPos]
           if board[r][c][-1]!="w" )    

      

Ada lebih banyak pengecualian untuk dikelola seperti "castling" dan "en passant" tetapi sebagian besar kode harus lebih sederhana (dan mungkin lebih cepat).

12
Alain T. 10 Januari 2021, 00:56

Sepertinya Anda memperumit hal-hal dalam pembuatan gerakan Anda dan memeriksa deteksi yang membuatnya sangat lambat.

Pendekatan deteksi pemeriksaan yang lebih baik

Sekarang Anda mengatakan bahwa Anda menghasilkan semua gerakan hukum untuk lawan dan melihat apakah mereka dapat menangkap raja. Ini sangat lambat dan pendekatan yang lebih baik adalah melihat dari perspektif raja Anda sendiri dan melihat apakah ada bidak musuh ke segala arah setelah Anda bergerak, itu bisa terlihat seperti ini (di mana kotak adalah kotak raja Anda):

def is_in_check(square):

    enemy_color, friendly_color = ('b', 'w') if self.is_white_turn else ('w', 'b')

    # Check out from all directions from the king
    for i, d in enumerate(s.directions):
        for j in range(1, 8):  # Check the entire row/column in that direction
            end_square = square + d*j
            piece_color, piece_type = self.board[end_square][0], self.board[end_square][1]
            if is_on_board(end_square ):
                if piece_color == friendly_color and piece_type != 'K':
                    break
                elif piece_color == enemy_color:
                    # 5 different cases:
                    # 1. Orthogonally from king and piece is a rook
                    # 2. Diagonally from king and piece is a bishop
                    # 3. 1 square away diagonally from king and piece is a pawn
                    # 4. Any direction and piece is a queen
                    # 5. Any direction 1 square away and piece is a king
                    if (0 <= i <= 3 and piece_type == 'R') or \
                            (4 <= i <= 7 and piece_type == 'B') or \
                            (j == 1 and piece_type == 'p' and ((enemy_color == 'w' and 6 <= i <= 7) or (enemy_color == 'b' and 4 <= i <= 5))) or \
                            (piece_type == 'Q') or \
                            (j == 1 and piece_type == 'K'):
                        return True
                    else:  # Enemy piece that is not applying check or pin
                        break
            else:  # i, j is off board
                break

    # Check for knight checks
    for d in s.knight_moves:
        end_piece = self.board[square + d]
        if is_on_board(end_square):
            if end_piece[1] == 'N' and end_piece[0] == enemy_color:  # Enemy knight attacking king
                return True

    return False

Tanyakan di komentar jika kodenya tidak jelas, saya paling banyak menyalin dari mesin awal saya sehingga mungkin tidak persis seperti representasi Anda. Idenya adalah untuk melihat keluar dari segala arah dari raja. Jika Anda menemukan bagian sendiri atau keluar dari papan, istirahat dan lanjutkan ke arah berikutnya. Jika Anda menemukan bidak musuh, maka ada 5 kasus yang dikomentari dalam kode: jika Anda melihat secara diagonal dan bidak musuh adalah uskup dll. Pencarian ini sangat cepat karena maksimal Anda harus melihat 27 tempat jika raja berada di tengah papan dan tidak ada bagian yang menghalangi, tetapi seringkali jauh lebih sedikit.

Pindahkan generasi

Saya telah menghabiskan banyak waktu untuk mencoba membuat mesin Python saya secepat mungkin dan memulai seperti Anda dengan representasi papan array 2D. Ini berfungsi, tetapi representasi papan 1D lebih cepat (walaupun sedikit lebih sulit untuk dipahami).

Tetapi untuk representasi 2D Anda, ada 2 pendekatan seperti yang saya lihat:

  1. Hasilkan gerakan hukum semu dan kemudian pada pencarian Anda menguji apakah itu legal atau tidak.
  2. Hasilkan semua potongan yang disematkan dan kemudian hasilkan hanya gerakan legal.

1. Buat langkah hukum semu dengan pemeriksaan hukum nanti

Sepertinya Anda memiliki pendekatan kerja. Saya merasa sedikit lebih baik untuk mengulang melalui arah yang mungkin daripada memilikinya dalam 4 loop terpisah, sesuatu seperti ini untuk ratu misalnya (maaf untuk menunjukkan pendekatan 1D saya, namun serupa untuk Anda, hanya arah lain):

def get_queen_moves(square):

    # Up, left, down, right, up/left, up/right, down/left, down/right
    for d in [-10, -1, 10, 1, -11, -9, 9, 11]:
        for i in range(1, 8):   # At most 7 squares in each direction
            end_square = square + d*i
            end_piece = self.board[end_square]

            # If square is enemy piece or empty square, append move
            if end_piece in [enemy_pieces, empty_square]:
                moves.append(square, end_square)

                # If enemy piece, then break the direction since we can't go further here
                if end_piece in enemy_pieces:
                    break
            # Found own piece, can't move here so move on to next direction
            else:
                break

Di pencarian minimax Anda (negamax dalam kasus saya, pendekatan yang sama) Anda akan melakukan sesuatu seperti ini:

def negamax(depth, alpha, beta):

    # Depth = 0, return value from the quiescence search
    if depth == 0:
        return self.quiescence(alpha, beta)

    # Get pseudo legal moves
    children = gen_moves(self.gamestate)

    # Negamax recursive loop
    for child in children:

        # If move is legal, make it. Otherwise move on to the next candidate.
        # In my make_move function I return 1 if I am not left in check, otherwise I unmake the move there and return 0.
        if self.gamestate.make_move(child):

            # Do a normal search
            score = -self.negamax(depth - 1, -beta, -alpha, True)

            # Take back move
            self.gamestate.unmake_move()

Jika Anda menerapkan urutan langkah dan alfa/beta dll, kemungkinan besar Anda akan menghemat banyak waktu untuk tidak memeriksa legalitas semua gerakan, tetapi hanya untuk gerakan yang Anda pertimbangkan. Saya harap saya membuat diri saya jelas di sini.

2. Buat pin dan hanya langkah legal

Saya suka menghasilkan pin terlebih dahulu dan kemudian hanya menghasilkan gerakan legal. Ini sedikit lebih rumit, jadi tolong tanyakan apakah kode saya tidak jelas. Idenya adalah pergi dari raja ke segala arah seperti sebelumnya. Jika kami menemukan bagian sendiri (katakanlah uskup dalam kasus ini) di mis. arah diagonal kami terus berjalan lebih sering dan melihat apakah kami menemukan uskup atau ratu musuh ke arah itu. Jika kita melakukannya, uskup kita disematkan. Kami menyimpan bidak tersebut dan juga ke arah mana ia ditemukan (potongan yang disematkan masih bisa bergerak, menuju dan menjauh dari raja jika itu adalah uskup seperti dalam kasus ini).

Berikut adalah kode untuk menghasilkan gerakan hukum dan juga untuk menemukan pin dan cek:

# Get all moves considering checks and pins
def get_valid_moves(self):

    king_pos = self.white_king_location if self.is_white_turn else self.black_king_location

    # Find if is in check and all the possible pinned pieces
    self.is_in_check, self.pins, self.checks = self.check_for_pins_and_checks(king_pos)

    # If we are in check we can only take the piece, move the king, or put own piece in the way
    if self.is_in_check:
        if len(self.checks) == 1:  # Single check
            moves = self.get_all_possible_moves()
            check = self.checks[0]
            checking_piece_pos = check[0]
            piece_checking = self.board[check[0]]  # Enemy piece that is causing the check
            valid_squares = []  # Valid squares the piece can move to
            if piece_checking[1] == 'N':  # Knight check, must capture knight or move king
                valid_squares = [checking_piece_pos]
            else:
                for i in range(1, 8):
                    valid_square = (king_pos + check[1] * i)  # Look in the direction of checking piece
                    valid_squares.append(valid_square)
                    if valid_square == checking_piece_pos:  # If finding the checking piece, look no further
                        break
            # Filter to only keep moves that are valid during check
            moves = list(filter(lambda x: x[0] == king_pos or x[1] in valid_squares or
                                (self.board[x[0]][1] == 'p' and x[1] == self.enpassant_square and piece_checking[1] == 'p'), moves))
        else:  # Double check, only king can move
            moves = []
            self.get_king_moves(king_pos, moves, False)
    # If not in check, we find all moves (with respect to pins)
    else:
        moves = self.get_all_possible_moves()

    return moves

# Checks if there are any pinned pieces or current checks
def check_for_pins_and_checks(self, square):
    pins, checks = [], []
    is_in_check = False

    enemy_color, friendly_color = ('b', 'w') if self.is_white_turn else ('w', 'b')

    # Check out from all directions from the king
    for i in range(8):
        d = s.directions[i]
        possible_pin = False
        for j in range(8):  # Check the entire row/column in that direction
            end_square = square + d*j
            piece_color, piece_type = self.board[end_square][0], self.board[end_square][1]
            if is_on_board(end_square):
                if piece_color == friendly_color and piece_type != 'K':
                    if not possible_pin:  # First own piece, we found a possible pin
                        possible_pin = (end_square, d)
                    else:  # 2nd friendly piece, it wasn't a pin
                        break
                elif piece_color == enemy_color:
                    # 5 different cases as before:
                    if (0 <= i <= 3 and piece_type == 'R') or \
                            (4 <= i <= 7 and piece_type == 'B') or \
                            (j == 1 and piece_type == 'p' and ((enemy_color == 'w' and 6 <= i <= 7) or (enemy_color == 'b' and 4 <= i <= 5))) or \
                            (piece_type == 'Q') or \
                            (j == 1 and piece_type == 'K'):
                        if not possible_pin:  # No friendly piece is blocking -> is check
                            is_in_check = True
                            checks.append((end_square, d))
                            break
                        else:  # Friendly piece is blocking -> we found a pinned piece
                            pins.append(possible_pin)
                            break
                    else:  # Enemy piece that is not applying check or pin
                        break
            else:  # i, j is off board
                break

    # Check for knight checks
    for d in s.knight_moves:
        end_square = square + d
        end_piece = self.board[end_square]
        if is_on_board(end_square):
            if end_piece[0] == enemy_color and end_piece[1] == 'N':  # Enemy knight attacking king
                is_in_check = True
                checks.append((end_square, d))

    return is_in_check, pins, checks

Jadi sekarang kita perlu menerapkan informasi yang kita pin ke fungsi generate move. Saya akan menggunakan ratu sebagai contoh lagi. Satu-satunya hal yang perlu kita lakukan adalah menemukan apakah potongan tersebut disematkan (potongan kode tambahan pertama) dan kemudian tepat sebelum kita menambahkan langkah, kita perlu memeriksa bahwa potongan tersebut tidak disematkan ATAU bahwa arah pin memungkinkan kita untuk memindahkan potongan ada (misalnya memindahkan ratu menuju atau menjauh dari raja).

def get_queen_moves(square):

    # Loop through our pins and see if our piece is pinned. Remove it from our pinned piece list since we don't need the information any more.
    pin_direction = ()
    for i in range(len(self.pins)-1, -1, -1):
        if self.pins[i][0] == square:
            piece_pinned = True
            pin_direction = (self.pins[i][1])
            self.pins.remove(self.pins[i])
            break

    # Up, left, down, right, up/left, up/right, down/left, down/right
    for d in [-10, -1, 10, 1, -11, -9, 9, 11]:
        for i in range(1, 8):   # At most 7 squares in each direction
            end_square = square + d*i
            end_piece = self.board[end_square]

            # If square is enemy piece or empty square, append move
            if end_piece in [enemy_pieces, empty_square]:

                # Here we check if piece is pinned or if the direction allows us to add the piece anyway. 
                if not piece_pinned or pin_direction in (d, -d):
                    moves.append(square, end_square)

                    # If enemy piece, then break the direction since we can't go further here
                    if end_piece in enemy_pieces:
                        break
            # Found own piece, can't move here so move on to next direction
            else:
                break

Itu saja, silakan bertanya jika Anda memiliki pertanyaan lebih lanjut :)

2
Eli 9 Januari 2021, 16:04