Bài viết này lần đầu được đăng lên trang Never Stop Building bởi Jason Fox vào 13/12/2013 tại http://neverstopbuilding.com/minimax. Dưới đây chỉ là bài dịch của bài viết trên.
Mình vừa mới làm ra một game show Tic Tac Toe ( tương tự như như Caro nhưng chỉ có 9 ô ) “ bất khả chiến bại ”. Tuy dự án Bất Động Sản trên khá đơn thuần, nhưng nó đã giúp mình khám phá thêm về nhiều thứ xoay quanh về giải thuật và lập trình. Nếu bạn muốn chiêm ngưỡng và thưởng thức, hay đơn thuần là không tin, bạn hoàn toàn có thể thử chơi một vài ván Tic Tac Toe ở đây .
Để tạo ra một chương trình Tic Tac Toe hoàn hảo, một thuật toán có thể tính toán tất cả nước đi và xác định nước đi có lợi là thiết yếu. Sau một lúc tìm hiểu về các thuật toán, thuật toán Minimax là lựa chọn hợp lý nhất.
Bạn đang đọc: Ứng dụng thuật toán Minimax trong game Tic-Tac-Toe (Cờ Caro)
Phải mất một lúc mình mới hiểu được nguyên tắc của thuật toán Minimax và ứng dụng nó vào trong game show của mình. Mình có lướt qua 1 số ít ví dụ trên mạng kèm theo chú thích, nhưng theo mình không có ví dụ nào thật sự dễ hiểu như quy trình mình làm project này. Vì vậy, mình mong bài viết này hoàn toàn có thể giúp những bạn hiểu rõ hơn về thuật toán Minimax, đồng thời chiêm ngưỡng và thưởng thức vẻ đẹp mà thuật toán mang lại .
Miêu tả một trò chơi Tic Tac Toe hoàn hảo
Vậy thế nào là một game show Tic Tac Toe tuyệt vời và hoàn hảo nhất ? Một game show Tic Tac Toe “ bất khả chiến bại ” được định nghĩa rằng :
Nếu mình chơi một cách hoàn hảo, thì trong tất cả các ván Tic Tac Toe mình sẽ Thắng hoặc Hòa, và nếu mình chơi với một người chơi hoàn hảo khác, thì cả hai sẽ luôn luôn Hòa.
Vậy làm thế nào để ta hoàn toàn có thể miêu tả ba tác dụng Thắng, Thua, và Hòa để chương trình hoàn toàn có thể hiểu và quyết định hành động nước đi ? Trong trường hợp này, mình sẽ lần lượt gán điểm số vào ba trường hợp của game show :
- Mình thắng. Ngon đấy! Mình được 10 điểm rồi.
- Mình thua. Mất 10 điểm (vì người chơi kia đã lấy 10 điểm).
- Mình hòa. Huề cả làng. Điểm số giữ nguyên.
Nhờ vào việc gán những điểm tương ứng, tất cả chúng ta hoàn toàn có thể xác lập số điểm của một ván bất kể .
Ví dụ
Để hiểu rõ hơn, hãy lấy một ví dụ từ một ván Tic Tac Toe gần tới hồi kết, đồng thời là lượt đi của mình (mình là X). Mục tiêu của mình rõ ràng là tối ưu hóa điểm số, đồng nghĩa với việc chiến thắng và ra về với 10 điểm.
Hình ở trên miêu tả ba nước đi mình hoàn toàn có thể đi khi rơi vào một nước như vậy, và rõ ràng một trong ba nước sẽ làm mình thắng game show và có 10 điểm. Và nếu mình không đi nước đó, thì O sẽ cướp lấy thời cơ và thắng lợi game show này. Cơ mà mình không muốn O thắng, nên tiềm năng của mình, với thời cơ là người đi trước trước khi O lội ngược dòng, là lựa nước đi dẫn tới hiệu quả thắng .
Còn O thì sao?
Chúng ta biết gì về O? Giả định O muốn chiến thắng trò chơi cũng như chúng ta, O đương nhiên sẽ chọn nước đi bất lợi cho chúng ta nhất (có lợi cho O), đồng nghĩa với việc lựa nước đi tối thiểu hoá điểm số của chúng ta. Hãy nhìn trò chơi dưới góc nhìn của O ở hai trường hợp ở trên, khi mà chúng ta không thể thắng ngay lập tức như trường hợp ở trên.
Rõ ràng O sẽ chọn nước đi để tất cả chúng ta bị trừ 10 điểm .
Miêu tả thuật toán Minimax
Chìa khóa của thuật toán Minimax chính là lượt chơi qua lại giữa hai người chơi, khi mà cả hai đều mong ước nước đi có điểm trên cao nhất. Điểm số của từng nước đi của ta được quyết định hành động bởi đối thủ cạnh tranh, người quyết định hành động nước nào sẽ mang lại điểm số nhỏ nhất cho tất cả chúng ta. trái lại, điểm số của đối thủ cạnh tranh lại được quyết định hành động bởi tất cả chúng ta, người tìm cách tối ưu hóa điểm số. Nói ngắn gọn thì thuật toán Minimax trong game show Tic Tac Toe chính là thử hết những nước đi hoàn toàn có thể cho đến khi game show kết thúc .
Giả dụ đang tới lượt X, thì game show sẽ có quy trình tiến độ như sau :
- Nếu trò chơi kết thúc, trả về điểm số dưới góc nhìn của X.
- Không thì thu thập các nước đi có thể ở lượt mới.
- Tạo một mảng (một cấu trúc dữ liệu bao gồm một nhóm các giá trị phần tử hoặc biến) chứa các điểm số tương ứng với các nước nêu trên.
- Đối với từng tình huống, cập nhật điểm số tính bởi thuật Minimax vào mảng nêu trên.
- Nếu lượt đi là của X, trả về điểm số lớn nhất trong mảng.
- Nếu lượt đi là của O, trả về điểm số nhỏ nhất trong mảng.
Bạn sẽ chú ý rằng thuật toán Minimax là một thuật toán đệ quy – sự qua lại giữa lượt đi của hai người chơi cho đến khi số điểm sau cuối được tìm thấy .
Hãy cũng xem qua nguyên tắc của thuật toán so với một cây nước đi rất đầy đủ và chỉ ra làm thế nào mà nước đi dẫn tới thắng lợi được lựa chọn :
- Tình huống 1 là lượt đi của X. X tạo ra 3 tình huống 2, 3, và 4 và áp dụng thuật toán Minimax trên từng tình huống.
- Tình huống 2 trả về điểm +10 cho mảng điểm của tình huống 1, bởi vì trò chơi đã đến hồi kết.
- Tình huống 3 và 4 chưa tới hồi kết nên lần lượt tạo ra các tình huống 5, 6 và 7, 8 đồng thời áp dụng thuật toán Minimax.
- Tình huống 5 trả về điểm -10 cho mảng điểm của tình huống 3, tương tự với tình huống 7 trả về điểm -10 cho mảng 4.
- Tình huống 6 và tình huống 8 chỉ tạo ra một tình huống, đồng thời là tình huống cuối cùng dẫn tới trò chơi kết thúc với X là người thắng, nên cả hai sẽ lần lượt trả về điểm +10 cho mảng 3 và 4.
- Bởi vì sau tình huống thứ 3 và thứ 4 là lượt đi của O, nên O sẽ đi nước đi dẫn tới điểm số thấp nhất. Bởi vì cả hai tình huống đều có mảng chứa +10 và -10, nên tình huống 3 và 4 sẽ trả về -10 cho mảng điểm của tình huống 1 (điểm thấp nhất).
- Trong mảng điểm của tình huống 1 sẽ chứa các điểm lần lượt là +10, -10, -10. Vì tình huống 1 là lượt đi của X nên X sẽ lựa nước đi có điểm cao nhất, nghĩa là chọn nước đi dẫn tới số điểm +10 – nước đi tương tự tình huống thứ 2.
Tuy đơn thuần, nhưng quy trình trên cần rất nhiều công sức của con người. Bởi vậy nên tất cả chúng ta mới cần máy tính để chạy chương trình thay cho tất cả chúng ta .
Tới đây, mình mong rằng bạn đã hiểu về nguyên tắc hoạt động giải trí của thuật toán Minimax khi lựa chọn nước đi tương thích. Dưới đây là một đoạn pseudo code để những bạn tìm hiểu thêm :
12345678910111213141516171819
# @ player is the turn taking player
defscore(game)
if<spanclass=” skimlinks-unlinked “>game.win?(@player)
return10
elsif<spanclass=” skimlinks-unlinked “>game.win?(@opponent)
return-10
else
return0
end
end
Người thắng được + 10, người thua bị – 10, và hòa là 0. Bạn sẽ chú ý rằng người chơi là X hay O không quan trọng, mà quan trọng là lượt đi của ai .
Và dưới đây là là ứng dụng của thuật toán Minimax không thiếu ; chú ý quan tâm rằng nước đi ( move ) có dạng hàng / cột, ví dụ như [ 0, 2 ] chính là hàng thứ 0, cột thứ 2, đồng thời là ô phải trên cùng .
defminimax(game)
returnscore(game)if<spanclass=” skimlinks-unlinked “>game.over?
scores=[]# an array of scores
moves=[]# an array of moves
# Populate the scores array, recursing as needed
<spanclass=” skimlinks-unlinked “>game.get_available_moves.eachdo|move|
possible_game=game.get_new_state(move)
<spanclass=” skimlinks-unlinked “>scores.pushminimax(possible_game)
<spanclass=” skimlinks-unlinked “>moves.pushmove
end
# Do the min or the max calculation
ifgame.active_turn= =@player
# This is the max calculation
max_score_index=<spanclass=” skimlinks-unlinked “>scores.each_with_index.max[1]
@choice=moves[max_score_index]
returnscores[max_score_index]
else
# This is the min calculation
min_score_index=<spanclass=” skimlinks-unlinked “>scores.each_with_index.min[1]
@choice=moves[min_score_index]
returnscores[min_score_index]
end
end
Khi thuật toán này được vận dụng trong một lớp PerfectPlayer, nước đi tuyệt vời và hoàn hảo nhất nhất được tàng trữ trong biến @ choice, biến được sử dụng để trả lại những trường hợp mà người chơi đã đi .
Tuy vậy, trong quy trình test game show, mình chợt nhận ra một điều mê hoặc rằng thuật toán này có đôi chút “ bi quan ”. Nghĩa là, khi đặt game show vào một trường hợp hiển nhiên thua, thì game show sẽ chọn một nước đi “ bi quan ” – thua ngay lập tức. Thuật toán còn hoàn toàn có thể hiểu rằng : “ Này anh bạn, đằng nào tôi cũng thua nên thua ở nước đi sau đó hay nước đi thứ 6 chả quan trọng đâu. ”
Mình phát hiện ra điều này khi đụng độ một trường hợp có sẵn, hoặc là một lỗi trong quy trình mình lập trình game show. Mình mong đợi máy tính tối thiểu phải đứng lên chặn đường thắng của mình, nhưng không :
Hãy xem những gì sẽ xảy ra bằng cây nước đi ( Lưu ý, mình đã lược bỏ vài trường hợp để cho ví dụ đỡ rối hơn ) :
- Giả định tình huống 1 khi cả hai cùng chơi một cách hoàn hảo, và O là máy tính. O chọn bước đi như tình huống 5 và thua ngay lập tức khi X chọn như tình huống 9.
- Nhưng nếu O chặn X như tình huống 3, X sẽ chặn O như tình huống 7.
- Điều này dẫn đến chiến thắng chắc chắn cho X như tình huống 10 và 11. Như vậy, bất kể O đi nước nào trong tình huống 7, X vẫn thắng.
Bởi lẽ tất cả chúng ta đang chạy vòng lặp cho từng ô trống, từ trái sang phải, từ trên xuống dưới, tổng thể nước đi đều tương tự nhau và dẫn tới phần thua cho O, nước đi trong trường hợp 5 được chọn do tại nó là nước đi sau cuối trong toàn bộ những nước đi hoàn toàn có thể chứa trong mảng move ở trường hợp 1. Thứ tự của những thành phần trong mảng lần lượt là : [ [ 0, 0 ], [ 0, 2 ], [ 1, 0 ], [ 1, 1 ] ] .
Vậy một bậc thầy về Tic Tac Toe sẽ làm gì trong trường hợp này ?
Chơi kiên cường: Chiều sâu
Chìa khóa để cải thiện thuật toán này, khiến cho máy tính kháng cự cho tới khi game show thật sự chấm hết, chính là xem xét chiều sâu, hay nói cách khác là số lượt, trong quy trình giám sát. Về cơ bản thì người chơi tuyệt vời phải chơi một cách tuyệt vời và hoàn hảo nhất, tuy nhiên phải lê dài game show lâu nhất hoàn toàn có thể .
Để làm được điều này, tất cả chúng ta sẽ trừ đi chiều sâu của game ( số lượt ) từ số điểm tính ra khi game show kết thúc. Khi đó, càng nhiều lượt thì điểm càng thấp, càng ít lượt thì điểm càng cao. Do đó, đoạn code ở trên sau khi chỉnh sửa sẽ như sau :
defscore(game,depth)
if<spanclass=” skimlinks-unlinked “>game.win?(@player)
return10-depth
elsif<spanclass=” skimlinks-unlinked “>game.win?(@opponent)
returndepth-10
else
return0
end
end
defminimax(game,depth)
returnscore(game)if<spanclass=” skimlinks-unlinked “>game.over?
depth+ =1
scores=[]# an array of scores
moves=[]# an array of moves
# Populate the scores array, recursing as needed
<spanclass=” skimlinks-unlinked “>game.get_available_moves.eachdo|move|
possible_game=game.get_new_state(move)
<spanclass=” skimlinks-unlinked “>scores.pushminimax(possible_game,depth)
<spanclass=” skimlinks-unlinked “>moves.pushmove
end
# Do the min or the max calculation
ifgame.active_turn= =@player
# This is the max calculation
max_score_index=<spanclass=” skimlinks-unlinked “>scores.each_with_index.max[1]
@choice=moves[max_score_index]
returnscores[max_score_index]
else
# This is the min calculation
min_score_index=<spanclass=” skimlinks-unlinked “>scores.each_with_index.min[1]
@choice=moves[min_score_index]
returnscores[min_score_index]
end
end
Vậy nên mỗi khi vận dụng thuật Minimax, độ sâu được tăng 1 và khi game show kết thúc, điểm số sẽ được tính dựa trên chiều sâu. Cùng xem nó sẽ ra sao khi vận dụng vào ví dụ phía trên :
Xem thêm: TOP 7 app ghép mặt chó mèo cực độc đáo trên Android, iOS
Lần này, chiều sâu đã tạo ra sự độc lạ về điểm số giữa những trường hợp kết thúc của game show. Và chính do ở trường hợp 0, thuật toán Minimax đang tìm kiếm điểm số lớn nhất, điểm – 6 sẽ được chọn vì lớn hơn điểm – 8. Do đó, ngay cả khi biết trước được cái chết của mình, máy tính sẽ chọn chặn nước đi của đối thủ cạnh tranh, thay vì tự tử mổ bụng seppuku như samurai .
Kết luận
Mình mong rằng cuộc bàn luận này đã giúp bạn hiểu rõ hơn về thuật toán Minimax và chinh phục game show Tic Tac Toe. Nếu bạn có thêm vướng mắc hoặc cần giải đáp rõ hơn, vui vẻ để lại phản hồi và mình sẽ cải tổ bài viết của mình. Tất cả những đoạn code của game show Tic Tac Toe hoàn toàn có thể được tìm thấy trên Github nếu bạn có nhu yếu .
Ngoài Tic Tac Toe, thuật toán Minimax còn được vận dụng thoáng rộng nhiều trong kim chỉ nan game show. Tiêu biểu là cờ Caro, cờ vua … và những game đối kháng hai người trong đó nước đi hoàn toàn có thể Dự kiến được ( khác với oẳn tù tì, khi Phần Trăm ra búa, bao, kéo đều như nhau ) .
Source: https://mindovermetal.org
Category: Ứng dụng hay
