การสร้าง AI หมากรุก ด้วย python (Chess AI)

narongrit

Narongrit

Posted on April 12, 2024

การสร้าง AI หมากรุก ด้วย python (Chess AI)

การสร้าง AI ในเกมนั้นเป็นอะไรที่ค่อนข้างยากเนื่องจากระบบเกมที่มีความซับซ้อนสูงในหลายๆเกมในปัจจุบัน แต่ก็ยังมีเกมกระดานหรือเกมต่างๆที่ยังได้รับความนิยมอยู่ ถึงแม้จะไม่ได้มีความซับซ้อนมาก เกมที่หยิบยกมาครั้งนี้ก็คือ "เกมหมากรุก"

เริ่มต้นการสร้าง AI เล่นหมากรุก
ขั้นตอนที่ 1

pip install chess
Enter fullscreen mode Exit fullscreen mode

การใช้ Library ไลบรารี่ที่จะดูแลกฏเกณฑ์ทั้งหมดนี้ตลอดจนการแสดงผลของบอร์ด เริ่มต้นด้วยการติดตั้ง python-chess

การทดลองสร้าง บอร์ดหมากรุก ขึ้นมาด้วยไลบารี่

import chess

board = chess.Board()
Enter fullscreen mode Exit fullscreen mode

หากแสดงผลออกมา จะได้รับจอแสดงผลคอนโซลหรือรูปภาพ ขึ้นอยู่กับโปรแกรม Python สำหรับบทความนี้ จะใช้ Jupyter Notebook เพื่อแสดงภาพที่ชัดเจนต่อการบรรยาย

Image description

การประเมินกระดานและการหาเส้นทางที่ดีที่สุด

ขั้นตอนที่ 2

เพื่อสร้างอัลกอริธึมของ เราจำเป็นต้องค้นหาการเคลื่อนไหวที่ดีที่สุดเท่าที่จะเป็นไปได้ เราจำเป็นต้องประเมินการเคลื่อนไหวที่เป็นไปได้แต่ละครั้ง ไม่ว่าจะโดยการเพิ่มหรือลดคะแนน

ในการประเมินกระดานและค้นหาการเคลื่อนไหว ให้เริ่มด้วยการกำหนดค่าให้กับแต่ละชิ้น เริ่มจากชิ้นส่วนที่สำคัญที่สุดคือเบี้ย เราจะให้คะแนนมันต่ำ และ ราชินีซึ่งเป็นตัวที่สำคัญที่สุด (แน่นอนว่าต้องมีราชาด้วย) สมมติว่าเบี้ยมีค่าเท่ากับ 1 บิชอปหรือม้ามีค่าเท่ากับ 3 เรือมีค่าเท่ากับ 5 ราชินีมีค่าเท่ากับ 9 และราชามีค่าเท่ากับ 0

piece_values = {
    chess.PAWN: 1,
    chess.KNIGHT: 3,
    chess.BISHOP: 3,
    chess.ROOK: 5,
    chess.QUEEN: 9,
    chess.KING: 0
}
Enter fullscreen mode Exit fullscreen mode

การสร้างฟังก์ชันการประเมินผลโดยใช้ Chess

def evaluate_board(board):
    score = 0
    for square in chess.SQUARES:
        piece = board.piece_at(square)
        if piece is not None:
            if piece.color == chess.WHITE:
                score += piece_values[piece.piece_type]
            else:
                score -= piece_values[piece.piece_type]
    return score
Enter fullscreen mode Exit fullscreen mode

สร้างฟังก์ชันการประเมินบอร์ด

 board = chess.Board()
    evaluation = evaluate_board(board)
    print(f"Evaluation with all pieces: {evaluation}")

    board.remove_piece_at(chess.E2)
    evaluation = evaluate_board(board)
    print(f"Evaluation without a white pawn: {evaluation}")

    board.remove_piece_at(chess.A8)
    evaluation = evaluate_board(board)
    print(f"Evaluation without a black rook: {evaluation}")
Enter fullscreen mode Exit fullscreen mode
Evaluation with all pieces: 0
Evaluation without a white pawn: -1
Evaluation without a black rook: 4
Enter fullscreen mode Exit fullscreen mode

การค้นหาเส้นทางที่ดีที่สุด

