อะไรคือ Alpha-Beta Pruning in AI?

เรามาทำความรู้จักกับ Alpha-Beta Pruning in AI? กันว่าคืออะไร

Alpha-Beta Pruning เป็นเทคนิคหนึ่งที่ใช้ในอัลกอริทึมปัญญาประดิษฐ์ (Artificial Intelligence) เพื่อเพิ่มประสิทธิภาพในการค้นหาในต้นไม้ค้นหา (Search Trees) โดยลดจำนวนโหนดที่ต้องตรวจสอบเพื่อหาคำตอบที่เป็นไปได้ทั้งหมด

หลักการทำงานของ Alpha-Beta Pruning เป็นอย่างไร

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

ข้อดีของการนำ Alpha-Beta Pruning เข้ามาช่วยมีประโยชน์อย่างไร

การใช้ Alpha-Beta Pruning ช่วยให้อัลกอริทึมปัญญาประดิษฐ์ทำงานได้เร็วขึ้นและให้ผลลัพธ์ที่ถูกต้องขึ้น

การสร้างเกมโดยใช้ Alpha-Beta

เป็นเทคนิคหนึ่งที่ใช้ในการพัฒนาเกมหรือโปรแกรมคอมพิวเตอร์ที่มีการตัดสินใจในสภาวะที่มีคู่แข่งและต้องเลือกทางเลือกที่ดีที่สุดในแต่ละรอบ ดังนั้นเกมที่ใช้อัลฟ่าเบต้าเป็นเทคนิคที่เกี่ยวข้องกับการคำนวณค่าคะแนนหรือคำนวณความคืบหน้าของเกม โดยในบทความนี้จะยกตัวอย่าง "เกมหมากฮอส (Checkers)"

เกมหมากฮอส (Checkers)

เป็นเกมกระดานวางแผนสำหรับผู้เล่นสองคน ซึ่งเกี่ยวข้องกับการเดินหมากเหมือนกันในแนวทแยงและการยึดบังคับโดยโดดข้ามหมากฝั่งตรงข้าม ในบทความนี้ได้เขียนเกมหมากฮอสที่เขียนโดยใช้อัลกอริทึม minimax และ Alpha-Beta

สามารถดูวิธีการเล่นได้ที่นี่ คลิ๊ก

ขั้นตอนที่ 1 import โมดูล deepcopy จากไลบรารี copy และ time และ math
ทั้งสามโมดูลเป็นส่วนหนึ่งของไลบรารีพื้นฐานของ Python ที่มาพร้อมกับการติดตั้ง Python แล้วเรียบร้อยแล้ว

• โมดูล deepcopy จะช่วยให้เราสามารถสร้างคัดลอก (copy) วัตถุใน Python ที่มีโครงสร้างซับซ้อนได้โดยไม่มีการอ้างอิงถึงวัตถุเดิม
• โมดูล time จะมีฟังก์ชันที่เกี่ยวข้องกับการจับเวลาและการประมวลผลเวลาใน Python
• โมดูล math จะมีฟังก์ชันทางคณิตศาสตร์ที่ช่วยให้เราสามารถทำงานกับค่าทางคณิตศาสตร์เช่น ค่าความสูงทางคณิตศาสตร์ หรือการทำงานกับฟังก์ชันทางคณิตศาสตร์อื่นๆ ในภาษา Python

from copy import deepcopy
import time
import math

ขั้นตอนที่ 2 กำหนดค่าตัวแปรแบบ string ให้กับตัวแปร
แต่ละตัวแปรจะมีข้อความของ ANSI escape code ที่ใช้สำหรับการควบคุมสีของตัวอักษรแสดงผลในเทอร์มินัล (terminal) หรือคอนโซล (console) ในสาธารณะสี โดย ANSI escape code เป็นรหัสพิเศษที่ถูกเพิ่มเข้ามาในข้อความ (string) เพื่อควบคุมคุณสมบัติต่างๆ ของการแสดงผลในเทอร์มินัล

• ansi_black = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีดำ
• ansi_red = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีแดง
• ansi_green = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีเขียว
• ansi_yellow = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีเหลือง
• ansi_blue = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีน้ำเงิน
• ansi_magenta = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีม่วงแดง
• ansi_cyan = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีเขียวเข้ม
• ansi_white = สำหรับการตั้งค่าสีของตัวอักษรเป็นสีขาว
• ansi_reset = สำหรับการรีเซ็ตค่าสีของตัวอักษรกลับไปเป็นค่าเริ่มต้น

ansi_black = "\u001b[30m"
ansi_red = "\u001b[31m"
ansi_green = "\u001b[32m"
ansi_yellow = "\u001b[33m"
ansi_blue = "\u001b[34m"
ansi_magenta = "\u001b[35m"
ansi_cyan = "\u001b[36m"
ansi_white = "\u001b[37m"
ansi_reset = "\u001b[0m"

ขั้นตอนที่ 3 การสร้างคลาส Node ที่มีคุณสมบัติต่าง ๆ

