วิธีสร้างเกม Tic-Tac-Toe โดยใช้ Python

เกม Tic-Tac-Toe คือเกมอะไร?
เกม Tic-Tac-Toe หรือเกม OX ที่เรานั้นรู้จักกันนั้นเอง เป็นเกมแบบ turn-based ที่ต้องมีผู้เล่นสองคนเล่นกันเองและผลัดกันเล่น จนกว่าจะมีฝ่ายใดฝ่ายหนึ่งชนะ ตัวอย่างของเกมประเภทนี้ ได้แก่ Tic-Tac-Toe, Backgammon, Mancala, Chess และ Connect 4

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับ Algorithm ของ Random Game, Minimax Game และ Alpha-Beta Pruning Game ซึ่ง algorithm ที่กล่าวมานั้นมีความแตกต่างกัน ดังนั้นเราจะมาดูกันว่าเราจะใช้ algorithm แบบไหนที่เหมาะสมกับเกม Tic-Tac-Toe มากที่สุด

มาเริ่มกันเลย!!!
เริ่มแรกก่อนที่เราจะเริ่มสร้าง algorithm เราต้องสร้างกระดานกันก่อน

ขั้นตอนที่ 1 สร้างกระดานให้กับเกม Tic-Tac-Toe
เราต้องสร้างช่องว่างให้กับ Player ก่อนโดยสร้างเงื่อนไขสำหรับ Check ว่ามีผู้เล่นคนไหนชนะหรือยัง

# นำเข้าไลบรารีที่จำเป็นทั้งหมด
import random
from time import sleep
from time import time

n = 3

# สร้างกระดานเปล่า
def create_board():
# สำหรับการดีบัก
    board = [
    [ '_', '_', '_' ], 
    [ '_', '_', '_' ], 
    [ '_', '_', '_' ]]

    return board

# ตรวจหาที่ว่างบนกระดานสำหรับการย้ายครั้งต่อไป
def possibilities(board):
    l = []

    for i in range(len(board)):
        for j in range(len(board)):

            if board[i][j] == '_':
                l.append((i, j))
    return l

# เลือกพื้นที่สุ่มสำหรับผู้เล่น
def random_place(board, player):
    selection = possibilities(board)
    current_loc = random.choice(selection)
    x,y = current_loc
    board[x][y] = player
    return(board)

ขั้นตอนที่ 2 จะเป็นการตรวจสอบว่าผู้เล่นคนไหนชนะ
ในขั้นตอนนี้จะเป็นการตรวจสอบว่า เครื่องหมายของผู้เล่นคนไหนครบ 3 ตัวหรือยังในแต่ละทุกทิศทาง ถ้าหากผู้เล่นคนไหนชนะจะทำการ return(win) ออกมา

# ตรวจสอบว่าผู้เล่นมีเครื่องหมายครบสามตัวหรือยัง
# ในแถวแนวนอน
def row_win(board, player):
    for x in range(len(board)):
        win = True

        for y in range(len(board)):
            if board[x][y] != player:
                win = False
                continue

        if win == True:
            return(win)
    return(win)

# ตรวจสอบว่าผู้เล่นมีเครื่องหมายครบสามตัวหรือยัง
# ในแถวแนวตั้ง
def col_win(board, player):
    for x in range(len(board)):
        win = True

        for y in range(len(board)):
            if board[y][x] != player:
                win = False
                continue

        if win == True:
            return(win)
    return(win)

# ตรวจสอบว่าผู้เล่นมีเครื่องหมายครบสามตัวหรือยัง
# ในแนวทแยง
def diag_win(board, player):
    win = True
    y = 0
    for x in range(len(board)):
        if board[x][x] != player:
            win = False
    if win:
        return win
    win = True
    if win:
        for x in range(len(board)):
            y = len(board) - 1 - x
            if board[x][y] != player:
                win = False
    return win

