วิธีสร้างเกม Tic-Tac-Toe โดยใช้ Python
Tags: ai, machinelearning, tutorial, python
Published: 2023-04-04 10:24:06

**เกม 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 ว่ามีผู้เล่นคนไหนชนะหรือยัง
```python
# นำเข้าไลบรารีที่จำเป็นทั้งหมด
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) ออกมา
```python
# ตรวจสอบว่าผู้เล่นมีเครื่องหมายครบสามตัวหรือยัง
# ในแถวแนวนอน
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 ในการเล่นแต่ละครั้ง**
```python
def printMatrix(mat):
     
  for i in range(n):
      for j in range(n):
          print("%s " % (mat[i][j]), end = " ")
            
      print()
```

**ขั้นตอนที่ 4 ตรวจสอบว่ายังมีที่ว่างให้เล่นอยู่อีกหรือเปล่า?**
```python
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) 
```python
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"
```python
print("Winner is: " + str(play_game()))
```
**Display**
<pre>
_  _  _  
_  _  _  
_  _  _  

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
</pre>

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

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

**ขั้นตอนที่ 1 สร้าง Minimax Game Algorithm**
```python
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**
```python
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 ทุกครั้ง
```python
print("Winner is: " + str(play_game_minimax_CC()))
```
**Display**
<pre>
_  _  _  
_  _  _  
_  _  _  

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

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

**ขั้นตอนที่ 1 สร้าง Alpha-Beta Pruning Game Algorithm**
```python
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 ตำแหน่งที่ดีที่สุดให้กับผู้เล่น
```python
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 ทุกครั้ง
```python
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**
```python
print("Winner is: " + str(play_minimax_alpha_beta_CC()))
```
**Display**
<pre>
_  _  _  
_  _  _  
_  _  _  

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

**ถ้างั้นเราลองให้ machine ใช้วิธีแบบ Random กับ Alpha-Beta Pruning ดูว่าผลจะเป็นอย่างไร**
```python
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**
```python
print("Winner is: " + str(play_with_random()))
```
<pre>
_  _  _  
_  _  _  
_  _  _  

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

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

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