• board: พารามิเตอร์ที่รับค่าเป็นอาร์เรย์หรือโครงสร้างข้อมูลอื่น ๆ ที่เกี่ยวข้องกับการเก็บข้อมูลของสถานะหรือสถานะปัจจุบันของโหนด
• move: พารามิเตอร์ที่รับค่าเป็นการเคลื่อนย้ายหรือท่าทางที่ทำให้โหนดนี้ถูกสร้างขึ้น อาจเป็นการเคลื่อนย้ายหรือท่าทางที่ถูกทำให้โหนดนี้ถูกสร้างขึ้น
• parent: พารามิเตอร์ที่รับค่าเป็นโหนดที่เป็นโหนดก่อนหน้าที่เชื่อมโยงกับโหนดปัจจุบัน มักจะใช้ในการสร้างโครงสร้างข้อมูลแบบต้นไม้
• value: พารามิเตอร์ที่รับค่าเป็นค่าที่เกี่ยวข้องกับโหนดนี้ อาจเป็นค่าที่บ่งบอกคุณภาพหรือความสำคัญของโหนดนี้ > ฟังก์ชัน init ในคลาส Node ใช้สำหรับกำหนดค่าเริ่มต้นให้กับแต่ละตัวแปรที่เป็นสมาชิกของคลาส Node โดยให้รับค่าพารามิเตอร์ต่าง ๆ เพื่อกำหนดค่าให้กับตัวแปรแต่ละตัว ในที่นี้คือ board, move, parent, และ value ที่ถูกส่งเข้ามาในพารามิเตอร์ของฟังก์ชัน init ของคลาส Node

class Node:
    def __init__(self, board, move=None, parent=None, value=None):
        self.board = board
        self.value = value
        self.move = move
        self.parent = parent

ขั้นตอนที่ 4 กำหนดเงื่อนไขในการสร้างโหนดลูกตามกฎเกม Checkers

def get_children(self, minimizing_player, mandatory_jumping):
        current_state = deepcopy(self.board)
        available_moves = []
        children_states = []
        big_letter = ""
        queen_row = 0
        if minimizing_player is True:
            available_moves = Checkers.find_available_moves(current_state, mandatory_jumping)
            big_letter = "C"
            queen_row = 7
        else:
            available_moves = Checkers.find_player_available_moves(current_state, mandatory_jumping)
            big_letter = "B"
            queen_row = 0
        for i in range(len(available_moves)):
            old_i = available_moves[i][0]
            old_j = available_moves[i][1]
            new_i = available_moves[i][2]
            new_j = available_moves[i][3]
            state = deepcopy(current_state)
            Checkers.make_a_move(state, old_i, old_j, new_i, new_j, big_letter, queen_row)
            children_states.append(Node(state, [old_i, old_j, new_i, new_j]))
        return children_states
    def set_value(self, value):
        self.value = value
    def get_value(self):
        return self.value
    def get_board(self):
        return self.board
    def get_parent(self):
        return self.parent
    def set_parent(self, parent):
        self.parent = parent

ขั้นตอนที่ 5 การสร้างคลาส Checkers
คลาส Checkers ที่มีตัวแปรและเมธอดเพื่อเก็บและจัดการตารางหมากฮอส, ตัวเลขและสถานะของเกมหมากฮอส รวมถึงเมธอดในการกำหนดตำแหน่งเริ่มต้นของหมากของคอมพิวเตอร์และผู้เล่นบนตารางหมากฮอส

• self.matrix: เป็นรายการที่มีสมาชิกย่อย 8 รายการซึ่งแต่ละรายการมีสมาชิกย่อย 8 ตัวแปร แทนตารางหมากฮอส โดยแต่ละตัวแปรเก็บข้อมูลเป็นสตริงแบบ "---" หรือขีดกลาง แสดงถึงช่องว่างในตารางหมากฮอส
• self.player_turn: เป็นตัวแปรบูลีน (boolean) ที่บอกว่าเป็นตาของผู้เล่น (True) หรือไม่ (False)
• self.computer_pieces: เป็นตัวแปรจำนวนเต็มที่เก็บจำนวนเหล่าหมากของคอมพิวเตอร์
• self.player_pieces: เป็นตัวแปรจำนวนเต็มที่เก็บจำนวนเหล่าหมากของผู้เล่น
• self.available_moves: เป็นรายการที่เก็บเคลื่อนที่ที่เป็นไปได้ของหมากที่ถือครองอยู่ในรูปแบบของตัวเลขแถวและหลัก
• self.mandatory_jumping: เป็นตัวแปรบูลีนที่บอกว่าตอนนี้เกิดการกระโดดบังคับของหมากหรือไม่
• self.position_computer(): เป็นเมธอดที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้นของหมากของคอมพิวเตอร์บนตารางหมากฮอส
• self.position_player(): เป็นเมธอดที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้นของหมากของผู้เล่นบนตารางหมากฮอส

class Checkers:
    def __init__(self):
        self.matrix = [[], [], [], [], [], [], [], []]
        self.player_turn = True
        self.computer_pieces = 12
        self.player_pieces = 12
        self.available_moves = []
        self.mandatory_jumping = False
        for row in self.matrix:
            for i in range(8):
                row.append("---")
        self.position_computer()
        self.position_player()

ขั้นตอนที่ 6 การทำงาน position_computer
เมธอด position_computer() ในคลาส Checkers ใช้ในการกำหนดตำแหน่งของหมากของคอมพิวเตอร์บนตารางหมากฮอส โดยกำหนดค่า "c" ตามด้วยตำแหน่งแนวแกน X และ Y ของตาราง สำหรับแถวที่ 0 ถึงแถวที่ 2 และหมากจะถือครองตำแหน่งที่มีค่าผลรวมของแนวแกน X และ Y เป็นเลขคี่บนตารางหมากฮอส โดยให้แต่ละตำแหน่งแสดงสัญลักษณ์ "c" ตามด้วยตำแหน่งแนวแกน X และ Y ของตารางในรูปแบบของสตริงเช่น "cXY".

def position_computer(self):
        for i in range(3):
            for j in range(8):
                if (i + j) % 2 == 1:
                    self.matrix[i][j] = ("c" + str(i) + str(j))