# ประเมินว่ามีผู้ชนะหรือเสมอกัน
def evaluate(board):
    winner = 'no'

    for player in ['x', 'o']:
        if (row_win(board, player) or
                col_win(board, player) or
                diag_win(board, player)):
            winner = player

    if (not isMovesLeft(board)) and winner == 'no':
        winner = 'tie'
    return winner

ขั้นตอนที่ 3 แสดงผล Board ในการเล่นแต่ละครั้ง

def printMatrix(mat):

  for i in range(n):
      for j in range(n):
          print("%s " % (mat[i][j]), end = " ")

      print()

ขั้นตอนที่ 4 ตรวจสอบว่ายังมีที่ว่างให้เล่นอยู่อีกหรือเปล่า?

def isMovesLeft(b):
  for i in b:
    if '_' in i:
      return True

  return False

เย้!!! สร้างกระดานให้กับเกม Tic-Tec-Toe เสร็จแล้วงั้นเรามาสร้าง algorithm กันโดยเราจะสร้าง Algorithm Random Game กันก่อน ว่าแต่ Random Game คืออะไร? ก็คือเป็นตัวควบคุมเกมที่ใช้การเล่นแบบ random

ขั้นตอนที่ 1 สร้าง Algorithm Random Game
โดยเกมนี้ algorithm จะเล่นแบบ random กับ Player(หรือเรานั้นเอง) ถ้าหากเราจะลงตำแหน่งไหนให้พิมพ์ Coordinate เช่น 0 0 (column ที่ 1 row ที่ 1)

def play_game():
  board, winner, counter = create_board(), 'no', 1
  printMatrix(board)
  sleep(1)
  player = 'x'

  while winner == 'no':
    if (player == 'x'):
      board = random_place(board, player)
      print("\nBoard after " + str(counter) + " move")
      printMatrix(board)
      sleep(1)
      counter += 1
      winner = evaluate(board)
      if winner != 'no':
        break
      else:
        player = 'o'
    else:
      pos = input("input number: ")
      (i,j) = tuple(map(int, pos.split(' ')))
      while board[i][j] !='_':
        pos = input("input number: ")
        (i,j) = tuple(map(int, pos.split(' ')))

      board[i][j] = player
      print("\nBoard after " + str(counter) + " move")
      printMatrix(board)
      sleep(2)
      counter += 1
      winner = evaluate(board)
      if winner != 'no':
        break
      else:
        player = 'x'
  return(winner)

ขั้นตอนที่ 2 เริ่มเล่นเกมแบบ Random Game
โดยกำหนดให้ machine เป็น "X" และ Player เป็น "O"

print("Winner is: " + str(play_game()))

Display

_  _  _  
_  _  _  
_  _  _  

Board after 1 move
_  _  _  
_  _  _  
x  _  _  
input number: 0 0

Board after 2 move
o  _  _  
_  _  _  
x  _  _  

Board after 3 move
o  _  _  
_  _  _  
x  x  _  
input number: 2 2

Board after 4 move
o  _  _  
_  _  _  
x  x  o  

Board after 5 move
o  _  x  
_  _  _  
x  x  o  
input number: 1 1

Board after 6 move
o  _  x  
_  o  _  
x  x  o  
Winner is: o

จะเห็นว่าตานี้ Player เป็นผู้ชนะเพราะ machine นั้นเล่นแบบ random โดยไม่สนว่าจะทำยังไงให้ชนะ

Algorithm ถัดไปที่จะนำมาใช้นั้นคือ Minimax Game

ขั้นตอนที่ 1 สร้าง Minimax Game Algorithm

def minimax(board, depth, isMax,player,opponent) :
    winner = evaluate(board)

    if (winner == player) : 
        return 10-depth

    if (winner == opponent) :
        return -10-depth

    if (winner == 'tie') :
        return 0

    if (isMax) :     
        best = -1000 
        for i in range(3) :         
            for j in range(3) :
                if (board[i][j]=='_') :

                    # ทำการย้าย 
                    board[i][j] = player 
                    best = max( best, minimax(board,
                                              depth + 1,
                                              not isMax,player,opponent) )

                    # ยกเลิกการย้าย 
                    board[i][j] = '_'
        return best
    else :
        best = 1000  
        for i in range(3) :         
            for j in range(3) :
                if (board[i][j] == '_') :
                    board[i][j] = opponent 
                    best = min(best, minimax(board, depth + 1, not isMax,player,opponent))
                    board[i][j] = '_'
        return best