เพื่อค้นหาทางที่ดีที่สุด สิ่งที่เราต้องทำตอนนี้คือทดสอบท่งที่เป็นไปได้ทั้งหมด และดูว่าทางไหนนำไปสู่การประเมินบอร์ดที่ได้เปรียบที่สุดตามสีของเรา

def best_move_using_simple_evaluation(board):
    white_to_play = board.turn
    best_score = -9999 if white_to_play else 9999
    best_move = random_move(board)
    for move in board.legal_moves:  # we try each possible move to find the best
        board.push(move)
        score = evaluate_board(board)
        board.pop()
        if score > best_score and white_to_play:
            best_score = score
            best_move = move
        elif score < best_score and not white_to_play:
            best_score = score
            best_move = move
    return best_move
Enter fullscreen mode Exit fullscreen mode

ตอนนี้จะได้บอทที่เล่นหมากรุกได้แล้ว แต่อัลกอริธึม ของบอทตัวนี้ยังไม่มีประสิทธิภาพมากพอเพราะทางที่ AI เลือกยังไม่มีแบบแผนและค่อนข้างที่จะเป็นการ Random

การเพิ่มประสิทธิภาพของ AI

ขั้นตอนที่ 3

เราจะใช้ Minimax ที่เป็นอัลกอริทึมที่ใช้เพื่อลดการสูญเสียที่อาจเกิดขึ้นในกรณีที่เลวร้ายที่สุด มันเป็นอัลกอริทึมที่พิจารณาการตอบสนองที่ดีที่สุดต่อสถานการณ์ และเลือกกลยุทธ์เพื่อให้การตอบสนองที่ดีที่สุด ดังนี้

def minimax(board, depth, white_to_play):
    if depth == 0 or board.is_game_over():
        return evaluate_board(board)
    if white_to_play:
        best_score = -99999
        for move in board.legal_moves:
            board.push(move)
            score = minimax(board, depth - 1, False)
            board.pop()
            best_score = max(score, best_score)
        return best_score
    else:
        best_score = 99999
        for move in board.legal_moves:
            board.push(move)
            score = minimax(board, depth - 1, True)
            board.pop()
            best_score = min(score, best_score)
        return best_score
Enter fullscreen mode Exit fullscreen mode

ตอนนี้เราแค่ต้องแก้ไขฟังก์ชันของเราที่คำนวณการเคลื่อนไหวที่ดีที่สุดเพื่อคำนวณคะแนนโดยใช้ minimax

def best_move_using_minimax(board, depth):
    white_to_play = board.turn
    best_score = -99999 if white_to_play else 99999
    best_move = random_move(board)
    for move in board.legal_moves:
        board.push(move)
        score = minimax(board, depth - 1, not white_to_play)
        board.pop()
        if score > best_score and white_to_play:
            best_score = score
            best_move = move
        elif score < best_score and not white_to_play:
            best_score = score
            best_move = move
    return best_move
Enter fullscreen mode Exit fullscreen mode

ผลลัพธ์ที่ได้จากการใช้ Minimax หลังจากเดิน 4-5 รอบ (AI ฝ่ายขาว)
Image description

การเลือกเส้นทางของ AI นั้นดีดูมีแผนการมากขึ้นนิดหน่อยแต่ยังดูไม่ค่อยดีมากนักและใช้เวลาคำนวนนานเราจึงต้องปรับปรุง Minimax เพิ่มเติม

การปรับปรุง Minimax ให้ใช้การได้ดียิ่งขึ้น

ขั้นตอนที่ 4

เราจะใช้ Alpha-Beta Pruning เพื่อเพิ่มประสิทธิภาพอัลกอริธึม minimax ของเรา เทคนิคนี้จะกำจัดแผนผังเกมที่รับประกันว่าจะแย่กว่าทางเลือกอื่นที่สำรวจก่อนหน้านี้ ช่วยลดจำนวนตำแหน่งที่ต้องประเมิน ทำให้กระบวนการค้นหาเร็วขึ้น