ขั้นตอนที่ 7 การทำงาน position_player
เมธอด position_player() ในคลาส Checkers ใช้ในการกำหนดตำแหน่งของหมากของผู้เล่นบนตารางหมากฮอส โดยกำหนดค่า "b" ตามด้วยตำแหน่งแนวแกน X และ Y ของตาราง สำหรับแถวที่ 5 ถึงแถวที่ 7 และหมากจะถือครองตำแหน่งที่มีค่าผลรวมของแนวแกน X และ Y เป็นเลขคี่บนตารางหมากรุก โดยให้แต่ละตำแหน่งแสดงสัญลักษณ์ "b" ตามด้วยตำแหน่งแนวแกน X และ Y ของตารางในรูปแบบของสตริงเช่น "bXY".

def position_player(self):
        for i in range(5, 8, 1):
            for j in range(8):
                if (i + j) % 2 == 1:
                    self.matrix[i][j] = ("b" + str(i) + str(j))

ขั้นตอนที่ 8 การทำงาน print_matrix
เมธอด print_matrix() ในคลาส Checkers ใช้ในการแสดงตารางหมากฮอสที่ถือครองอยู่ในปัจจุบัน โดยแสดงหมากแต่ละตัวด้วยสัญลักษณ์ที่ระบุผู้เล่น (c หรือ b) และตำแหน่งหมากในแนวแกน X และ Y ของตาราง พร้อมกับตัวอักษร "|" เพื่อแยกแต่ละคอลัมน์ของตาราง.

def print_matrix(self):
        i = 0
        print()
        for row in self.matrix:
            print(i, end="  |")
            i += 1
            for elem in row:
                print(elem, end=" ")
            print()
        print()
        for j in range(8):
            if j == 0:
                j = "     0"
            print(j, end="   ")
        print("\n")

ขั้นตอนที่ 9 การทำงาน get_player_input
เมธอด get_player_input(self) เป็นเมธอดในการรับค่า input จากผู้เล่นเพื่อทำการเล่นเกมหมากฮอส โดยมีขั้นตอนการทำงานดังนี้:

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

def get_player_input(self):
        available_moves = Checkers.find_player_available_moves(self.matrix, self.mandatory_jumping)
        if len(available_moves) == 0:
            if self.computer_pieces > self.player_pieces:
                print(
                    ansi_red + "You have no moves left, and you have fewer pieces than the computer.YOU LOSE!" + ansi_reset)
                exit()
            else:
                print(ansi_yellow + "You have no available moves.\nGAME ENDED!" + ansi_reset)
                exit()
        self.player_pieces = 0
        self.computer_pieces = 0
        while True:

            coord1 = input("Which piece[i,j]: ")
            if coord1 == "":
                print(ansi_cyan + "Game ended!" + ansi_reset)
                exit()
            elif coord1 == "s":
                print(ansi_cyan + "You surrendered.\nCoward." + ansi_reset)
                exit()
            coord2 = input("Where to[i,j]:")
            if coord2 == "":
                print(ansi_cyan + "Game ended!" + ansi_reset)
                exit()
            elif coord2 == "s":
                print(ansi_cyan + "You surrendered.\nCoward." + ansi_reset)
                exit()
            old = coord1.split(",")
            new = coord2.split(",")

            if len(old) != 2 or len(new) != 2:
                print(ansi_red + "Illegal input" + ansi_reset)
            else:
                old_i = old[0]
                old_j = old[1]
                new_i = new[0]
                new_j = new[1]
                if not old_i.isdigit() or not old_j.isdigit() or not new_i.isdigit() or not new_j.isdigit():
                    print(ansi_red + "Illegal input" + ansi_reset)
                else:
                    move = [int(old_i), int(old_j), int(new_i), int(new_j)]
                    if move not in available_moves:
                        print(ansi_red + "Illegal move!" + ansi_reset)
                    else:
                        Checkers.make_a_move(self.matrix, int(old_i), int(old_j), int(new_i), int(new_j), "B", 0)
                        for m in range(8):
                            for n in range(8):
                                if self.matrix[m][n][0] == "c" or self.matrix[m][n][0] == "C":
                                    self.computer_pieces += 1
                                elif self.matrix[m][n][0] == "b" or self.matrix[m][n][0] == "B":
                                    self.player_pieces += 1
                        break

ขั้นตอนที่ 10 การทำงาน find_available_moves
เมธอด find_available_moves เป็น @staticmethod ที่อยู่ในคลาส Checkers และใช้ในการหาทางเดินหรือการกระโดดที่สามารถทำได้ในเกมหมากฮอส โดยมีพารามิเตอร์ board และ mandatory_jumping คืนค่าเป็นรายการของทางเดินหรือกระโดดที่สามารถทำได้ตามสถานะปัจจุบันของกระดานเกมหมากฮอส โดยพิจารณาตำแหน่งของเหมืองบนกระดาน และตรวจสอบเงื่อนไข mandatory_jumping เพื่อคืนค่าทางเดินหรือกระโดดที่จำเป็น (mandatory) หากมี ถ้าไม่มีจะคืนค่าทางเดินทั้งหมดที่เป็นไปได้

