Triển khai thuật toán Minimax cho AI bằng Python

Thuật toán Mini-Max có lịch sử phong phú trong AI, bắt đầu từ những năm 1920. Dù thời đó chưa dùng thuật ngữ AI cho các thuật toán máy tính, thuật toán nền tảng này chắc chắn đã mang lại những hiểu biết sớm nhất về cách máy móc có thể đưa ra quyết định tối ưu trong các tình huống đối kháng. Thuật toán được John von Neumann chính thức hóa lần đầu trong bài báo năm 1928 “Zur Theorie der Gesellschaftsspiele” (Về lý thuyết trò chơi chiến lược), đặt nền tảng cho lý thuyết trò chơi hiện đại và các thuật toán ra quyết định.

Năm 1997, Deep Blue của IBM đánh bại nhà vô địch cờ vua thế giới Garry Kasparov bằng các biến thể nâng cao của Mini-max. Kể từ đó, thuật toán này là xương sống cho những cách tiếp cận tinh vi hơn như Tìm kiếm Cây Monte Carlo (MCTS) và các hệ thống học tăng cường.

Trong bài viết này, chúng ta sẽ không xây dựng lại Deep Blue nổi tiếng cho cờ vua mà là một phiên bản đơn giản hơn nhiều cho trò ca-rô bằng Python. Trên đường đi, bạn sẽ có trực giác vững vàng về cách thuật toán hoạt động và cách áp dụng nó vào các trò chơi phức tạp hơn trong thế giới thực.

Thuật toán Minimax là gì?

Minimax thường là một thuật toán ra quyết định cho các trò chơi hai người (như cờ vua, ca-rô hay cờ đam). Nó cho phép máy tính lên kế hoạch nhiều nước đi, giả định rằng đối thủ của bạn sẽ luôn thực hiện nước đi tốt nhất có thể. Trong phần này, chúng ta sẽ xem tổng quan thuật toán qua ví dụ trò ca-rô.

Tổng quan về thuật toán Minimax

Trong một ván ca-rô ngoài đời, mỗi lần đến lượt, bạn cố gắng đi nước tốt nhất đồng thời giả định đối thủ cũng sẽ chơi tốt nhất. Đó chính xác là những gì thuật toán Minimax làm — nó giúp máy tính đi nước tối ưu bằng cách suy nghĩ trước về mọi nước đi có thể xảy ra.

Tên Minimax xuất phát từ cách nó hoạt động:

• “Mini” đại diện cho đối thủ cố gắng giảm thiểu điểm số của bạn
• “Max” đại diện cho bạn cố gắng tối đa hóa điểm số của mình

Khi đến lượt bạn, bạn muốn thực hiện những nước đi cho cơ hội thắng cao nhất (tối đa hóa). Khi đến lượt đối thủ, bạn giả định họ sẽ đi những nước mang lại kết cục tệ nhất cho bạn (giảm thiểu).

Tầm quan trọng của Minimax trong AI

Minimax cực kỳ quan trọng trong trí tuệ nhân tạo vì nhiều lý do:

1. Giúp máy tính đưa ra quyết định thông minh trong trò chơi hai người
2. Là nền tảng cho nhiều hệ thống AI chơi game hiện đại
3. Dạy máy tính biết nhìn xa và lập kế hoạch nước đi

Điều thú vị là cùng một ý tưởng này được dùng trong rất nhiều ứng dụng thực tế:

• Đối thủ AI trong trò chơi điện tử
• Các trò chiến lược như cờ vua và cờ đam
• Thậm chí một số công cụ hỗ trợ ra quyết định trong kinh doanh

Dù Minimax nghe có vẻ phức tạp, thực chất nó chỉ là dạy máy tính suy nghĩ như một người chơi cẩn trọng, cân nhắc cả nước đi của mình lẫn nước đi của đối thủ trước khi ra quyết định.

Hiểu thuật toán Minimax

Hãy cùng phân tích cách Minimax hoạt động bằng ví dụ ca-rô đơn giản. Hãy tưởng tượng bạn chơi X, và máy tính là O.

Máy tính suy nghĩ như thế nào

Khi đến lượt máy tính, nó làm theo các bước sau:

1. Xem tất cả các nước có thể đi
2. Với mỗi nước, tưởng tượng bạn sẽ làm gì tiếp theo
3. Tiếp tục suy nghĩ cho đến khi đạt điểm kết thúc (ai đó thắng hoặc hòa)
4. Chọn nước mang lại cơ hội thắng cao nhất

Chấm điểm ván đấu

Máy tính có thể dùng hệ thống điểm đơn giản:

• +10 điểm nếu máy thắng
• -10 điểm nếu bạn thắng
• 0 điểm nếu hòa

Hãy nghĩ về nó như một cái cây khả năng:

