Trò chơi bảng Trí tuệ nhân tạo: Thuật toán Minimax: 8 bước

2024 Tác giả: John Day | [email protected]. Sửa đổi lần cuối: 2024-01-30 13:32

Bạn đã bao giờ tự hỏi máy tính mà bạn chơi với cờ vua hoặc cờ caro được tạo ra như thế nào chưa? Không cần tìm đâu xa hơn, cuốn sách Có thể hướng dẫn này sẽ chỉ cho bạn cách tạo ra trí thông minh nhân tạo (AI) đơn giản nhưng hiệu quả bằng cách sử dụng Thuật toán Minimax! Bằng cách sử dụng Thuật toán Minimax, AI thực hiện các bước đi được lập kế hoạch và suy nghĩ tốt (hoặc ít nhất là bắt chước một quá trình suy nghĩ). Bây giờ, tôi chỉ có thể cung cấp cho bạn mã cho AI mà tôi đã tạo ra, nhưng điều đó sẽ không vui đâu. Tôi sẽ giải thích logic đằng sau các lựa chọn của máy tính.

Trong phần có thể hướng dẫn này, tôi sẽ hướng dẫn bạn các bước về cách tạo AI cho Othello (AKA Reversi) trong python. Bạn nên có hiểu biết trung cấp về cách viết mã trong python trước khi giải quyết dự án này. Dưới đây là một số trang web tốt để bạn chuẩn bị cho chương trình Có thể hướng dẫn này: w3schools hoặc learningpython. Ở cuối phần Hướng dẫn này, bạn nên có một AI sẽ thực hiện các bước di chuyển có tính toán và có thể đánh bại hầu hết con người.

Vì có thể hướng dẫn này chủ yếu đề cập đến cách tạo ra một AI, tôi sẽ không giải thích cách thiết kế một trò chơi trong python. Thay vào đó, tôi sẽ cung cấp mã cho trò chơi mà con người có thể đấu với người khác và sửa đổi nó để bạn có thể chơi trò chơi mà con người đấu với AI.

Tôi đã học cách tạo ra AI này thông qua một chương trình mùa hè tại Columbia SHAPE. Tôi đã có một khoảng thời gian vui vẻ ở đó vì vậy hãy xem trang web của họ để xem liệu bạn có quan tâm không.

Bây giờ chúng ta đã hoàn thành nhiệm vụ hậu cần, hãy bắt đầu viết mã!

(Tôi đặt một vài ghi chú trong các hình ảnh nên hãy nhớ xem chúng)

Quân nhu

Điều này thật dễ dàng:

1) Máy tính có môi trường python như Spyder hoặc IDLE

2) Tải xuống các tệp cho trò chơi Othello từ GitHub của tôi

3) Bộ não của bạn với sự kiên nhẫn được cài đặt

Bước 1: Tải xuống các tệp cần thiết

Khi bạn truy cập GitHub của tôi, bạn sẽ thấy 5 tệp. Tải xuống tất cả 5 và đặt tất cả chúng vào cùng một thư mục. Trước khi chúng tôi chạy trò chơi, hãy mở tất cả các tệp trong môi trường spyder.

Đây là những gì các tệp làm:

1) othello_gui.py tệp này tạo bảng trò chơi để người chơi chơi trên đó (dù là người hay máy tính)

2) othello_game.py tệp này chơi hai máy tính với nhau mà không có bảng trò chơi và chỉ hiển thị điểm số và di chuyển vị trí

3) ai_template.py đây là nơi bạn sẽ đặt tất cả mã của mình để tạo AI của bạn

4) randy_ai.py đây là một AI tạo sẵn chọn các bước di chuyển của nó một cách ngẫu nhiên

5) othello_shared.py một loạt các chức năng được tạo sẵn mà bạn có thể sử dụng để tạo AI của mình, chẳng hạn như để kiểm tra các nước đi có sẵn, điểm số hoặc trạng thái bàn cờ

6) Ba tệp khác: Puma.py, erika_5.py và nathan.py, được tạo bởi tôi, Erika và Nathan tương ứng từ chương trình SHAPE, đây là ba AI khác nhau với các mã duy nhất

Bước 2: Cách mở và chơi Python Othello

Khi bạn đã mở tất cả các tệp, ở góc dưới cùng bên phải của màn hình, hãy nhập "run othello_gui.py" và nhấn enter trong Bảng điều khiển IPython. Hoặc trong Mac terminal, gõ "python othello_gui.py" (dĩ nhiên là sau khi bạn ở đúng thư mục). Sau đó, một bảng sẽ bật lên trên màn hình của bạn. Chế độ này là chế độ con người vs con người. Ánh sáng đi thứ hai và bóng tối đi trước. Hãy xem video của tôi nếu bạn cảm thấy bối rối. Ở trên cùng, có điểm của mỗi ô màu. Để chơi, hãy nhấp vào một khoảng trống di chuyển hợp lệ để đặt một ô ở đó và sau đó đưa máy tính cho đối thủ của bạn, người sẽ thực hiện tương tự và lặp lại.