# หาการเคลื่อนไหวที่ดีที่สุดสำหรับผู้เล่น
def findBestMove(board,player,opponent) : 
    bestVal = -1000 
    bestMove = (-1, -1) 
    for i in range(3):     
        for j in range(3):

            # Check ถ้าพื้นที่ว่าง
            if board[i][j]== '_':
                board[i][j] = player
                # คำนวณฟังก์ชั่นเพื่อประเมินสำหรับเคลื่อนไหว.
                start = time() 
                moveVal = minimax(board, 0, False,player,opponent) 
                end = time()
                # ยกเลิกการย้าย
                board[i][j] = '_'  
                if (moveVal > bestVal) :                
                    bestMove = (i, j)
                    bestVal = moveVal

    print("\nThe value of the best Move is :", bestVal)
    print(bestMove)
    print("Time : ",end-start)

    (i,j) = bestMove
    board[i][j] = player
    return board

ขั้นตอนที่ 2 กำหนด "X" และ "O" ให้ machine

def play_game_minimax_CC():
  board, winner, counter = create_board(), 'no', 1
  printMatrix(board)
  sleep(1)
  player = 'x'

  while winner == 'no':
    if player == 'x':
      opponent = 'o'
    else:
      opponent = 'x'

    board = findBestMove(board, player,opponent)
    print("\nBoard after " + str(counter) + " move")
    printMatrix(board)
    sleep(1)
    counter += 1
    winner = evaluate(board)
    if player == 'x':
      player = 'o'
    else:
      player = 'x'

  return(winner)

ขั้นตอนที่ 3 เริ่มเล่นเกมแบบ Minimax Game
เนื่องจากตานี้จะให้ machine เล่นกันเอง ดังนั้นผลที่ได้จะเป็น Tie ทุกครั้ง

print("Winner is: " + str(play_game_minimax_CC()))

Display

_  _  _  
_  _  _  
_  _  _  

The value of the best Move is : 0
(0, 0)
Time :  0.6078829765319824

Board after 1 move
x  _  _  
_  _  _  
_  _  _  

The value of the best Move is : 0
(1, 1)
Time :  0.08142495155334473

Board after 2 move
x  _  _  
_  o  _  
_  _  _  

The value of the best Move is : 0
(0, 1)
Time :  0.010361194610595703

Board after 3 move
x  x  _  
_  o  _  
_  _  _  

The value of the best Move is : 0
(0, 2)
Time :  0.001558065414428711

Board after 4 move
x  x  o  
_  o  _  
_  _  _  

The value of the best Move is : 0
(2, 0)
Time :  0.00042629241943359375

Board after 5 move
x  x  o  
_  o  _  
x  _  _  

The value of the best Move is : 0
(1, 0)
Time :  0.00011277198791503906

Board after 6 move
x  x  o  
o  o  _  
x  _  _  

The value of the best Move is : 0
(1, 2)
Time :  7.963180541992188e-05

Board after 7 move
x  x  o  
o  o  x  
x  _  _  

The value of the best Move is : 0
(2, 1)
Time :  2.2411346435546875e-05

Board after 8 move
x  x  o  
o  o  x  
x  o  _  

The value of the best Move is : 0
(2, 2)
Time :  1.4066696166992188e-05

Board after 9 move
x  x  o  
o  o  x  
x  o  x  
Winner is: tie

จะเห็นว่า Minimax Game Algorithm จะเป็นวิธีที่ machine นั้นมีความคิดมากขึ้นพยายามหาทางชนะและพยายามไม่ให้ฝ่ายตรงข้ามชนะ ดังนั้นในเมื่อ machine มี algorithm ที่เหมือนกันจึงไม่มีทางเลยที่จะมีใครชนะ ซึ่งผลที่ออกมาจึงเป็น Tie