@staticmethod
    def find_available_moves(board, mandatory_jumping):
        available_moves = []
        available_jumps = []
        for m in range(8):
            for n in range(8):
                if board[m][n][0] == "c":
                    if Checkers.check_moves(board, m, n, m + 1, n + 1):
                        available_moves.append([m, n, m + 1, n + 1])
                    if Checkers.check_moves(board, m, n, m + 1, n - 1):
                        available_moves.append([m, n, m + 1, n - 1])
                    if Checkers.check_jumps(board, m, n, m + 1, n - 1, m + 2, n - 2):
                        available_jumps.append([m, n, m + 2, n - 2])
                    if Checkers.check_jumps(board, m, n, m + 1, n + 1, m + 2, n + 2):
                        available_jumps.append([m, n, m + 2, n + 2])
                elif board[m][n][0] == "C":
                    if Checkers.check_moves(board, m, n, m + 1, n + 1):
                        available_moves.append([m, n, m + 1, n + 1])
                    if Checkers.check_moves(board, m, n, m + 1, n - 1):
                        available_moves.append([m, n, m + 1, n - 1])
                    if Checkers.check_moves(board, m, n, m - 1, n - 1):
                        available_moves.append([m, n, m - 1, n - 1])
                    if Checkers.check_moves(board, m, n, m - 1, n + 1):
                        available_moves.append([m, n, m - 1, n + 1])
                    if Checkers.check_jumps(board, m, n, m + 1, n - 1, m + 2, n - 2):
                        available_jumps.append([m, n, m + 2, n - 2])
                    if Checkers.check_jumps(board, m, n, m - 1, n - 1, m - 2, n - 2):
                        available_jumps.append([m, n, m - 2, n - 2])
                    if Checkers.check_jumps(board, m, n, m - 1, n + 1, m - 2, n + 2):
                        available_jumps.append([m, n, m - 2, n + 2])
                    if Checkers.check_jumps(board, m, n, m + 1, n + 1, m + 2, n + 2):
                        available_jumps.append([m, n, m + 2, n + 2])
        if mandatory_jumping is False:
            available_jumps.extend(available_moves)
            return available_jumps
        elif mandatory_jumping is True:
            if len(available_jumps) == 0:
                return available_moves
            else:
                return available_jumps

ขั้นตอนที่ 11 การทำงาน check_jumps
เมธอด check_jumps เป็น @staticmethod ที่อยู่ในคลาส Checkers และใช้ในการตรวจสอบเงื่อนไขสำหรับกระโดดในเกมหมากฮอส โดยตรวจสอบค่าตำแหน่งใหม่ที่ต้องการกระโดดไปว่าเป็นตำแหน่งที่ถูกต้องหรือไม่ ซึ่งรวมถึงตรวจสอบเงื่อนไขต่างๆ เช่น ตำแหน่งใหม่อยู่ในช่วงที่ถูกต้องของกระดาน (0-7) และไม่มีเหมืองอยู่บนตำแหน่งแหล่งผ่านทาง (via_i, via_j) ที่ว่างเปล่า และตรวจสอบเงื่อนไขต่างๆ ที่เกี่ยวกับแผ่นเหมือง (C/c) และแผ่นธรรมดา (b/B) ที่ต้องปฏิบัติ

@staticmethod
    def check_jumps(board, old_i, old_j, via_i, via_j, new_i, new_j):
        if new_i > 7 or new_i < 0:
            return False
        if new_j > 7 or new_j < 0:
            return False
        if board[via_i][via_j] == "---":
            return False
        if board[via_i][via_j][0] == "C" or board[via_i][via_j][0] == "c":
            return False
        if board[new_i][new_j] != "---":
            return False
        if board[old_i][old_j] == "---":
            return False
        if board[old_i][old_j][0] == "b" or board[old_i][old_j][0] == "B":
            return False
        return True

ขั้นตอนที่ 12 การทำงาน check_moves
เมธอด check_moves เป็น @staticmethod ที่อยู่ในคลาส Checkers และใช้ในการตรวจสอบเงื่อนไขสำหรับการเดินทางในเกมหมากฮอส โดยตรวจสอบค่าตำแหน่งใหม่ที่ต้องการเดินทางไปว่าเป็นตำแหน่งที่ถูกต้องหรือไม่ ซึ่งรวมถึงตรวจสอบเงื่อนไขต่างๆ เช่น ตำแหน่งใหม่อยู่ในช่วงที่ถูกต้องของกระดาน (0-7) และไม่มีแผ่นที่ตำแหน่งปลายทาง (new_i, new_j) ที่ไม่ว่างเปล่า และตรวจสอบเงื่อนไขต่างๆ ที่เกี่ยวกับแผ่นธรรมดา (b/B) ที่ต้องปฏิบัติ และตรวจสอบเงื่อนไขเกี่ยวกับแผ่นที่ต้นทาง (old_i, old_j) ที่ไม่เป็นแผ่นธรรมดา

@staticmethod
    def check_moves(board, old_i, old_j, new_i, new_j):

        if new_i > 7 or new_i < 0:
            return False
        if new_j > 7 or new_j < 0:
            return False
        if board[old_i][old_j] == "---":
            return False
        if board[new_i][new_j] != "---":
            return False
        if board[old_i][old_j][0] == "b" or board[old_i][old_j][0] == "B":
            return False
        if board[new_i][new_j] == "---":
            return True

ขั้นตอนที่ 13 การทำงาน calculate_heuristics
เมธอด calculate_heuristics เป็น @staticmethod ที่อยู่ในคลาส Checkers ที่ใช้สำหรับคำนวณคะแนนเชิงเสมอภาพสำหรับสถานะบอร์ดที่กำหนดเข้ามา คะแนนเชิงเสมอภาพนี้ถูกคำนวณขึ้นอยู่กับเงื่อนไขและค่าที่กำหนดให้กับองค์ประกอบต่างๆ ของบอร์ด

• คำนวณ mine และ opp คือจำนวนของชิปที่เป็นของผู้เล่นและของคู่ต่อสู้ตามลำดับ
• สำหรับแต่ละชิปบนบอร์ด:
  • กำหนดคะแนนให้กับแต่ละชนิดของชิป ตามเงื่อนไขที่กำหนด
  • เพิ่มคะแนนถ้าชิปอยู่ที่ขอบของบอร์ด
  • ตรวจสอบเงื่อนไขและเพิ่มหรือลดคะแนนตามที่กำหนดให้กับชิปและตำแหน่งบนบอร์ดที่เกี่ยวข้อง
