Cấu trúc dữ liệu và Giải thuật Bài 106: Lý thuyết trò chơi (Game Theory & Minimax) - Phân tích chiến lược và định nghĩa trạng thái thắng thua trong thuật toán.

Sau khi đã tối ưu hóa các cấu trúc phân cấp bằng Tree DP ở Bài 105, chúng ta bước sang một lĩnh vực mang tính tương tác chiến lược cao: Lý thuyết trò chơi kết hợp Thuật toán Minimax.

Trong các trò chơi tổng bằng không (Zero-sum games) như cờ vua, cờ caro, hoặc các hệ thống ra quyết định đối kháng (như định giá tự động trong đấu giá ngược hoặc bot đàm phán), hai người chơi lần lượt đi những nước đi tối ưu nhằm chống lại đối thủ. Để máy tính có thể "suy nghĩ" và đưa ra nước đi bách chiến bách thắng, Thuật toán Minimax ra đời như một mô hình duyệt cây quyết định kinh điển.

1. Bản chất của Thuật toán Minimax

Minimax hoạt động dựa trên giả định rằng cả hai người chơi đều vô cùng thông minh:

• Maximizer (Người chơi tối đa hóa): Luôn muốn tìm cách đạt được điểm số cao nhất có thể.

• Minimizer (Người chơi tối thiểu hóa): Luôn tìm cách ép đối thủ (hoặc bản thân) về mức điểm thấp nhất có thể.

Thuật toán duyệt qua cây trạng thái của trò chơi theo chiều sâu (DFS), đánh giá giá trị tại các nút lá (khi trò chơi kết thúc: Thắng = +10, Thua = -10, Hòa = 0), sau đó lan truyền giá trị ngược lên các nút cha theo quy tắc: tầng của Maximizer chọn giá trị lớn nhất ($\max$), tầng của Minimizer chọn giá trị nhỏ nhất ($\min$).

2. Tối ưu hóa với Cắt tỉa Alpha-Beta (Alpha-Beta Pruning)

Vấn đề chí mạng của Minimax thuần túy là bùng nổ tổ hợp (Combinatorial Explosion). Số lượng trạng thái trong cờ vua lớn hơn cả số nguyên tử trong vũ trụ.

Để giải quyết, Alpha-Beta Pruning được tích hợp vào Minimax bằng cách duy trì hai giá trị $\alpha$ (ngưỡng tốt nhất mà Maximizer có thể đảm bảo) và $\beta$ (ngưỡng tốt nhất mà Minimizer có thể đảm bảo). Nếu tại một nhánh, kết quả tồi tệ hơn nhánh đã xét, thuật toán sẽ cắt tỉa (prune) ngay lập tức, không thèm duyệt sâu tiếp, giúp tăng tốc độ xử lý gấp bội mà không làm mất độ chính xác.

3. Hiện thực hóa Minimax bằng Golang

Đoạn code Golang dưới đây cài đặt thuật toán Minimax cơ bản cho một trò chơi đối kháng dạng cây quyết định:

Go

package main

import (
	"fmt"
	"math"
)

// Hàm Minimax tính điểm tối ưu cho người chơi hiện tại
func minimax(depth int, nodeIndex int, isMaximizing bool, scores []int, h int) int {
	// Điều kiện dừng: Đã đến tầng lá của cây
	if depth == h {
		return scores[nodeIndex]
	}

	if isMaximizing {
		best := math.MinInt32
		// Duyệt qua 2 nhánh con (trái và phải)
		for i := 0; i < 2; i++ {
			val := minimax(depth+1, nodeIndex*2+i, false, scores, h)
			if val > best {
				best = val
			}
		}
		return best
	} else {
		best := math.MaxInt32
		for i := 0; i < 2; i++ {
			val := minimax(depth+1, nodeIndex*2+i, true, scores, h)
			if val < best {
				best = val
			}
		}
		return best
	}
}

func main() {
	// Các điểm số tại các nút lá của cây quyết định (chiều cao h = 3 -> 2^3 = 8 lá)
	scores := []int{3, 5, 2, 9, 12, 5, 23, 23}
	
	// Chiều cao cây h = log2(8) = 3
	treeHeight := 3

	optimalScore := minimax(0, 0, true, scores, treeHeight)
	fmt.Printf("Điểm số tối ưu mà Maximizer có thể đạt được: %d\n", optimalScore)
}

4. Ứng dụng thực tế ngoài Trò chơi

• Hệ thống Định giá Tự động (Dynamic Pricing & Auctions): Mô phỏng hành vi trả giá của các đối thủ cạnh tranh trên sàn thương mại điện tử để đưa ra mức giá thầu tối ưu.

• An ninh mạng & Phòng thủ tự động: Dự báo các bước đi tiếp theo của hacker trong các mô hình trò chơi bảo mật (Security Games).

• Trí tuệ nhân tạo đàm phán: Xây dựng chiến lược phản hồi trong các hệ thống tự động chốt đơn hoặc thương lượng tài nguyên hạ tầng.