ถัดไปจะเป็น Alpha-Beta Pruning Game Algorithm มาดูกันว่าจะมีความแตกต่างกับ algorithm อื่นๆที่กล่าวมาอย่างไรบ้าง

ขั้นตอนที่ 1 สร้าง Alpha-Beta Pruning Game Algorithm

def minimax_AlphaBeta(board, depth, isMax,player,opponent,alpha,beta) :
    winner = evaluate(board)

    if (winner == player) : 
        return 10-depth

    if (winner == opponent) :
        return -10-depth

    if (winner == 'tie') :
        return 0

    if (isMax) :     
        best = -1000 
        for i in range(3) :         
            for j in range(3) :      
                if (board[i][j]=='_') :
                    board[i][j] = player 
                    best = max( best, minimax_AlphaBeta(board,
                                              depth + 1,
                                              not isMax,
                                              player,opponent,
                                              alpha,beta) )
                    board[i][j] = '_'

                    if best >= beta:
                      return best
                    alpha = max(alpha,best)        
        return best
    else :
        best = 1000 
        for i in range(3) :         
            for j in range(3) :
                if (board[i][j] == '_') :
                    board[i][j] = opponent 
                    best = min(best, minimax_AlphaBeta(board, depth + 1, 
                                             not isMax,
                                             player,opponent,
                                             alpha,beta))
                    board[i][j] = '_'
                    if best <= alpha:
                      return best

                    beta = min(beta,best)
        return best

ขั้นตอนที่ 2 ทำหารหาตำแหน่งที่ดีที่สุด
โดย Method นี้จะทำการ return ตำแหน่งที่ดีที่สุดให้กับผู้เล่น

def findBestMove(board,player,opponent) : 
    bestVal = -1000 
    bestMove = (-1, -1) 
    MIN = -1000
    MAX = 1000

    for i in range(3):     
        for j in range(3):
            if board[i][j]== '_':
                board[i][j] = player 
                start = time()
                moveVal = minimax_AlphaBeta(board, 0, False,
                                            player,opponent,
                                            MIN,MAX) 
                end = time()
                board[i][j] = '_' 

                # หาพื้นที่ที่ดีที่สุดเพื่อทำการย้าย
                if (moveVal > bestVal) :                
                    bestMove = (i, j)
                    bestVal = moveVal

    print("\nThe value of the best Move is :", bestVal)
    print(bestMove)
    print("Time: ",end-start)

    (i,j) = bestMove
    board[i][j] = player
    return board

ขั้ยตอนที่ 3 กำหนด "X" และ "O" ให้ machine
เนื่องจากตานี้จะทำการให้ machine เล่นกันเองดังนั้นผลที่ได้จะต้องเป็น Tie ทุกครั้ง

def play_minimax_alpha_beta_CC():
  board, winner, counter = create_board(), 'no', 1
  printMatrix(board)
  sleep(2)
  player = 'x'

  while winner == 'no':
    if player == 'x':
      opponent = 'o'
    else:
      opponent = 'x'

    board = findBestMove(board, player,opponent)
    print("Board after " + str(counter) + " move")
    printMatrix(board)
    sleep(2)
    counter += 1
    winner = evaluate(board)
    if player == 'x':
      player = 'o'
    else:
      player = 'x'

  return(winner)

ขั้นตอนที่ 4 เริ่มเล่นเกมแบบ Alpha-Beta Pruning Game

print("Winner is: " + str(play_minimax_alpha_beta_CC()))

Display

_  _  _  
_  _  _  
_  _  _  

The value of the best Move is : 0
(0, 0)
Time:  0.04757213592529297
Board after 1 move
x  _  _  
_  _  _  
_  _  _  

The value of the best Move is : 0
(1, 1)
Time:  0.011094331741333008
Board after 2 move
x  _  _  
_  o  _  
_  _  _  

The value of the best Move is : 0
(0, 1)
Time:  0.0037636756896972656
Board after 3 move
x  x  _  
_  o  _  
_  _  _  

