การสร้าง AI หมากรุก ด้วย python (Chess AI)
Narongrit
Posted on April 12, 2024
การสร้าง AI ในเกมนั้นเป็นอะไรที่ค่อนข้างยากเนื่องจากระบบเกมที่มีความซับซ้อนสูงในหลายๆเกมในปัจจุบัน แต่ก็ยังมีเกมกระดานหรือเกมต่างๆที่ยังได้รับความนิยมอยู่ ถึงแม้จะไม่ได้มีความซับซ้อนมาก เกมที่หยิบยกมาครั้งนี้ก็คือ "เกมหมากรุก"
เริ่มต้นการสร้าง AI เล่นหมากรุก
ขั้นตอนที่ 1
pip install chess
การใช้ Library ไลบรารี่ที่จะดูแลกฏเกณฑ์ทั้งหมดนี้ตลอดจนการแสดงผลของบอร์ด เริ่มต้นด้วยการติดตั้ง python-chess
การทดลองสร้าง บอร์ดหมากรุก ขึ้นมาด้วยไลบารี่
import chess
board = chess.Board()
หากแสดงผลออกมา จะได้รับจอแสดงผลคอนโซลหรือรูปภาพ ขึ้นอยู่กับโปรแกรม Python สำหรับบทความนี้ จะใช้ Jupyter Notebook เพื่อแสดงภาพที่ชัดเจนต่อการบรรยาย
การประเมินกระดานและการหาเส้นทางที่ดีที่สุด
ขั้นตอนที่ 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
}
การสร้างฟังก์ชันการประเมินผลโดยใช้ 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
สร้างฟังก์ชันการประเมินบอร์ด
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}")
Evaluation with all pieces: 0
Evaluation without a white pawn: -1
Evaluation without a black rook: 4
การค้นหาเส้นทางที่ดีที่สุด
เพื่อค้นหาทางที่ดีที่สุด สิ่งที่เราต้องทำตอนนี้คือทดสอบท่งที่เป็นไปได้ทั้งหมด และดูว่าทางไหนนำไปสู่การประเมินบอร์ดที่ได้เปรียบที่สุดตามสีของเรา
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
ตอนนี้จะได้บอทที่เล่นหมากรุกได้แล้ว แต่อัลกอริธึม ของบอทตัวนี้ยังไม่มีประสิทธิภาพมากพอเพราะทางที่ 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
ตอนนี้เราแค่ต้องแก้ไขฟังก์ชันของเราที่คำนวณการเคลื่อนไหวที่ดีที่สุดเพื่อคำนวณคะแนนโดยใช้ 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
ผลลัพธ์ที่ได้จากการใช้ Minimax หลังจากเดิน 4-5 รอบ (AI ฝ่ายขาว)
การเลือกเส้นทางของ 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
อัลกอริธึมนี้เป็นการปรับปรุง 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]
]
}
ตอนนี้เราใช้รายการที่มีคะแนนสำหรับแต่ละตำแหน่งของชิ้นส่วนบนกระดาน ยิ่งคะแนนสูง ชิ้นส่วนก็ยิ่งมีความสําคัญมากขึ้น
ตอนนี้เราสามารถเขียนฟังก์ชันการประเมินของเราใหม่ได้
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
เราไม่จำเป็นต้องแก้ไขอัลกอริทึมของเรา เนื่องจากมันไม่ได้ขึ้นอยู่กับฟังก์ชันการประเมินที่เราใช้ ดังนั้นเราจึงสามารถลองใช้ฟังก์ชันการประเมินใหม่ของเราได้โดยทันที
move = best_move_using_minimax(board, 5)
board.push(move)
board
ตอนนี้เรามีอัลกอริธึมที่เล่นได้ค่อนข้างดี โดยผลลัพธ์ที่ได้ระหว่างเล่นคือ
AI มีแบบแผนค่อนข้างดีถึงในระกับที่สามารถจัดการกับผู้เล่นใหม่ฝึกหัดได้แล้ว!
สรุป
ตอนนี้เรามีอัลกอริธึมซึ่งยอมได้ว่าถึงจะเป็นอัลกอริธึมพื้นฐาน แต่ก็เล่นโดยมีแบบแผนและไม่พลาดมากเกินไปจนสามารถเอาชนะมือใหม่ได้อย่างสมบูรณ์แบบได้แล้ว และ เพื่อให้ทำงานได้ดียิ่งขึ้น เราจำเป็นต้องมีทรัพยากรเพิ่มเติมเพื่อเพิ่มความลึกหรืออัลกอริธึมที่ใช้โครงข่ายประสาทเทียมที่ได้รับการฝึกฝนในเกมจำนวนมาก ในที่นี่ ตอนนี้ AI เล่นหมากรุกพื้นฐานอันนี้ก็คงสามารถนำไปใช้ในการฝึกฝนได้จริงในระดับนึงแล้ว
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
November 30, 2024