Nếu bạn không biết cách chơi Othello, hãy đọc các quy tắc này từ trang web của bảng cực kỳ:

Đen luôn di chuyển trước. Nước đi được thực hiện bằng cách đặt một đĩa cùng màu của người chơi lên bàn cờ ở vị trí "lệch ra ngoài" một hoặc nhiều đĩa của đối phương. Một đĩa hoặc một hàng đĩa bị tràn ra ngoài khi nó được bao quanh ở hai đầu bằng các đĩa có màu đối lập. Một đĩa có thể tràn ra ngoài bất kỳ số lượng đĩa nào trong một hoặc nhiều hàng theo bất kỳ hướng nào (ngang, dọc, chéo)…. (đọc xong tại trang web của họ)

Sự khác biệt giữa trò chơi gốc và trò chơi python này là khi không còn nước đi hợp lệ nào cho một người chơi, trò chơi sẽ kết thúc

Bây giờ bạn có thể chơi trò chơi với một người bạn, hãy tạo một AI để bạn có thể chơi cùng.

Bước 3: Thuật toán Minimax: Tạo kịch bản

Trước khi nói về cách viết điều này trong mã, chúng ta hãy xem xét logic đằng sau nó. Thuật toán minimax là một thuật toán theo dõi ngược, ra quyết định và thường được sử dụng trong các trò chơi hai người chơi, theo lượt. Mục tiêu của AI này là tìm ra nước đi tốt nhất tiếp theo và các nước đi tốt nhất tiếp theo cho đến khi thắng trò chơi.

Bây giờ, thuật toán sẽ xác định nước đi nào là nước đi tốt nhất? Hãy dừng lại và nghĩ xem bạn sẽ chọn nước đi tiếp theo như thế nào. Hầu hết mọi người sẽ chọn nước đi sẽ mang lại cho họ nhiều điểm nhất, phải không? Hoặc nếu họ đã suy nghĩ trước, họ sẽ chọn nước đi sẽ thiết lập một tình huống mà họ có thể giành được nhiều điểm hơn nữa. Cách suy nghĩ thứ hai là cách suy nghĩ của Thuật toán Minimax. Nó hướng tới tất cả các thiết lập bảng trong tương lai và thực hiện động thái có thể dẫn đến nhiều điểm nhất.

Tôi gọi đây là một thuật toán backtracking, bởi vì nó bắt đầu bằng cách đầu tiên tạo và đánh giá tất cả các trạng thái bảng trong tương lai với các giá trị liên quan của chúng. Điều này có nghĩa là thuật toán sẽ chơi trò chơi nhiều nhất có thể (thực hiện các bước di chuyển cho chính mình và đối thủ) cho đến khi mọi tình huống của trò chơi đã diễn ra. Để theo dõi tất cả các trạng thái của bảng (kịch bản), chúng ta có thể vẽ một cái cây (xem trong hình). Cái cây trong hình trên là một ví dụ đơn giản của trò chơi Connect 4. Mọi cấu hình bảng được gọi là trạng thái bảng và vị trí của nó trên cây được gọi là nút. Tất cả các nút ở dưới cùng của cây là trạng thái bảng cuối cùng sau khi thực hiện tất cả các nước đi. Rõ ràng là một số trạng thái hội đồng quản trị tốt hơn cho một người chơi hơn người kia. Vì vậy, bây giờ chúng ta phải làm cho AI chọn trạng thái bảng mà nó muốn đến.

Bước 4: Minimax: Đánh giá cấu hình bo mạch

Để cung cấp giá trị cho các trạng thái trên bàn cờ, chúng ta phải học các chiến lược của trò chơi mà chúng ta đang chơi: trong trường hợp này là các chiến lược của Othello. Vì trò chơi này là cuộc chiến lật đĩa của đối thủ và của bạn, nên vị trí đĩa tốt nhất là vị trí ổn định và không thể bị lật. Ví dụ, góc là nơi mà khi một đĩa được đặt lên, nó không thể đổi sang màu khác. Vì vậy, vị trí đó sẽ vô cùng quý giá. Các vị trí tốt khác bao gồm các mặt của bảng sẽ cho phép bạn lấy rất nhiều đá. Có nhiều chiến lược hơn trên trang web này.