• คืนค่าผลรวมของคะแนนที่คำนวณขึ้นมาพร้อมกับผลต่างระหว่างจำนวนชิปของผู้เล่นและคู่ต่อสู้ที่คูณด้วยค่าคงที่ 1000

@staticmethod
    def calculate_heuristics(board):
        result = 0
        mine = 0
        opp = 0
        for i in range(8):
            for j in range(8):
                if board[i][j][0] == "c" or board[i][j][0] == "C":
                    mine += 1

                    if board[i][j][0] == "c":
                        result += 5
                    if board[i][j][0] == "C":
                        result += 10
                    if i == 0 or j == 0 or i == 7 or j == 7:
                        result += 7
                    if i + 1 > 7 or j - 1 < 0 or i - 1 < 0 or j + 1 > 7:
                        continue
                    if (board[i + 1][j - 1][0] == "b" or board[i + 1][j - 1][0] == "B") and board[i - 1][
                        j + 1] == "---":
                        result -= 3
                    if (board[i + 1][j + 1][0] == "b" or board[i + 1][j + 1] == "B") and board[i - 1][j - 1] == "---":
                        result -= 3
                    if board[i - 1][j - 1][0] == "B" and board[i + 1][j + 1] == "---":
                        result -= 3

                    if board[i - 1][j + 1][0] == "B" and board[i + 1][j - 1] == "---":
                        result -= 3
                    if i + 2 > 7 or i - 2 < 0:
                        continue
                    if (board[i + 1][j - 1][0] == "B" or board[i + 1][j - 1][0] == "b") and board[i + 2][
                        j - 2] == "---":
                        result += 6
                    if i + 2 > 7 or j + 2 > 7:
                        continue
                    if (board[i + 1][j + 1][0] == "B" or board[i + 1][j + 1][0] == "b") and board[i + 2][
                        j + 2] == "---":
                        result += 6

                elif board[i][j][0] == "b" or board[i][j][0] == "B":
                    opp += 1

        return result + (mine - opp) * 1000

ขั้นตอนที่ 14 การทำงาน find_player_available_moves
เมธอด find_player_available_moves เป็น @staticmethod ที่อยู่ในคลาส Checkers ใช้สำหรับค้นหาท่าเดินที่เป็นไปได้สำหรับผู้เล่นในเกมหมากฮอส (Checkers) โดยอิงจากสถานะบอร์ดที่กำหนดให้ ฟังก์ชันนี้จะคืนค่าอาเรย์ของท่าเดินที่เป็นไปได้ทั้งหมด แยกเป็นท่าเดินธรรมดาและท่ากระโดดที่เป็นไปได้ โดยขึ้นอยู่กับสถานะของการกระโดดบังเอิญที่ถูกกำหนดให้ (mandatory_jumping) ซึ่งถ้ามีการกระโดดบังเอิญที่เป็นไปได้ (available_jumps) จะถูกนำมาใช้ในการคืนค่าก่อน หากไม่มีการกระโดดบังเอิญ หรือถูกกำหนดให้ต้องกระโดดบังเอิญแต่ไม่มีท่ากระโดดบังเอิญที่เป็นไปได้ จะคืนค่าท่าเดินธรรมดา (available_moves) แทน ฟังก์ชันนี้สามารถใช้ในการค้นหาท่าเดินที่เป็นไปได้สำหรับผู้เล่นในเกมหมากฮอสได้ตามสถานะของบอร์ดและการกระโดดที่ถูกกำหนดให้ โดยจะคืนค่าอาเรย์ของท่าเดินที่เป็นไปได้ทั้งหมด แยกเป็นท่าเดินธรรมดาและท่ากระโดดที่เป็นไปได้

@staticmethod
    def find_player_available_moves(board, mandatory_jumping):
        available_moves = []
        available_jumps = []
        for m in range(8):
            for n in range(8):
                if board[m][n][0] == "b":
                    if Checkers.check_player_moves(board, m, n, m - 1, n - 1):
                        available_moves.append([m, n, m - 1, n - 1])
                    if Checkers.check_player_moves(board, m, n, m - 1, n + 1):
                        available_moves.append([m, n, m - 1, n + 1])
                    if Checkers.check_player_jumps(board, m, n, m - 1, n - 1, m - 2, n - 2):
                        available_jumps.append([m, n, m - 2, n - 2])
                    if Checkers.check_player_jumps(board, m, n, m - 1, n + 1, m - 2, n + 2):
                        available_jumps.append([m, n, m - 2, n + 2])
                elif board[m][n][0] == "B":
                    if Checkers.check_player_moves(board, m, n, m - 1, n - 1):
                        available_moves.append([m, n, m - 1, n - 1])
                    if Checkers.check_player_moves(board, m, n, m - 1, n + 1):
                        available_moves.append([m, n, m - 1, n + 1])
                    if Checkers.check_player_jumps(board, m, n, m - 1, n - 1, m - 2, n - 2):
                        available_jumps.append([m, n, m - 2, n - 2])
                    if Checkers.check_player_jumps(board, m, n, m - 1, n + 1, m - 2, n + 2):
                        available_jumps.append([m, n, m - 2, n + 2])
                    if Checkers.check_player_moves(board, m, n, m + 1, n - 1):
                        available_moves.append([m, n, m + 1, n - 1])
                    if Checkers.check_player_jumps(board, m, n, m + 1, n - 1, m + 2, n - 2):
                        available_jumps.append([m, n, m + 2, n - 2])
                    if Checkers.check_player_moves(board, m, n, m + 1, n + 1):
                        available_moves.append([m, n, m + 1, n + 1])
                    if Checkers.check_player_jumps(board, m, n, m + 1, n + 1, m + 2, n + 2):
                        available_jumps.append([m, n, m + 2, n + 2])
        if mandatory_jumping is False:
            available_jumps.extend(available_moves)
            return available_jumps
        elif mandatory_jumping is True:
            if len(available_jumps) == 0:
                return available_moves
            else:
                return available_jumps