• Trên đỉnh là bàn cờ hiện tại
• Mỗi nhánh là một nước đi có thể
• Dưới cùng là mọi kết quả có thể

Luân phiên lượt

Máy tính chuyển đổi giữa hai chế độ tư duy:

1. Chế độ tối đa hóa (lượt của máy):

• Tìm nước mang lại điểm cao nhất
• Cố gắng thắng hoặc buộc hòa

2. Chế độ tối thiểu hóa (lượt của người chơi):

• Giả định bạn sẽ đi những nước cho điểm thấp nhất
• Chuẩn bị trước cho các nước tốt nhất của bạn

Ví dụ đơn giản

Giả sử đến lượt máy (X) trong ván này:

Máy sẽ:

1. Thấy có 3 ô trống để chọn
2. Với mỗi ô trống, tưởng tượng mọi nước đi tương lai
3. Chọn nước dẫn đến kết quả tốt nhất cho mình
4. Trong trường hợp này, nên chọn ô giữa hàng dưới để chặn nước thắng của bạn

Cách suy nghĩ trước này giúp máy chơi một ván ca-rô hoàn hảo mỗi lần!

Giả mã thuật toán Minimax

Hãy phân tích cách viết thuật toán Minimax từng bước. Đừng lo nếu bạn mới làm quen với giả mã — hãy coi đó là viết các bước bằng tiếng Anh đơn giản trước khi chuyển nó thành mã thật!

Giải thích từng bước

Hàm Minimax cần ba thứ chính để hoạt động:

1. Bàn cờ hiện tại
2. Độ sâu (chúng ta nhìn trước bao nhiêu nước)
3. Lượt của người tối đa hóa (máy) hay tối thiểu hóa (người)

Giả mã cơ bản trông như sau:

function minimax(board, depth, isMaximizingPlayer):
   # First, check if the game is over
   if game is won:
       return +10 if computer wins, -10 if human wins
   if game is tied:
       return 0

   # If it's the computer's turn (maximizing)
   if isMaximizingPlayer:
       bestScore = -infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, false)
           undo the move
           bestScore = max(score, bestScore)
       return bestScore

   # If it's the human's turn (minimizing)
   else:
       bestScore = +infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, true)
           undo the move
           bestScore = min(score, bestScore)
       return bestScore

Dù hầu hết ví dụ giả mã đều dễ hiểu bằng tiếng Anh, ví dụ trên khác một chút vì nó dùng đệ quy. Đệ quy là khi một hàm tự gọi chính nó lặp đi lặp lại để giải một bài toán lớn hơn. Hãy nghĩ như nhìn vào một chiếc gương phản chiếu một chiếc gương khác — bạn thấy cùng một hình ảnh lặp lại nhiều lần, nhỏ dần mỗi lần.

Trong thuật toán Minimax của chúng ta, cần đệ quy vì ta cố gắng xem trước mọi nước đi tương lai của ván game. Mỗi lần hàm tự gọi, nó đang xem xét nước tiếp theo có thể xảy ra. 

Điều này giúp ta tìm ra nước đi tốt nhất bằng cách kiểm tra mọi cách ván đấu có thể diễn ra, giống như một người chơi rất thông minh nghĩ “Nếu tôi làm thế này, họ có thể làm thế kia, rồi tôi có thể làm thế này…”, và cứ thế cho đến khi ván kết thúc. Để tìm hiểu thêm về đệ quy, bạn có thể đọc hướng dẫn đệ quy riêng của chúng tôi.

Ví dụ minh họa

Hãy xem nó hoạt động trong một tình huống đơn giản:

1. Vị trí bắt đầu:

2. Máy tính suy nghĩ:

• “Nếu tôi đặt X vào bất kỳ ô trống nào…”
• “Người chơi sẽ làm gì tiếp theo?”
• “Và tôi có thể làm gì sau đó?”
• “Nước nào cho điểm cuối cùng tốt nhất?”

3. Với mỗi ô trống, máy tính:

• Thực hiện một nước đi
• Kiểm tra xem ván đã kết thúc chưa
• Nếu chưa, tưởng tượng nước tốt nhất của người chơi
• Tiếp tục cho đến khi tìm thấy một kết cục
• Chọn nước có điểm cao nhất

Hãy nghĩ như chơi cờ vua — bạn luôn nghĩ “Nếu tôi đi đây, họ sẽ đi đó, rồi tôi có thể đi đây…” nhưng máy tính có thể nghĩ về TẤT CẢ các nước đi cùng lúc!

Điều thú vị ở thuật toán này là nó luôn tìm ra nước đi tốt nhất có thể, giả định cả hai bên chơi hoàn hảo. Giống như có một quả cầu pha lê cho bạn thấy mọi tương lai có thể của ván đấu!

Triển khai Minimax cho ca-rô từng bước