Bây giờ chúng ta có thể gán giá trị cho các vị trí cho mỗi bảng trạng thái của hội đồng quản trị. Khi một vị trí bị chiếm bởi quân cờ của AI, thì bạn cho một số điểm nhất định tùy thuộc vào vị trí đó. Ví dụ: trạng thái bàn cờ mà quân cờ của AI ở trong góc, bạn có thể thưởng 50 điểm, nhưng nếu nó ở vị trí không thuận lợi, quân cờ có thể có giá trị bằng 0. Sau khi tính đến tất cả các giá trị của các vị trí, bạn chỉ định trạng thái bảng một giá trị. Ví dụ: nếu AI có quân cờ ở góc, trạng thái bàn cờ có thể có điểm 50 trong khi trạng thái bàn cờ khác có quân cờ của AI ở giữa có điểm 10.

Có nhiều cách để làm điều này, và tôi có ba phương pháp phỏng đoán khác nhau để đánh giá các mảnh bảng. Tôi khuyến khích bạn thực hiện kiểu khám phá của riêng bạn. Tôi đã tải ba AI khác nhau lên github của mình bởi ba nhà sản xuất khác nhau, với ba phương pháp khám phá khác nhau: Puma.py, erika5.py, nathanh.py.

Bước 5: Thuật toán Minimax: Chọn Nước đi Tốt nhất

Bây giờ sẽ thật tuyệt nếu AI có thể chọn tất cả các bước di chuyển để đến trạng thái bảng với điểm số cao nhất. Nhưng hãy nhớ rằng AI cũng đang chọn nước đi cho đối thủ khi nó tạo ra tất cả các trạng thái trên bàn cờ và nếu đối thủ thông minh, nó sẽ không cho phép AI đạt được điểm số cao nhất trên bàn cờ. Thay vào đó, một đối thủ thông minh sẽ thực hiện động thái để khiến AI đi đến trạng thái bảng thấp nhất. Trong thuật toán, chúng tôi gọi hai người chơi là người chơi tối đa hóa và người chơi giảm thiểu. AI sẽ là người chơi tối đa hóa vì nó muốn nhận được nhiều điểm nhất cho mình. Đối thủ sẽ là người chơi tối thiểu vì đối thủ đang cố gắng thực hiện hành động mà AI nhận được ít điểm nhất.

Khi tất cả các trạng thái bảng được tạo và các giá trị đã được gán cho các bảng, thuật toán bắt đầu so sánh các trạng thái của bảng. Trong các bức ảnh, tôi đã tạo một cái cây để đại diện cho cách thuật toán sẽ chọn các bước di chuyển của nó. Mỗi lần tách trong các nhánh là một nước đi khác nhau mà AI hoặc đối thủ có thể chơi. Ở bên trái của các hàng nút, tôi đã viết liệu trình phát tối đa hóa hay thu nhỏ sẽ hoạt động. Hàng dưới cùng là tất cả các trạng thái bảng với các giá trị của chúng. Bên trong mỗi nút đó là một con số và đó là điểm chúng tôi gán cho mỗi bảng: chúng càng cao thì càng tốt cho AI.

Các định nghĩa: nút cha - một nút kết quả hoặc tạo ra các nút bên dưới nó; nguồn gốc của các nút con - các nút đến từ cùng một nút cha

Các nút trống thể hiện chuyển động mà AI sẽ thực hiện để đạt được trạng thái bảng tốt nhất. Nó bắt đầu bằng việc so sánh các nút con của nút ngoài cùng bên trái: 10, -3, 5. Vì người chơi tối đa hóa sẽ thực hiện nước đi, nó sẽ chọn nước đi sẽ mang lại cho nó nhiều điểm nhất: 10. Vì vậy, sau đó chúng tôi chọn và lưu trữ di chuyển với điểm bảng và ghi nó vào nút cha. Bây giờ 10 đã ở trong nút cha, bây giờ là lượt người chơi tối thiểu hóa. Tuy nhiên, nút mà chúng ta sẽ so sánh 10 là trống, vì vậy chúng ta phải đánh giá nút đó trước khi trình phát thu nhỏ có thể chọn. Vì vậy, chúng ta quay lại lượt của người chơi tối đa và so sánh các nút con của nút liền kề: 8, -2. Tối đa hóa sẽ chọn 8 và chúng tôi viết điều đó trong nút cha trống. Bây giờ thuật toán đã hoàn thành việc điền vào các khoảng trống cho các nút con ở trên nó, trình phát tối thiểu hóa có thể so sánh các nút con đó - 10 và 8 và chọn 8. Sau đó, thuật toán lặp lại quá trình này cho đến khi toàn bộ cây được điền đầy đủ. Ở cuối ví dụ này, chúng ta có điểm 8. Đó là trạng thái bàn cờ cao nhất mà AI có thể chơi để giả sử đối thủ đang chơi tối ưu. Vì vậy, AI sẽ chọn nước đi đầu tiên dẫn đến trạng thái bàn cờ 8, và nếu đối thủ chơi tối ưu, AI sẽ chơi tất cả các nước đi để đến trạng thái bàn cờ 8. (Theo ghi chú trên hình ảnh của tôi)