ขั้นตอนที่ 15 การทำงาน check_player_moves
เมธอด check_player_moves เป็น @staticmethod ที่อยู่ในคลาส Checkers ตรวจสอบความถูกต้องของการเลื่อนหรือเคลื่อนย้ายหมากในเกมตาม (checkers) โดยมีเงื่อนไขต่าง ๆ เช่น ตำแหน่งปลายทางต้องไม่เกินขอบเขตของกระดานเกม (8x8), ตำแหน่งเริ่มต้นและปลายทางต้องไม่มีหมากอยู่แล้ว, ชนิดของหมากเรือนต้งไม่ใช่หมากแรกและหมากแรกตัวใหม่ที่ถูกโปรโมชัน (king) และตำแหน่งปลายทางต้องเป็นช่องว่าง เมื่อทุกเงื่อนไขถูกต้อง ฟังก์ชันจะคืนค่า True ให้กับการเคลื่อนย้ายหมาก ถ้าเงื่อนไขใดเงื่อนไขหนึ่งไม่ถูกต้อง ฟังก์ชันจะคืนค่า False ให้กับการเคลื่อนย้ายหมาก

@staticmethod
    def check_player_moves(board, old_i, old_j, new_i, new_j):
        if new_i > 7 or new_i < 0:
            return False
        if new_j > 7 or new_j < 0:
            return False
        if board[old_i][old_j] == "---":
            return False
        if board[new_i][new_j] != "---":
            return False
        if board[old_i][old_j][0] == "c" or board[old_i][old_j][0] == "C":
            return False
        if board[new_i][new_j] == "---":
            return True

ขั้นตอนที่ 16 การทำงาน check_player_jumps
เมธอด check_player_jumps เป็น @staticmethod ที่อยู่ในคลาส Checkers สำหรับตรวจสอบความถูกต้องของการกระโดดหรือเคลื่อนย้ายหมากในเกมตาม (checkers) โดยมีเงื่อนไขต่าง ๆ เช่น ตำแหน่งปลายทางต้องไม่เกินขอบเขตของกระดานเกม (8x8), ตำแหน่งแฟล็ก (via) ต้องไม่ว่างเปล่า, ชนิดของหมากเรือนต้องไม่ใช่หมากแดง (b) หรือหมากเรือนแดง (B), ตำแหน่งปลายทางต้องเป็นช่องว่าง, ตำแหน่งเริ่มต้นต้องไม่ว่างเปล่า, ชนิดของหมากเรือนต้องไม่ใช่หมากดำ (c) หรือหมากเรือนดำ (C) และเงื่อนไขอื่น ๆ ถูกต้อง ฟังก์ชันจะคืนค่า True ให้กับการเคลื่อนย้ายหมาก ถ้าเงื่อนไขใดเงื่อนไขหนึ่งไม่ถูกต้อง ฟังก์ชันจะคืนค่า False ให้กับการเคลื่อนย้ายหมาก

@staticmethod
    def check_player_jumps(board, old_i, old_j, via_i, via_j, new_i, new_j):
        if new_i > 7 or new_i < 0:
            return False
        if new_j > 7 or new_j < 0:
            return False
        if board[via_i][via_j] == "---":
            return False
        if board[via_i][via_j][0] == "B" or board[via_i][via_j][0] == "b":
            return False
        if board[new_i][new_j] != "---":
            return False
        if board[old_i][old_j] == "---":
            return False
        if board[old_i][old_j][0] == "c" or board[old_i][old_j][0] == "C":
            return False
        return True

ขั้นตอนที่ 17 การทำงาน evaluate_states
ฟังก์ชัน evaluate_states() ใช้ในการประเมินสถานะปัจจุบันของเกมหมากฮอสและเลือกทำตาสำหรับคอมพิวเตอร์ โดยให้คะแนนให้กับท่าเดินแต่ละท่าและเก็บไว้ในพจนานุกรม แล้วเลือกท่าเดินที่มีคะแนนสูงสุดให้คอมพิวเตอร์เล่น พร้อมทั้งแสดงผลเวลาที่ใช้ในการประมวลผล และตรวจสอบสถานะเกมว่าเกมจบหรือไม่ ดังนั้นสรุปได้ว่าฟังก์ชันนี้เป็นส่วนสำคัญในกระบวนการเล่นเกมหมากฮอสของคอมพิวเตอร์.

def evaluate_states(self):
        t1 = time.time()
        current_state = Node(deepcopy(self.matrix))

        first_computer_moves = current_state.get_children(True, self.mandatory_jumping)
        if len(first_computer_moves) == 0:
            if self.player_pieces > self.computer_pieces:
                print(
                    ansi_yellow + "Computer has no available moves left, and you have more pieces left.\nYOU WIN!" + ansi_reset)
                exit()
            else:
                print(ansi_yellow + "Computer has no available moves left.\nGAME ENDED!" + ansi_reset)
                exit()
        dict = {}
        for i in range(len(first_computer_moves)):
            child = first_computer_moves[i]
            value = Checkers.minimax(child.get_board(), 4, -math.inf, math.inf, False, self.mandatory_jumping)
            dict[value] = child
        if len(dict.keys()) == 0:
            print(ansi_green + "Computer has cornered itself.\nYOU WIN!" + ansi_reset)
            exit()
        new_board = dict[max(dict)].get_board()
        move = dict[max(dict)].move
        self.matrix = new_board
        t2 = time.time()
        diff = t2 - t1
        print("Computer has moved (" + str(move[0]) + "," + str(move[1]) + ") to (" + str(move[2]) + "," + str(
            move[3]) + ").")
        print("It took him " + str(diff) + " seconds.")