def minimax(board, depth, alpha, beta, white_to_play):
    if depth == 0:
        return evaluate_board(board), None
    if white_to_play:
        best_score = -9999
        best_move = None
        for move in board.legal_moves:
            board.push(move)
            score, _ = minimax(board, depth - 1, alpha, beta, False)
            board.pop()
            if score > best_score:
                best_score = score
                best_move = move
            alpha = max(alpha, best_score)
            if alpha >= beta:
                break
        return best_score, best_move
    else:
        best_score = 9999
        best_move = None
        for move in board.legal_moves:
            board.push(move)
            score, _ = minimax(board, depth - 1, alpha, beta, True)
            board.pop()
            if score < best_score:
                best_score = score
                best_move = move
            beta = min(beta, best_score)
            if alpha >= beta:
                break
        return best_score, best_move
Enter fullscreen mode Exit fullscreen mode

อัลกอริธึมนี้เป็นการปรับปรุง Minimax มีประสิทธิภาพมากขึ้นและกินทรพยากรน้อยลง โดยไม่ส่งผลต่อการเปลี่ยนแปลงผลลัพธ์ที่เกิดขึ้นของ AI

ฟังก์ชั่นการประเมินของเราเป็นพื้นฐานมาก โดยจะกำหนดค่าตายตัวให้กับชิ้นส่วน ดังนั้น AI จึงไม่คำนึงถึงตำแหน่งของหมาก เช่น เรารู้ว่าม้าที่อยู่มุมหนึ่งมีความสำคัญน้อยกว่าม้าที่อยู่ตรงกลาง หรืออีกกรณี คือ เบี้ยที่เข้าใกล้แคมป์ของฝ่ายตรงข้ามมีความสำคัญมากกว่าเบี้ยที่ยังไม่ขยับ เนื่องจากมีโอกาสมากที่จะกลายเป็นราชินี

ดังนั้นเราจะเปลี่ยนฟังก์ชั่นการประเมินผลโดยคำนึงถึงตำแหน่งของชิ้นส่วน เริ่มต้นด้วยการเปลี่ยน dictionary ของเรา

piece_values_with_position = {
    chess.PAWN: [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [50, 50, 50, 50, 50, 50, 50, 50],
        [10, 10, 20, 30, 30, 20, 10, 10],
        [5, 5, 10, 25, 25, 10, 5, 5],
        [0, 0, 0, 20, 20, 0, 0, 0],
        [5, -5, -10, 0, 0, -10, -5, 5],
        [5, 10, 10, -20, -20, 10, 10, 5],
        [0, 0, 0, 0, 0, 0, 0, 0]
    ],
    chess.KNIGHT: [
        [-50, -40, -30, -30, -30, -30, -40, -50],
        [-40, -20, 0, 0, 0, 0, -20, -40],
        [-30, 0, 10, 15, 15, 10, 0, -30],
        [-30, 5, 15, 20, 20, 15, 5, -30],
        [-30, 0, 15, 20, 20, 15, 0, -30],
        [-30, 5, 10, 15, 15, 10, 5, -30],
        [-40, -20, 0, 5, 5, 0, -20, -40],
        [-50, -40, -30, -30, -30, -30, -40, -50]
    ],
    chess.BISHOP: [
        [-20, -10, -10, -10, -10, -10, -10, -20],
        [-10, 0, 0, 0, 0, 0, 0, -10],
        [-10, 0, 5, 10, 10, 5, 0, -10],
        [-10, 5, 5, 10, 10, 5, 5, -10],
        [-10, 0, 10, 10, 10, 10, 0, -10],
        [-10, 10, 10, 10, 10, 10, 10, -10],
        [-10, 5, 0, 0, 0, 0, 5, -10],
        [-20, -10, -10, -10, -10, -10, -10, -20]
    ],
    chess.ROOK: [
        [0, 0, 0, 0, 0, 0, 0, 0],
        [5, 10, 10, 10, 10, 10, 10, 5],
        [-5, 0, 0, 0, 0, 0, 0, -5],
        [-5, 0, 0, 0, 0, 0, 0, -5],
        [-5, 0, 0, 0, 0, 0, 0, -5],
        [-5, 0, 0, 0, 0, 0, 0, -5],
        [-5, 0, 0, 0, 0, 0, 0, -5],
        [0, 0, 0, 5, 5, 0, 0, 0]
    ],
    chess.QUEEN: [
        [-20, -10, -10, -5, -5, -10, -10, -20],
        [-10, 0, 0, 0, 0, 0, 0, -10],
        [-10, 0, 5, 5, 5, 5, 0, -10],
        [-5, 0, 5, 5, 5, 5, 0, -5],
        [0, 0, 5, 5, 5, 5, 0, -5],
        [-10, 5, 5, 5, 5, 5, 0, -10],
        [-10, 0, 5, 0, 0, 0, 0, -10],
        [-20, -10, -10, -5, -5, -10, -10, -20]
    ],
    chess.KING: [
        [-30, -40, -40, -50, -50, -40, -40, -30],
        [-30, -40, -40, -50, -50, -40, -40, -30],
        [-30, -40, -40, -50, -50, -40, -40, -30],
        [-30, -40, -40, -50, -50, -40, -40, -30],
        [-20, -30, -30, -40, -40, -30, -30, -20],
        [-10, -20, -20, -20, -20, -20, -20, -10],
        [20, 20, 0, 0, 0, 0, 20, 20],
        [20, 30, 10, 0, 0, 10, 30, 20]
    ]
}
Enter fullscreen mode Exit fullscreen mode