Trong phần này, chúng ta sẽ xây dựng một AI ca-rô bất khả chiến bại sử dụng thuật toán Mini-max bằng Python thuần. Chúng ta sẽ chia nhỏ triển khai thành các bước đơn giản, giải thích trực giác đằng sau mỗi bước và cách chúng khớp vào bức tranh tổng thể của trò chơi.

Bước 1: Định nghĩa lớp TicTacToe

Trước tiên, ta định nghĩa một lớp chứa mọi logic và phương thức cần thiết để chơi ca-rô với máy tính của chúng ta:

class TicTacToe:
   def __init__(self):
       # Initialize empty board (using ' ' for empty squares)
       self.board = [" " for _ in range(9)]
       self.human_player = "O"
       self.ai_player = "X"

   def print_board(self):
       """Print the current state of the board"""
       for i in range(0, 9, 3):
           print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")
           if i < 6:
               print("---------")

   def available_moves(self):
       """Returns list of available moves (indices of empty squares)"""
       return [i for i, spot in enumerate(self.board) if spot == " "]

Ở trên, phương thức __init__ khởi tạo một bàn cờ mới như một danh sách gồm 9 khoảng trống (đại diện bởi ký tự khoảng trắng " "), với các chỉ số 0-8 đại diện cho vị trí từ trái sang phải, trên xuống dưới. Nó cũng thiết lập hai ký hiệu người chơi - "O" cho người chơi và "X" cho AI.

Phương thức print_board cung cấp cách trực quan hóa trạng thái hiện tại của bàn cờ. Nó in lưới 3x3 với đường phân cách giữa các hàng, hiển thị nước đi của mỗi người chơi ở vị trí tương ứng.

Phương thức available_moves trả về danh sách tất cả các nước đi hợp lệ còn có thể thực hiện. Nó làm điều này bằng cách kiểm tra các vị trí trên bàn còn trống (chứa ký tự " ") và trả về chỉ số của chúng. Điều này sẽ rất quan trọng để thuật toán minimax biết những nước nào có thể cân nhắc.

Những phương thức này là nền tảng để chúng ta xây dựng người chơi AI bằng thuật toán minimax.

Hãy kiểm tra nhanh:

>>> game = TicTacToe()
>>> game.print_board()
  |   | 
---------
  |   | 
---------
  |   |

>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Đúng như mong đợi, hiện tại bàn cờ trống và mọi nước đi đều khả dụng.

Bước 2: Cài đặt phương thức thực hiện nước đi và kiểm tra trạng thái bàn

Bây giờ, hãy thêm một phương thức để thực hiện nước đi:

class TicTacToe:
   ...
  
   def make_move(self, position, player):
       """Make a move on the board"""
       if self.board[position] == " ":
           self.board[position] = player
           return True
       return False

Chúng ta đã thêm phương thức make_move, phương thức này:

• Nhận vị trí (0–8) và ký hiệu người chơi (“X” hoặc “O”) làm đầu vào
• Kiểm tra xem vị trí đã chọn có trống (“ ”) không
• Nếu trống, đặt ký hiệu của người chơi và trả về True
• Nếu vị trí đã được chiếm, trả về False mà không thay đổi gì

Hãy thực hiện vài nước và kiểm tra các nước còn lại:

>>> game = TicTacToe()

>>> game.make_move(0, "X")
>>> game.make_move(1, "O")

>>> game.print_board()
 X | O | 
-----------
   |   | 
-----------
   |   |

>>> game.available_moves()
[2, 3, 4, 5, 6, 7, 8]

Hoạt động tốt. Bước tiếp theo là thêm phương thức kiểm tra xem bàn đã đầy chưa:

class TicTacToe:
   ...

   def is_board_full(self):
       """Check if the board is full"""
       return " " not in self.board

is_board_full là một phương thức boolean kiểm tra xem còn ô trống nào trên bàn không.

Tiếp theo, ta thêm phương thức kiểm tra có trạng thái thắng hay không:

class TicTacToe:
   ...

   def check_winner(self):
       """Check if there's a winner. Returns winner symbol or None"""
       # Check rows
       for i in range(0, 9, 3):
           if self.board[i] == self.board[i + 1] == self.board[i + 2] != " ":
               return self.board[i]

       # Check columns
       for i in range(3):
           if self.board[i] == self.board[i + 3] == self.board[i + 6] != " ":
               return self.board[i]

       # Check diagonals
       if self.board[0] == self.board[4] == self.board[8] != " ":
           return self.board[0]
       if self.board[2] == self.board[4] == self.board[6] != " ":
           return self.board[2]

       return None

Phương thức check_winner đánh giá trạng thái hiện tại của bàn cờ ca-rô để xác định có người thắng hay không. Nó kiểm tra mọi tổ hợp thắng có thể:

1. Hàng (3 khả năng):

