Bạn đang xem:
Giải thuật Minimax là một thuật toán đệ quy lựa chọn bước đi kế tiếp trong một trò chơi có hai người. Xét một trò chơi đối kháng trong đó hai người thay phiên đi nước đi của mình như tic-tac-toe, cờ vua, cờ tướng, cờ caro, cờ vây… Khi chơi bạn có thể khai triển hết không gian trạng thái nhưng khó khăn chủ yếu là bạn phải tính toán được phản ứng và nước đi của đối thủ mình như thế nào? Cách xử lý đơn giản là bạn giả sử đối thủ của bạn cũng sử dụng kiến thức về không gian trạng thái giống bạn. Giải thuật Minimax áp dụng giả thuyết này để tìm kiếm không gian trạng thái của trò chơi.
Tóm Tắt
Giải thuật Minimax
Giải thuật Minimax là một thuật toán đệ quy lựa chọn bước đi kế tiếp trong một trò chơi có hai người bằng cách định giá trị cho các Node trên cây trò chơi sau đó tìm Node có giá trị phù hợp để đi bước tiếp theo.Bạn đang xem: Thuật toán minimax trong game caro Giải thuật Minimax là một thuật toán đệ quy lựa chọn bước đi kế tiếp trong một trò chơi có hai người. Xét một trò chơi đối kháng trong đó hai người thay phiên đi nước đi của mình như tic-tac-toe, cờ vua, cờ tướng, cờ caro, cờ vây… Khi chơi bạn có thể khai triển hết không gian trạng thái nhưng khó khăn chủ yếu là bạn phải tính toán được phản ứng và nước đi của đối thủ mình như thế nào? Cách xử lý đơn giản là bạn giả sử đối thủ của bạn cũng sử dụng kiến thức về không gian trạng thái giống bạn. Giải thuật Minimax áp dụng giả thuyết này để tìm kiếm không gian trạng thái của trò chơi.Tic-tac-toe và Minimax
Hai đối thủ trong trò chơi được gọi là MIN và MAX luân phiên thay thế nhau đi. MAX đại diện cho người quyết dành thắng lợi và cố gắng tối đa hóa ưu thế của mình, ngược lại người chơi đại diện cho MIN lại cố gắng giảm điểm số của MAX và cố gắng làm cho điểm số của mình càng âm càng tốt. Giả thiết đưa ra MIN và MAX có kiến thức như nhau về không gian trạng thái trò chơi và cả hai đối thủ đều cố gắng như nhau.
Mỗi Node biểu diễn cho một trạng thái trên cây trò chơi. Node lá là Node chứa trạng thái kết thúc của trò chơi.
Giải thuật Minimax thể hiện bằng cách định trị các Node trên cây trò chơi:
Node thuộc lớp MAX thì gán cho nó giá trị lớn nhất của con Node đó.Node thuộc lớp MIN thì gán cho nó giá trị nhỏ nhất của con Node đó.
Xem thêm:
Node thuộc lớp MAX thì gán cho nó giá trị lớn nhất của con Node đó.Node thuộc lớp MIN thì gán cho nó giá trị nhỏ nhất của con Node đó.Xem thêm: Game One Piece Danh Nhau 1, Game One Piece Vs Fairy Tail 1
Từ các giá trị này người chơi sẽ lựa chọn cho mình nước đi tiếp theo hợp lý nhất.
Các bước thuật giải Minimax
Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm tức là trạng thái kết thúc của trò chơi).Tính giá trị của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả.Nếu như mức đang xét là của người chơi cực tiểu (nút MIN), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả nhỏ nhất.Nếu như mức đang xét là của người chơi cực đại (nút MAX), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả lớn nhất.
Ví dụ mô phỏng giải thuật Minimax cho trò chơi Tic-Tac-toe
MAX đại diện quân đi O.MIN đại diện quân đi X.
Xem thêm:
Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm tức là trạng thái kết thúc của trò chơi).Tính giá trị của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả.Nếu như mức đang xét là của người chơi cực tiểu (nút MIN), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả nhỏ nhất.Nếu như mức đang xét là của người chơi cực đại (nút MAX), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả lớn nhất.MAX đại diện quân đi O.MIN đại diện quân đi X.Xem thêm: Choi Game Tom Va Jerry Dua Oto, Game Tom & Jerry Đua Xe 2, Tom And Jerry Dua Xe O To
Trạng thái kết thúc là trạng thái có 3 ô liên tiếp ngang, dọc, chéo có cùng một quân cờ X hoặc O, nếu là X tức MIN thắng còn O tức MAX thắng còn nếu tất cả các ô cờ đều được đi và trạng thái chưa kết thúc thì bàn cờ hòa. Điểm thắng của X là -1, của O là 1, và bàn cờ hòa là 0.