ตอนนี้เราใช้รายการที่มีคะแนนสำหรับแต่ละตำแหน่งของชิ้นส่วนบนกระดาน ยิ่งคะแนนสูง ชิ้นส่วนก็ยิ่งมีความสําคัญมากขึ้น

ตอนนี้เราสามารถเขียนฟังก์ชันการประเมินของเราใหม่ได้

def get_piece_value(piece, x, y):
    if piece.piece_type == chess.PAWN:
        return 100 + piece_values_with_position[piece.piece_type][x][y]
    elif piece.piece_type == chess.KNIGHT:
        return 320 + piece_values_with_position[piece.piece_type][x][y]
    elif piece.piece_type == chess.BISHOP:
        return 330 + piece_values_with_position[piece.piece_type][x][y]
    elif piece.piece_type == chess.ROOK:
        return 500 + piece_values_with_position[piece.piece_type][x][y]
    elif piece.piece_type == chess.QUEEN:
        return 900 + piece_values_with_position[piece.piece_type][x][y]
    elif piece.piece_type == chess.KING:
        return 20000 + piece_values_with_position[piece.piece_type][x][y]
    else:
        return 0


def evaluate_board(board):
    score = 0
    for i in range(8):
        for j in range(8):
            piece = board.piece_at(chess.square(i, j))
            if piece is not None:
                if piece.color == chess.WHITE:
                    score += get_piece_value(piece, i, j)
                else:
                    score -= get_piece_value(piece, i, j)

    return score
Enter fullscreen mode Exit fullscreen mode

เราไม่จำเป็นต้องแก้ไขอัลกอริทึมของเรา เนื่องจากมันไม่ได้ขึ้นอยู่กับฟังก์ชันการประเมินที่เราใช้ ดังนั้นเราจึงสามารถลองใช้ฟังก์ชันการประเมินใหม่ของเราได้โดยทันที

move = best_move_using_minimax(board, 5)
board.push(move)
board
Enter fullscreen mode Exit fullscreen mode

ตอนนี้เรามีอัลกอริธึมที่เล่นได้ค่อนข้างดี โดยผลลัพธ์ที่ได้ระหว่างเล่นคือ

Image description

AI มีแบบแผนค่อนข้างดีถึงในระกับที่สามารถจัดการกับผู้เล่นใหม่ฝึกหัดได้แล้ว!

สรุป

ตอนนี้เรามีอัลกอริธึมซึ่งยอมได้ว่าถึงจะเป็นอัลกอริธึมพื้นฐาน แต่ก็เล่นโดยมีแบบแผนและไม่พลาดมากเกินไปจนสามารถเอาชนะมือใหม่ได้อย่างสมบูรณ์แบบได้แล้ว และ เพื่อให้ทำงานได้ดียิ่งขึ้น เราจำเป็นต้องมีทรัพยากรเพิ่มเติมเพื่อเพิ่มความลึกหรืออัลกอริธึมที่ใช้โครงข่ายประสาทเทียมที่ได้รับการฝึกฝนในเกมจำนวนมาก ในที่นี่ ตอนนี้ AI เล่นหมากรุกพื้นฐานอันนี้ก็คงสามารถนำไปใช้ในการฝึกฝนได้จริงในระดับนึงแล้ว

💖 💪 🙅 🚩
narongrit
Narongrit

Posted on April 12, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related