• Hàng trên (chỉ số 0,1,2)
• Hàng giữa (chỉ số 3,4,5)
• Hàng dưới (chỉ số 6,7,8)

2. Cột (3 khả năng):

• Cột trái (chỉ số 0,3,6)
• Cột giữa (chỉ số 1,4,7)
• Cột phải (chỉ số 2,5,8)

3. Đường chéo (2 khả năng):

• Từ trên-trái xuống dưới-phải (chỉ số 0,4,8)
• Từ trên-phải xuống dưới-trái (chỉ số 2,4,6)

Với mỗi tổ hợp, nó kiểm tra xem cả ba vị trí có chứa cùng một ký hiệu người chơi (X hoặc O) và không phải ô trống. Nếu tìm thấy tổ hợp thắng, nó trả về ký hiệu của người thắng. Nếu không có ai thắng sau khi kiểm tra tất cả khả năng, nó trả về None.

Hãy kiểm thử hàm ở trạng thái thắng và không thắng:

game = TicTacToe()

# Winning state
game.make_move(0, "X")
game.make_move(1, "X")
game.make_move(2, "X")

>>> game.print_board()
 X | X | X
-----------
   |   | 
-----------
   |   |

>>> game.check_winner()
'X'

game = TicTacToe()

# Non-winning state
game.make_move(0, "X")
game.make_move(1, "O")
game.make_move(2, "O")
game.make_move(3, "X")

>>> game.print_board()
 X | O | O
-----------
 X |   | 
-----------
   |   |

>>> game.check_winner() is None
True

Cuối cùng, ta thêm một phương thức boolean khác để xác định trò chơi đã kết thúc hay chưa:

class TicTacToe:
   ...

   def game_over(self):
       """Check if the game is over"""
       return self.check_winner() is not None or self.is_board_full()

Phương thức trả về True nếu tìm được người thắng hoặc bàn đã đầy.

Đến lúc này, chúng ta đã xây dựng xong mọi cơ chế cốt lõi:

• Bàn cờ được biểu diễn là danh sách 9 ô khởi tạo trống
• print_board() hiển thị trực quan trạng thái hiện tại
• available_moves() trả về chỉ số các ô trống
• make_move() đặt ký hiệu người chơi lên bàn
• check_winner() kiểm tra hàng, cột, chéo để xác định thắng sau mỗi nước
• is_board_full() xác định xem không còn nước đi
• game_over() kết hợp kiểm tra thắng và kiểm tra đầy bàn

Những phương thức này cung cấp nền tảng để tạo một trò chơi có thể chơi được, xử lý các thao tác cơ bản như đi nước và xác định trạng thái trò chơi.

Giờ đến phần quan trọng — trao cho máy tính “bộ não” để chơi bằng Minimax.

Bước 3: Cài đặt Minimax cho ca-rô

Bây giờ, hãy triển khai thuật toán cho trò chơi trong một phương thức mới:

class TicTacToe:
   ...

   def minimax(self, depth, is_maximizing):
       """
       Minimax algorithm implementation
       Returns the best score possible for the current board state
       """
       # Base cases
       winner = self.check_winner()
       if winner == self.ai_player:
           return 1
       if winner == self.human_player:
           return -1
       if self.is_board_full():
           return 0

Hàm nhận hai tham số:

• depth - Theo dõi chúng ta đang ở mức đệ quy bao nhiêu. Có thể dùng để giới hạn độ sâu tìm kiếm với trò chơi rất phức tạp, nhưng với ca-rô thì không cần.
• is_maximizing - Cờ boolean cho biết ta đang tìm điểm tối đa (lượt AI) hay tối thiểu (lượt người). Cờ này luân phiên trong mỗi lần gọi đệ quy khi người chơi thay nhau.