ขั้นตอนที่ 18 การทำงาน minimax
ฟังก์ชัน minimax() เป็นฟังก์ชันที่ใช้ในกระบวนการคำนวณคะแนนของท่าเดินแต่ละท่าในเกมเช็คเกอร์ โดยใช้อัลกอริทึม Minimax ซึ่งเป็นอัลกอริทึมที่ใช้ในการคำนวณคะแนนสำหรับการตัดสินใจในเกมที่มีผู้เล่นคนเดียวและคนตรงข้ามเกี่ยวข้อง ฟังก์ชันนี้รับพารามิเตอร์เข้ามาเพื่อกำหนดความลึกในการคำนวณ (depth) และค่า alpha และ beta ในกระบวนการตัดสินใจแบบ Alpha-Beta Pruning เพื่อเพิ่มประสิทธิภาพในการคำนวณ และให้คะแนนกับท่าเดินแต่ละท่าด้วยฟังก์ชัน Checkers.calculate_heuristics() ซึ่งคำนวณคะแนนเพื่อประเมินความน่าสนใจของท่าเดินนั้น และคืนค่าคะแนนที่คำนวณได้ให้กับท่าเดินนั้นๆ โดยใช้การตัดสินใจของผู้เล่นที่กำลังตัดสินใจ (maximizing_player) และค่า alpha, beta ในกระบวนการตัดสินใจเพื่อให้กับผู้เล่นที่กำลังไม่ใช่ผู้ตัดสินใจ (maximizing_player) ซึ่งจะนำไปใช้ในกระบวนการตัดสินใจแบบ Alpha-Beta Pruning เพื่อลดการคำนวณที่ไม่จำเป็น และให้คะแนนที่คำนวณได้ให้กับท่าเดินนั้นๆ ในท้ายที่สุดจะคืนค่าคะแนนที่คำนวณได้ให้กับท่าเดินนั้น ๆ เพื่อใช้ในกระบวนการตัดสินใจของอัลกอริทึม

@staticmethod
    def minimax(board, depth, alpha, beta, maximizing_player, mandatory_jumping):
        if depth == 0:
            return Checkers.calculate_heuristics(board)
        current_state = Node(deepcopy(board))
        if maximizing_player is True:
            max_eval = -math.inf
            for child in current_state.get_children(True, mandatory_jumping):
                ev = Checkers.minimax(child.get_board(), depth - 1, alpha, beta, False, mandatory_jumping)
                max_eval = max(max_eval, ev)
                alpha = max(alpha, ev)
                if beta <= alpha:
                    break
            current_state.set_value(max_eval)
            return max_eval
        else:
            min_eval = math.inf
            for child in current_state.get_children(False, mandatory_jumping):
                ev = Checkers.minimax(child.get_board(), depth - 1, alpha, beta, True, mandatory_jumping)
                min_eval = min(min_eval, ev)
                beta = min(beta, ev)
                if beta <= alpha:
                    break
            current_state.set_value(min_eval)
            return min_eval

ขั้นตอนที่ 19 การทำงาน make_a_move
เมธอด make_a_move() สำหรับอัปเดตสถานะบอร์ดเกมขึ้นอยู่กับท่าเล่นของผู้เล่น

@staticmethod
    def make_a_move(board, old_i, old_j, new_i, new_j, big_letter, queen_row):
        letter = board[old_i][old_j][0]
        i_difference = old_i - new_i
        j_difference = old_j - new_j
        if i_difference == -2 and j_difference == 2:
            board[old_i + 1][old_j - 1] = "---"

        elif i_difference == 2 and j_difference == 2:
            board[old_i - 1][old_j - 1] = "---"

        elif i_difference == 2 and j_difference == -2:
            board[old_i - 1][old_j + 1] = "---"

        elif i_difference == -2 and j_difference == -2:
            board[old_i + 1][old_j + 1] = "---"

        if new_i == queen_row:
            letter = big_letter
        board[old_i][old_j] = "---"
        board[new_i][new_j] = letter + str(new_i) + str(new_j)

ขั้นตอนที่ 20 การทำงาน play
เมธอด play() สำหรับเริ่มเกมหมากฮอสและเล่นตาละครั้งให้กับผู้เล่นและคอมพิวเตอร์ตามลำดับ

    def play(self):
        print(ansi_cyan + "##### WELCOME TO CHECKERS ####" + ansi_reset)
        print("\nSome basic rules:")
        print("1.You enter the coordinates in the form i,j.")
        print("2.You can quit the game at any time by pressing enter.")
        print("3.You can surrender at any time by pressing 's'.")
        print("Now that you've familiarized yourself with the rules, enjoy!")
        while True:
            answer = input("\nFirst, we need to know, is jumping mandatory?[Y/n]: ")
            if answer == "Y" or answer == "y":
                self.mandatory_jumping = True
                break
            elif answer == "N" or answer == "n":
                self.mandatory_jumping = False
                break
            elif answer == "":
                print(ansi_cyan + "Game ended!" + ansi_reset)
                exit()
            elif answer == "s":
                print(ansi_cyan + "You've surrendered before the game even started.\nPathetic." + ansi_reset)
                exit()
            else:
                print(ansi_red + "Illegal input!" + ansi_reset)
        while True:
            self.print_matrix()
            if self.player_turn is True:
                print(ansi_cyan + "\nPlayer's turn." + ansi_reset)
                self.get_player_input()
            else:
                print(ansi_cyan + "Computer's turn." + ansi_reset)
                print("Thinking...")
                self.evaluate_states()
            if self.player_pieces == 0:
                self.print_matrix()
                print(ansi_red + "You have no pieces left.\nYOU LOSE!" + ansi_reset)
                exit()
            elif self.computer_pieces == 0:
                self.print_matrix()
                print(ansi_green + "Computer has no pieces left.\nYOU WIN!" + ansi_reset)
                exit()
            elif self.computer_pieces - self.player_pieces == 7:
                wish = input("You have 7 pieces fewer than your opponent.Do you want to surrender?")
                if wish == "" or wish == "yes":
                    print(ansi_cyan + "Coward." + ansi_reset)
                    exit()
            self.player_turn = not self.player_turn