The value of the best Move is : 0
(0, 2)
Time:  0.00045871734619140625
Board after 4 move
x  x  o  
_  o  _  
_  _  _  

The value of the best Move is : 0
(2, 0)
Time:  0.0002200603485107422
Board after 5 move
x  x  o  
_  o  _  
x  _  _  

The value of the best Move is : 0
(1, 0)
Time:  0.000141143798828125
Board after 6 move
x  x  o  
o  o  _  
x  _  _  

The value of the best Move is : 0
(1, 2)
Time:  4.267692565917969e-05
Board after 7 move
x  x  o  
o  o  x  
x  _  _  

The value of the best Move is : 0
(2, 1)
Time:  2.3365020751953125e-05
Board after 8 move
x  x  o  
o  o  x  
x  o  _  

The value of the best Move is : 0
(2, 2)
Time:  1.8358230590820312e-05
Board after 9 move
x  x  o  
o  o  x  
x  o  x  
Winner is: tie

จะเห็นได้ว่าผลที่ได้จาก Alpha-Beta Pruning game นั้นคล้ายๆ กับ Minimax game แต่ถ้าเราสังเกตดีๆ เราจะเห็นว่าเวลาที่ใช้คำนวณในแต่ละขั้นตอนนั้น จะทำได้เร็วกว่าการเล่นแบบ Minimax game

ถ้างั้นเราลองให้ machine ใช้วิธีแบบ Random กับ Alpha-Beta Pruning ดูว่าผลจะเป็นอย่างไร

def play_with_random():
    board, winner, counter = create_board(), 'no', 1
    printMatrix(board)
    sleep(1)
    player = 'x'

    while winner == 'no':
      if player == 'x':
        board = random_place(board, player)
        print("\nBoard after " + str(counter) + " move")
        printMatrix(board)
        sleep(1)
        counter += 1
        winner = evaluate(board) 
        opponent = 'o'
      else:
        board = findBestMove(board, player,opponent)
        print("Board after " + str(counter) + " move")
        printMatrix(board)
        sleep(2)
        counter += 1
        winner = evaluate(board)
        opponent = 'x'


      if player == 'x':
        player = 'o'
      else:
        player = 'x'

    return(winner)

ทำการ Driver Code

print("Winner is: " + str(play_with_random()))

_  _  _  
_  _  _  
_  _  _  

Board after 1 move
_  _  x  
_  _  _  
_  _  _  

The value of the best Move is : 6
(0, 0)
Time :  0.014320135116577148
Board after 2 move
o  _  x  
_  _  _  
_  _  _  

Board after 3 move
o  _  x  
_  _  _  
_  x  _  

The value of the best Move is : 8
(1, 0)
Time :  0.000705718994140625
Board after 4 move
o  _  x  
o  _  _  
_  x  _  

Board after 5 move
o  _  x  
o  x  _  
_  x  _  

The value of the best Move is : 10
(2, 0)
Time :  0.00013303756713867188
Board after 6 move
o  _  x  
o  x  _  
o  x  _  
Winner is: o

จะเห็นได้เลยว่าใช้วิธี Alpha-Beta Pruning นั้นจะชนะตลอดเพราะ machine จะทำทุกวิถีทางเพื่อให้ตนเองชนะ

สรุป
จากทุก algorithm ที่ได้อธิบายมาจะเห็นได้ว่า algorithm แต่ละตัวนั้นมีความแตกต่างกัน ตั้งแต่รูปแบบ Random ที่ใช้วิธีแบบ random พื้นที่ที่ว่างโดยไม่สนว่าตนเองต้องชนะ รูปแบบ Minimax machine จะเริ่มหาวิถีทางเพื่อให้ตนเองชนะ และในส่วนของรูปแบบ Alpha-Beta Pruning นั้นจะมีการวิเคราะห์ที่เร็วกว่า Minimax

References : ผศ.ดร.เก็จแก้ว ธเนศวร
https://realpython.com/tic-tac-toe-ai-python/