Trong thân hàm, ta bắt đầu bằng các trường hợp cơ sở: Nếu AI thắng (winner == ai_player), trả về 1 vì đó là kết quả tốt nhất cho AI. Nếu người thắng (winner == human_player), trả về -1 vì đó là kết quả tệ nhất cho AI. Nếu bàn đầy và không có người thắng, trả về 0 cho hòa.

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       best_score = float("-inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(depth + 1, False)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = max(score, best_score)
       return best_score

Khi is_maximizing là True, chúng ta đang mô phỏng lượt AI và muốn tìm nước dẫn đến điểm cao nhất. Ta bắt đầu đặt best_score là âm vô cùng để bất kỳ điểm thực nào cũng tốt hơn. Với mỗi nước đi khả dụng, chúng ta:

1. Tạm thời đặt ký hiệu của AI lên bàn
2. Đánh giá đệ quy điều gì sẽ xảy ra nếu đi nước này bằng cách gọi minimax với is_maximizing=False (vì lượt tiếp theo là của người)
3. Hoàn tác nước đi tạm để khôi phục trạng thái bàn
4. Theo dõi điểm cao nhất đã thấy bằng max()

Điều này cho phép ta kiểm tra mọi nước AI có thể đi. Với mỗi nước, ta xem điều gì có thể xảy ra tiếp theo, cho tới khi có người thắng hoặc hòa. Sau đó ta suy ngược để tìm nước đầu tiên cho AI cơ hội thắng tốt nhất.

Giờ hãy làm phần tối thiểu hóa cho người:

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       ...

   else:
       # if it is the minimizing player's turn (human), we want to minimize the score
       best_score = float("inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.human_player
           # Recursively call minimax with the next depth and the maximizing player
           score = self.minimax(depth + 1, True)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = min(score, best_score)
       return best_score

Khi is_maximizing là False, chúng ta mô phỏng lượt của người chơi và muốn tìm nước dẫn đến điểm thấp nhất (vì điểm cao nghĩa là AI thắng). Chúng ta bắt đầu với best_score là dương vô cùng để bất kỳ điểm thực nào cũng thấp hơn. Với mỗi nước hợp lệ, ta:

1. Tạm thời đặt ký hiệu của người lên bàn
2. Đánh giá đệ quy bằng cách gọi minimax với is_maximizing=True (vì lượt tiếp theo là của AI)
3. Hoàn tác nước đi tạm để khôi phục trạng thái bàn
4. Theo dõi điểm thấp nhất bằng min()

Điều này mô phỏng người chơi cố gắng đi các nước tốt nhất để ngăn AI thắng. Người chơi muốn giảm thiểu điểm vì điểm dương đại diện cho chiến thắng của AI. Bằng cách luân phiên giữa lượt tối đa hóa và tối thiểu hóa, thuật toán xác định chuỗi nước đi tối ưu cho cả hai bên.

Bước 4: Tìm nước tốt nhất cho AI bằng Minimax

Giờ thuật toán đã sẵn sàng, ta cần phương thức khác sử dụng minimax để xác định nước tốt nhất cho AI sau mỗi nước của người:

class TicTacToe:
   ...

   def get_best_move(self):
       """Find the best move for AI using minimax"""
       best_score = float("-inf")
       best_move = None

       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(0, False)
           # Reset the move
           self.board[move] = " "

           # Update the best score
           if score > best_score:
               best_score = score
               best_move = move

       return best_move

Phương thức get_best_move chịu trách nhiệm xác định nước tối ưu cho AI bằng thuật toán minimax. Nó hoạt động bằng cách:

1. Bắt đầu với điểm tốt nhất là âm vô cùng và chưa chọn nước nào

2. Với mỗi nước còn trống trên bàn:

• Tạm thời đặt ký hiệu của AI vào vị trí đó
• Dùng minimax để đánh giá mức độ tốt của nước đó bằng cách mô phỏng phần còn lại của ván
• Hoàn tác nước tạm
• Nếu nước này dẫn đến điểm tốt hơn những gì đã thấy, cập nhật cả điểm tốt nhất và nước tốt nhất

3. Cuối cùng trả về nước dẫn đến điểm cao nhất

Cách tiếp cận này đảm bảo AI sẽ chọn nước cho cơ hội thắng tốt nhất, giả định người chơi cũng chơi tối ưu. Phương thức xét mọi trạng thái tương lai có thể và chọn con đường tối đa hóa cơ hội của AI đồng thời giảm cơ hội thắng của người.

Hãy kiểm thử trên một trạng thái ví dụ:

game = TicTacToe()

# Make a couple of moves
game.make_move(0, "X")
game.make_move(1, "O")

# Print the board

>>> game.print_board()
X | O | 
---------
  |   | 
---------
  |   |

>>> game.get_best_move()
3

# AI moves
>>> game.make_move(3, "X")

# I move
>>> game.make_move(4, "O")
>>> game.print_board()
X | O | 
---------
X | O | 
---------
  |   |

# Get the best move for AI
>>> game.get_best_move()
6

Như bạn thấy, AI đã tìm được chuỗi thắng dựa trên nước đi của tôi (đây là một trạng thái giả định nhưng chứng minh thuật toán của chúng ta hoạt động).

Bước 5: Cài đặt vòng lặp trò chơi

Giờ chúng ta đã triển khai và kiểm thử thuật toán minimax, hãy tạo vòng lặp trò chơi để có thể chơi đối kháng với AI.

class TicTacToe:

   ...

   def play_game(self):
       """Main game loop"""
       print("Welcome to Tic Tac Toe!")
       print("You are 'O' and the AI is 'X'")
       print("Enter positions (0-8) as shown below:")
       print("0 | 1 | 2")
       print("---------")
       print("3 | 4 | 5")
       print("---------")
       print("6 | 7 | 8")
       print("\n")

Phương thức play_game bắt đầu bằng việc hiển thị lời chào và hướng dẫn cho người chơi. Nó cho biết người chơi dùng ‘O’ và AI dùng ‘X’. Sau đó in một lưới được đánh số (0–8) để người chơi biết số nào tương ứng với vị trí nào trên bàn. Điều này giúp người chơi dễ dàng nhập số cho nước đi mong muốn.

# ... the rest of the class
def play_game(self):
   ...

   # Randomly decide who goes first
   import random

   ai_turn = random.choice([True, False])

   while not self.game_over():
       self.print_board()

       if ai_turn:
           print("\nAI's turn...")
           move = self.get_best_move()
           self.make_move(move, self.ai_player)
       else:
           while True:
               try:
                   move = int(input("\nYour turn (0-8): "))
                   if 0 <= move <= 8 and self.make_move(move, self.human_player):
                       break
                   else:
                       print("Invalid move! Try again.")
               except ValueError:
                   print("Please enter a number between 0 and 8!")

       ai_turn = not ai_turn

Sau khi hiển thị hướng dẫn ban đầu, trò chơi đi vào vòng lặp chính. Trò chơi ngẫu nhiên quyết định ai đi trước — AI hay người chơi — bằng random.choice([True, False]). Điều này tạo yếu tố công bằng và khó đoán khi bắt đầu mỗi ván.

Vòng lặp chính tiếp tục cho đến khi game_over() trả về True (hoặc có người thắng hoặc bàn đầy). Trong mỗi lượt, trạng thái bàn hiện tại được hiển thị bằng print_board().

Nếu là lượt của AI (ai_turn là True), chương trình:

1. In thông báo cho biết AI đang suy nghĩ
2. Gọi get_best_move() để xác định nước tối ưu bằng thuật toán minimax
3. Thực hiện nước đi bằng cách đặt ký hiệu ‘X’ của AI vào vị trí đã chọn

Nếu là lượt của người (ai_turn là False), chương trình:

1. Vào vòng lặp để nhận đầu vào hợp lệ từ người chơi2. Yêu cầu nhập số nước đi từ 0–83. Xác thực đầu vào là:

• Một số nguyên hợp lệ (dùng try/except)
• Trong phạm vi hợp lệ 0–8
• Chỉ đến vị trí trống trên bàn

4. Tiếp tục hỏi đến khi nhận được đầu vào hợp lệ. Thực hiện nước đi bằng cách đặt ký hiệu ‘O’ của người chơi vào vị trí đã chọn

Sau mỗi lượt, ai_turn được đảo bằng not để luân phiên người chơi. Điều này tạo nhịp điệu qua lại cho trò chơi, mỗi người chơi lần lượt cho đến khi có người thắng hoặc hòa.

Việc xác thực đầu vào đảm bảo trò chơi không bị sập do nhập sai và cung cấp thông báo lỗi hữu ích để hướng dẫn người chơi nhập nước đi đúng. Điều này tạo ra trải nghiệm trò chơi chắc chắn và thân thiện.

def play_game(self):
   ...
   # Game over
   self.print_board()
   winner = self.check_winner()
   if winner == self.ai_player:
       print("\nAI wins!")
   elif winner == self.human_player:
       print("\nCongratulations! You win!")
   else:
       print("\nIt's a tie!")

Khi trò chơi kết thúc, trạng thái bàn cuối cùng được hiển thị bằng print_board() và người thắng được xác định bởi check_winner(). Trò chơi có thể kết thúc theo ba cách:

1. AI thắng — Nếu check_winner() trả về ký hiệu của AI ('X'), nghĩa là AI đã tạo được một hàng thắng
2. Người chơi thắng — Nếu check_winner() trả về ký hiệu của người ('O'), nghĩa là người chơi đã tạo được một hàng thắng
3. Hòa — Nếu không ai thắng nhưng bàn đã đầy, nghĩa là không còn nước đi nào nữa

Thông điệp phù hợp sẽ được hiển thị để thông báo kết quả ván đấu. Điều này cung cấp phản hồi rõ ràng cho người chơi về cách ván đấu kết thúc.

Bước 6: Ghép tất cả lại với nhau

Giờ là lúc đặt toàn bộ mã đã viết vào một script Python với mệnh đề if/main ở cuối cùng:

# Start the game
if __name__ == "__main__":
   game = TicTacToe()
   game.play_game()

Điều này cho phép trò chơi bắt đầu ngay khi bạn chạy script bằng python script.py. Nếu bạn bị lạc giữa các phần giải thích và khối mã, bạn có thể tìm toàn bộ mã của trò chơi trong GitHub gist này.

Đây là một ván mẫu tôi đã chơi:

❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O' and the AI is 'X'
Enter positions (0-8) as shown below:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8


  |   | 
---------
  |   | 
---------
  |   | 

Your turn (0-8): 4
  |   | 
---------
  | O | 
---------
  |   | 

AI's turn...
X |   | 
---------
  | O | 
---------
  |   | 

Your turn (0-8): 5
X |   | 
----------
  | O | O
----------
  |   | 

AI's turn...
X |   | 
---------
X | O | O
---------
  |   | 

Your turn (0-8): 6
X |   | 
---------
X | O | O
---------
O |   | 

AI's turn...
X |   | X
---------
X | O | O
---------
O |   | 

Your turn (0-8): 1
X | O | X
---------
X | O | O
---------
O |   | 

AI's turn...
X | O | X
---------
X | O | O
---------
O | X | 

Your turn (0-8): 8
X | O | X
---------
X | O | O
---------
O | X | O

It's a tie!

Hãy nhớ, vì ca-rô là trò chơi đơn giản, bạn không có cơ hội đánh bại AI. Hoặc hòa, hoặc bạn thua!

Chuẩn hóa thuật toán Mini-max

Giờ hãy xem lại định nghĩa tổng quát của thuật toán ngoài ví dụ ca-rô đơn giản.

Thuật toán Minimax có thể được định nghĩa chính thức là một hàm đệ quy đánh giá các vị trí trong trò chơi tổng bằng không. Hãy phân tách các thành phần và tính chất chính thức của nó.

Định nghĩa toán học

Với trạng thái trò chơi s, giá trị minimax V(s) được định nghĩa như sau:

V(s) =
   utility(s)                    if s is terminal
   max(V(s')) for all s' in S    if player = MAX
   min(V(s')) for all s' in S    if player = MIN

Trong đó:

• s’ đại diện các trạng thái kế tiếp của s
• S là tập tất cả nước đi hợp lệ từ trạng thái s
• utility(s) là hàm đánh giá cho các trạng thái kết thúc

Các tính chất chính

1. Thông tin hoàn hảo

• Tất cả người chơi đều biết đầy đủ trạng thái trò chơi
• Không có thông tin ẩn hay yếu tố ngẫu nhiên
• Kết quả xác định

2. Bản chất tổng bằng không

• Lợi ích của người này đúng bằng tổn thất của người kia
• Tổng tiện ích cho tất cả người chơi luôn bằng không
• Với trò chơi hai người, tiện ích thường là {-1, 0, 1}

3. Chơi tối ưu

• Giả định cả hai người chơi đều ra quyết định tối ưu
• Đảm bảo kết quả tốt nhất có thể trước lối chơi hoàn hảo
• Dẫn đến cân bằng Nash theo thuật ngữ lý thuyết trò chơi

Phân tích độ phức tạp

Độ phức tạp thời gian: O(b^m)

• b = hệ số phân nhánh (số nước hợp lệ ở mỗi trạng thái)
• m = độ sâu tối đa của cây trò chơi

Độ phức tạp không gian: O(bm)

• Cần lưu trạng thái trò chơi ở mỗi mức
• Có thể tối ưu bằng làm sâu lặp (iterative deepening)

Hàm đánh giá

Với các trạng thái chưa kết thúc, hàm đánh giá f(s) nên:

1. Tương quan với xác suất thắng
2. Tính toán hiệu quả
3. Duy trì thang đo nhất quán trong suốt ván

Định nghĩa chính thức:

f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ

Trong đó:

• wᵢ là trọng số cho các đặc trưng khác nhau
• xᵢ là giá trị đặc trưng từ trạng thái trò chơi
• n là số đặc trưng được đánh giá

Bảo đảm tối ưu

Thuật toán Minimax bảo đảm lối chơi tối ưu khi thỏa các điều kiện:

1. Thông tin hoàn hảo
2. Kết quả xác định
3. Tìm kiếm đầy đủ tới các trạng thái kết thúc
4. Đánh giá trạng thái kết thúc chính xác

Điều này khiến nó đặc biệt phù hợp cho các trò như cờ vua, ca-rô và cờ đam, nơi các điều kiện trên được đáp ứng.

Biến thể nâng cao và hạn chế

Dù Minimax rất tốt cho các trò đơn giản như ca-rô, nó gặp vấn đề với trò lớn hơn. Hãy xem cách ta có thể làm nó tốt hơn và nơi nó gặp khó.

Làm Minimax nhanh hơn: Cắt tỉa Alpha-beta

Hãy tưởng tượng bạn chơi cờ vua và đang nghĩ về các nước đi. Nếu bạn đã tìm ra một nước thắng, bạn không cần kiểm tra mọi nước khác nữa, đúng không? Cắt tỉa Alpha-Beta hoạt động tương tự — nó giúp máy tính bỏ qua những nhánh mà ta đã biết sẽ không tốt hơn những gì đã tìm thấy.

Hãy nghĩ như thế này:

• Bạn đang tìm mua thanh kẹo rẻ nhất
• Bạn có $1 để chi
• Nếu bạn thấy thanh kẹo giá 50¢, bạn có thể bỏ qua những thanh giá hơn $1
• Điều này giúp tiết kiệm thời gian!

Giới hạn độ sâu: Không nhìn quá xa

Trong các trò lớn như cờ vua, có quá nhiều nước để kiểm tra hết. Vì vậy ta thêm giới hạn độ sâu:

1. Chỉ nhìn trước 4–5 nước thay vì đến cuối ván
2. Ước lượng hợp lý về mức độ tốt của vị trí tại điểm đó
3. Chọn nước tốt nhất dựa trên các ước lượng này

Bạn không thể lên kế hoạch mọi nước đến cuối ván, nhưng có thể lên kế hoạch vài nước trước!

Nơi Minimax gặp khó

Minimax không hoàn hảo. Đây là các vấn đề chính:

1. Quá nhiều lựa chọn

• Những trò như Cờ vây có quá nhiều nước có thể
• Ngay cả máy tính nhanh cũng không thể kiểm tra hết
• Vì thế ta cần phương pháp khác cho trò cực kỳ phức tạp

2. Vấn đề thời gian

• Càng nhìn xa nhiều nước, thời gian càng lâu
• Trong cờ vua, máy tính không thể xét mọi nước có thể
• Chúng cần thông minh trong việc chọn nhánh để xét

3. Không tốt cho trò chơi bất định

• Minimax hoạt động tốt nhất khi bạn thấy mọi thứ
• Nó không tốt cho các trò bài có thông tin ẩn
• Nó không xử lý tốt các sự kiện ngẫu nhiên (như tung xúc xắc)

Giải pháp hiện đại

AI chơi game ngày nay thường kết hợp Minimax với các kỹ thuật hay ho khác:

1. Học máy

• Máy tính có thể học bằng cách xem rất nhiều ván
• Điều này giúp chúng đưa ra ước lượng tốt hơn về nước tốt
• Các trò như AlphaGo dùng cách này để đánh bại nhà vô địch

2. Nhận dạng mẫu

• Thay vì kiểm tra mọi nước, hãy tìm các mẫu
• Giống như người chơi nhận biết nước tốt
• Điều này giúp máy tính nhanh hơn nhiều

3. Ngân hàng bộ nhớ

• Ghi nhớ các vị trí đã gặp trước đó
• Không tốn thời gian tính đi tính lại cùng một thứ
• Như có một “phao cứu sinh” các nước tốt!

Điều thú vị là những cải tiến này giúp máy tính chơi gần bằng hoặc thậm chí vượt con người! Nhưng hãy nhớ — dù có thêm nhiều “phép màu”, Minimax vẫn là nền tảng cốt lõi.

Kết luận

Trong hướng dẫn này, chúng ta đã khám phá thuật toán Minimax từ khái niệm cơ bản đến triển khai thực tế. Những điều đã học:

1. Khái niệm cốt lõi

• Cách Minimax giúp máy tính ra quyết định trong trò chơi
• Sự khác biệt giữa người chơi tối thiểu hóa và tối đa hóa
• Vì sao gọi là “minimax” và nó hoạt động ra sao

2. Kỹ năng triển khai

• Xây dựng trò chơi ca-rô từ đầu
• Viết thuật toán Minimax bằng Python
• Kiểm thử và gỡ lỗi logic trò chơi

3. Chủ đề nâng cao

• Làm thuật toán nhanh hơn với Cắt tỉa Alpha-Beta
• Xử lý hạn chế trong trò chơi phức tạp
• Cải tiến hiện đại bằng học máy

Tiếp theo là gì?

Thuật toán Minimax chỉ là một mảnh ghép trong bức tranh AI. Nếu bạn hứng thú học thêm về AI và thuật toán, đây là vài tài nguyên tuyệt vời để tiếp tục hành trình:

1. Thuật toán liên quan

• Hướng dẫn thuật toán A* — Tìm hiểu thuật toán tìm đường
• Hướng dẫn Gradient Boosting — Khám phá các thuật toán học máy

2. Ứng dụng Học máy

• Các trường hợp sử dụng Học máy — Xem các ứng dụng thực tế

3. Lộ trình học trọn vẹn

• Phát triển Ứng dụng AI — Xây dựng các dự án AI thực tiễn
• Nền tảng AI — Nắm vững các kiến thức cơ bản về AI

Hãy nhớ, dù bạn xây dựng một trò chơi đơn giản hay một hệ thống AI phức tạp, hiểu các thuật toán như Minimax cho bạn nền tảng vững chắc cho các chủ đề nâng cao hơn trong trí tuệ nhân tạo. Tiếp tục luyện tập, tiếp tục học hỏi, và quan trọng nhất, tiếp tục viết mã!