ขั้นตอนที่ 21 การเรียกใช้คลาส Checkers และเริ่มเกม
โดยเรียกใช้เมธอด play() ภายในคลาส Checkers เพื่อให้ผู้เล่นเริ่มเล่นเกมหมากฮอสและทำตาของตัวเองหรือคอมพิวเตอร์ตามลำดับ โดยเช็คเงื่อนไข if name == 'main': ก่อนที่จะเรียกใช้คลาส Checkers และเริ่มการเล่นเกม ซึ่งคำสั่งที่อยู่ภายในบล็อก if name == 'main': จะถูกทำงานเฉพาะเมื่อไฟล์ถูกเรียกใช้โดยตรง และไม่ถูกเรียกใช้เป็นโมดูลจากไฟล์อื่นๆ ในโปรแกรม Python

if __name__ == '__main__':
    checkers = Checkers()
    checkers.play()

ตัวอย่างผลที่ได้จาก code

เมื่อรันออกมาแล้วจะแสดงกฎเบื้องต้นของการเล่นเกมนี้ ทั้งหมด 3 ข้อดังนี้
1.คุณป้อนพิกัดในรูปแบบ i,j (row,col)
2.คุณสามารถออกจากเกมได้ตลอดเวลาโดยกด Enter
3.คุณสามารถยอมจำนนเมื่อใดก็ได้โดยกด 's'

ตัวอย่างการเล่น

เมื่อเริ่มเกม ตัวหมากของเรานั้นจะขึ้นต้นด้วย "bxx" # x คือตำแหน่งของ b ใน row,col (ไว้สำหรับการเล่นที่ง่ายขึ้น)

ตัวอย่าง : ถ้าต้องการเลื่อน b50 ไปยังที่ว่างที่วงกลมไว้ ดังนี้
Which piece[i,j]: 5,0 #ตำแหน่งของหมากที่จะเลื่อน
Where to[i,j]: 4,1 #ตำแหน่งเป้าหมายของหมาก

ตัวอย่างผลที่ได้
b50 จะถูกเลื่อนไปยังตำแหน่งที่เราเขียนลงไป กลายเป็น b41

ขั้นตอนต่อไป คอมพิวเตอร์จะทำการเล่นตัวหมากที่ขึ้นต้นด้วย "cxx"
และจะถูกส่งมาให้เราที่เป็น Player เล่นอีกครั้ง สลับกันไปมา จนกว่าจะมีฝั่งใดชนะ

สรุปผล

เกมหมากฮอส (Checkers) ใช้แนวคิดของ Minimax และ Alpha-Beta Pruning เพื่อปรับปรุงประสิทธิภาพในการวิเคราะห์สถานการณ์และการตัดสินใจในการเล่นของคอมพิวเตอร์ในเกมนี้

Minimax Algorithm:
เป็นวิธีการค้นหาแบบต้นแบบ (search algorithm) ที่ใช้ในการคำนวณคะแนนความคุ้มค่า (utility) ของสถานะเกมแต่ละตา โดยการทำนายทุกทางเลือกที่เป็นไปได้และหาทางเดินที่ดีที่สุดสำหรับผู้เล่น และทางเลือกที่แย่ที่สุดสำหรับคู่แข่ง แต่คำนวณทุกทางเลือกที่เป็นไปได้อาจใช้เวลานานมากเมื่อมีจำนวนทางเลือกมาก

Alpha-Beta Pruning:
Alpha-Beta Pruning เป็นเทคนิคในการปรับปรุงประสิทธิภาพของ Minimax โดยการตัดสาขาของต้นแบบที่ไม่จำเป็นต้องคำนวณเพื่อลดเวลาที่ใช้ในการค้นหา โดยประเมินคะแนนที่ดีที่สุด (best score) ที่เป็นไปได้ในทางเดียวกันสำหรับกลุ่มของตาที่ค้นหา และกำหนดค่า Alpha และ Beta ให้คอยตัดสาขาที่ไม่เป็นไปได้ทันทีเมื่อไม่ต้องการคำนวณเพิ่มเติม ทำให้ลดจำนวนการคำนวณที่ไม่จำเป็นลงและเพิ่มประสิทธิภาพในการค้นหา

การใช้ Minimax และ Alpha-Beta Pruning ในเกมหมากฮอสช่วยให้คอมพิวเตอร์สามารถวิเคราะห์สถานการณ์และตัดสินใจในการเล่น

ตัวอย่างโค้ดเกมหมากฮอสทั้งหมด

Github : Checker-Game
Colab : Checker-Game

References
how to play : https://th.wukihow.com/wiki/Play-Checkers
Code : https://github.com/dimitrijekaranfilovic/checkers
Img : https://www.youtube.com/watch?v=l-hh51ncgDI
: https://solitaired.com/guides/how-to-play-play-checkers