Tôi biết đó là rất nhiều. Nếu bạn thuộc một trong những kiểu người đó cần có người nói chuyện với bạn để hiểu điều gì đó, thì đây là một vài video mà tôi đã xem để giúp tôi nắm bắt ý tưởng đằng sau điều này: 1, 2, 3.

Bước 6: Thuật toán Minimax: Mã giả

Sau khi bạn hiểu logic đằng sau thuật toán minimax, hãy xem mã giả này (các chức năng phổ biến cho tất cả các mã) từ wikipedia:

chức năng minimax (nút, chiều sâu, tối đa hóaPlayer) là

nếu độ sâu = 0 hoặc nút là một nút đầu cuối thì

trả về giá trị heuristic của nút

nếu tối đa hóaPlayer thì

giá trị: = −∞

cho mỗi nút con làm

giá trị: = max (giá trị, minimax (con, độ sâu - 1, FALSE))

trả lại giá trị

else (* thu nhỏ trình phát *)

giá trị: = + ∞

cho mỗi nút con làm

giá trị: = min (giá trị, minimax (con, độ sâu - 1, TRUE))

trả lại giá trị

Đây là một hàm đệ quy, có nghĩa là nó gọi đi gọi lại chính nó cho đến khi nó đạt đến điểm dừng. Đầu tiên, hàm nhận ba giá trị, nút, độ sâu và đến lượt nó. Giá trị nút là nơi bạn muốn chương trình bắt đầu tìm kiếm. Độ sâu là mức độ bạn muốn chương trình tìm kiếm. Ví dụ, trong ví dụ cây của tôi, nó có độ sâu là 3, bởi vì nó đã tìm kiếm tất cả các trạng thái bàn cờ sau 3 lần di chuyển. Tất nhiên, chúng tôi muốn AI kiểm tra mọi trạng thái của bảng và chọn chiến thắng thắng cuộc, nhưng trong hầu hết các trò chơi có hàng nghìn nếu không phải hàng triệu cấu hình bảng, máy tính xách tay của bạn ở nhà sẽ không thể xử lý tất cả các cấu hình đó. Vì vậy, chúng tôi giới hạn độ sâu tìm kiếm của AI và để nó ở trạng thái bảng tốt nhất.

Mã giả này đang tái tạo quy trình mà tôi đã giải thích trong hai bước trước. Bây giờ chúng ta hãy thực hiện điều này một bước xa hơn và ngay điều này trong mã python.

Bước 7: Tạo AI của bạn với Ai_template.py

Trước khi xem mã Minimax AI của tôi, hãy thử tạo AI của riêng bạn bằng tệp ai_template.py và mã giả mà chúng ta đã nói ở bước trước. Có hai hàm trong mẫu ai được gọi là: def minimax_min_node (bảng, màu) và def minimax_max_node (bảng, màu). Thay vì để hàm minimax gọi chính nó một cách đệ quy, chúng ta có hai hàm khác nhau, gọi lẫn nhau. Để tạo ra heuristic để đánh giá các trạng thái của hội đồng quản trị, bạn sẽ phải tạo chức năng của riêng mình. Có một hàm tạo sẵn trong tệp othello_shared.py mà bạn có thể sử dụng để xây dựng AI của mình.

Sau khi bạn có AI của mình, hãy thử chạy nó với, randy_ai.py. Để chạy hai lối đi đối với nhau, hãy nhập "python othello_gui.py (chèn tên tệp ai).py (chèn tên tệp).py" trong thiết bị đầu cuối mac hoặc nhập "run othello_gui.py (chèn tên tệp ai).py (chèn tên tệp).py”và đảm bảo rằng bạn đang ở đúng thư mục. Ngoài ra, hãy xem video của tôi để biết các bước chính xác.

Bước 8: Đã đến lúc thực hiện AI chiến đấu

Bây giờ, hãy gặp một nhóm bạn máy tính của bạn và khiến họ thiết kế AI của riêng mình! Sau đó, bạn có thể tạo ra một cuộc cạnh tranh và nhờ AI của bạn đánh bại nó. Hy vọng rằng, ngay cả khi bạn không thể xây dựng AI của riêng mình, bạn vẫn có thể hiểu cách hoạt động của thuật toán minimax. Nếu bạn có bất kỳ câu hỏi nào, hãy đăng bất kỳ câu hỏi nào trong phần bình luận bên dưới.