Tic Tac Toe trên Arduino Với AI (Thuật toán Minimax): 3 bước

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

Trong phần có thể hướng dẫn này, tôi sẽ chỉ cho bạn cách xây dựng trò chơi Tic Tac Toe với AI bằng Arduino. Bạn có thể đấu với Arduino hoặc xem Arduino đấu với chính nó.

Tôi đang sử dụng một thuật toán được gọi là "thuật toán minimax", có thể được sử dụng không chỉ để xây dựng AI cho Tic Tac Toe mà còn cho nhiều trò chơi khác như Four in a Row, cờ caro hoặc thậm chí là cờ vua. Các trò chơi như cờ vua rất phức tạp và đòi hỏi các phiên bản thuật toán tinh vi hơn nhiều. Đối với trò chơi Tic Tac Toe của chúng tôi, chúng tôi có thể sử dụng phiên bản đơn giản nhất của thuật toán, tuy nhiên nó khá ấn tượng. Trên thực tế, AI tốt đến mức không thể đánh bại Arduino!

Trò chơi rất dễ xây dựng. Bạn chỉ cần một vài thành phần và bản phác thảo mà tôi đã viết. Tôi cũng đã thêm một lời giải thích chi tiết hơn về thuật toán, nếu bạn muốn hiểu nó hoạt động như thế nào.

Bước 1: Xây dựng và chơi

Để xây dựng trò chơi Tic Tac Toe, bạn sẽ cần các thành phần sau:

• Một Arduino Uno
• 9 đèn LED RGB WS2812
• 9 nút nhấn
• một số dây và cáp jumper

Nối dây các thành phần như được hiển thị trong Fritzing sketch. Sau đó tải mã lên Arduino của bạn.

Theo mặc định, Arduino có lượt đi đầu tiên. Để làm cho mọi thứ thú vị hơn một chút, nước đi đầu tiên được chọn ngẫu nhiên. Sau nước đi đầu tiên, Arduino sử dụng thuật toán minimax để xác định nước đi tốt nhất có thể. Bạn bắt đầu một trò chơi mới bằng cách đặt lại Arduino.

Bạn có thể xem Arduino "suy nghĩ" bằng cách mở Serial Monitor. Đối với mọi nước đi có thể xảy ra, thuật toán sẽ tính toán xếp hạng cho biết liệu nước đi này sẽ dẫn đến thắng (giá trị 10) hay thua (giá trị -10) cho Arduino hoặc hòa (giá trị 0).

Bạn cũng có thể xem Arduino đấu với chính nó bằng cách bỏ ghi chú dòng "#define DEMO_MODE" ở đầu phác thảo. Nếu bạn tải lên bản phác thảo đã sửa đổi, Arduino sẽ thực hiện bước đi đầu tiên một cách ngẫu nhiên và sau đó sử dụng thuật toán minimax để xác định nước đi tốt nhất cho mỗi người chơi trong mỗi lượt.

Lưu ý rằng bạn không thể thắng Arduino. Mọi trò chơi sẽ kết thúc với tỷ số hòa hoặc bạn thua, nếu bạn mắc sai lầm. Điều này là do thuật toán luôn chọn nước đi tốt nhất có thể. Như bạn có thể biết, trò chơi Tic Tac Toe sẽ luôn kết thúc với tỷ số hòa nếu cả hai người chơi không mắc sai lầm. Ở chế độ demo, mọi trò chơi đều kết thúc với tỷ số hòa vì như chúng ta đều biết, máy tính không bao giờ mắc lỗi;-)

Bước 2: Thuật toán Minimax

Thuật toán bao gồm hai thành phần: chức năng đánh giá và chiến lược tìm kiếm. Hàm đánh giá là hàm gán giá trị số cho các vị trí trên bảng. Nếu vị trí là vị trí cuối cùng (tức là vị trí mà người chơi màu xanh hoặc người chơi màu đỏ đã thắng hoặc không có người chơi nào thắng), chức năng đánh giá rất đơn giản: Giả sử Arduino chơi màu xanh lam và người chơi người chơi màu đỏ. Nếu vị trí là vị trí chiến thắng đối với màu xanh lam, hàm sẽ gán giá trị 10 cho vị trí đó; nếu đó là một vị trí chiến thắng cho màu đỏ, hàm sẽ gán giá trị -10 cho vị trí đó; và nếu vị trí là hòa, hàm sẽ gán giá trị bằng 0.

Khi đến lượt Arduino, nó muốn chọn một nước đi tối đa hóa giá trị của hàm đánh giá, bởi vì tối đa hóa giá trị có nghĩa là nó sẽ thích thắng hơn hòa (10 lớn hơn 0) và chấp nhận hòa hơn thua (0 lớn hơn -10). Bằng một lập luận tương tự, đối thủ muốn chơi theo cách mà cô ta giảm thiểu giá trị của hàm đánh giá.

Đối với vị trí không phải là vị trí cuối cùng, thuật toán tính toán giá trị của hàm đánh giá bằng chiến lược tìm kiếm đệ quy. Bắt đầu từ vị trí hiện tại, nó mô phỏng luân phiên tất cả các bước di chuyển mà người chơi màu xanh và người chơi màu đỏ có thể thực hiện. Điều này có thể được hình dung như một cái cây, giống như trong sơ đồ. Khi đến vị trí cuối cùng, nó bắt đầu lùi lại, mang giá trị của hàm đánh giá từ mức đệ quy thấp hơn lên mức đệ quy cao hơn. Nó chỉ định giá trị tối đa (nếu trong bước đệ quy tương ứng là lượt của người chơi màu xanh lam) hoặc mức tối thiểu (nếu trong bước đệ quy tương ứng là lượt của người chơi màu đỏ) của các giá trị của hàm đánh giá từ mức đệ quy thấp hơn đến vị trí trên mức đệ quy cao hơn. Cuối cùng, khi thuật toán đã hoàn thành bước lùi và đến vị trí hiện tại một lần nữa, thì nước đi đó (hoặc một trong các nước đi) có giá trị hàm đánh giá lớn nhất.

Điều này nghe có vẻ hơi trừu tượng nhưng thực ra không khó lắm đâu. Hãy xem xét vị trí được hiển thị ở trên cùng của sơ đồ. Trong bước đệ quy đầu tiên, màu xanh lam có thể thực hiện ba bước di chuyển khác nhau. Blue cố gắng tối đa hóa giá trị của chức năng đánh giá. Đối với mỗi nước đi màu xanh có thể thực hiện, có hai nước đi màu đỏ có thể thực hiện. Màu đỏ cố gắng giảm thiểu giá trị của hàm đánh giá. Hãy xem xét nước đi mà màu xanh dương đóng ở góc trên bên phải. Nếu màu đỏ chơi ở ô chính giữa, màu đỏ đã thắng (-10). Ngược lại, nếu màu đỏ đóng ở ô dưới cùng chính giữa, thì màu xanh sẽ thắng ở nước đi tiếp theo (10). Vì vậy, nếu màu xanh dương đóng ở góc trên bên phải, màu đỏ sẽ phát ở ô trung tâm, vì điều đó làm giảm thiểu giá trị của hàm đánh giá. Tương tự, nếu màu xanh lam phát ở ô dưới cùng chính giữa, thì màu đỏ sẽ lại phát ở ô trung tâm vì điều đó giảm thiểu chức năng đánh giá. Ngược lại, nếu màu xanh dương đóng ở ô chính giữa, thì không quan trọng nước đi của màu đỏ, màu xanh sẽ luôn thắng (10). Vì màu xanh lam muốn tối đa hóa chức năng đánh giá, nó sẽ phát ở ô trung tâm, vì vị trí đó dẫn đến giá trị của hàm đánh giá (10) lớn hơn hai nước đi còn lại (-10).

Bước 3: Khắc phục sự cố và các bước tiếp theo

Nếu bạn nhấn một nút và đèn LED khác với đèn LED tương ứng với nút sáng lên, có thể dây trên chân A0-A2 hoặc 4-6 bị lẫn lộn hoặc bạn đã kết nối các đèn LED không đúng thứ tự.

Cũng lưu ý rằng thuật toán không nhất thiết phải luôn chọn một nước đi sẽ cho phép Arduino giành chiến thắng nhanh nhất có thể. Trên thực tế, tôi đã dành một khoảng thời gian để gỡ lỗi thuật toán vì Arduino đã không chọn một nước đi có thể là một nước đi chiến thắng. Tôi mất một thời gian cho đến khi tôi nhận ra rằng thay vào đó nó đã chọn một nước đi đảm bảo rằng nó sẽ thắng một nước đi sau đó. Nếu bạn muốn, bạn có thể thử sửa đổi thuật toán để nó luôn thích một nước đi thắng hơn là thắng sau.

Một phần mở rộng có thể có của dự án này là sử dụng thuật toán để xây dựng AI cho ngón chân cái 4x4 hoặc thậm chí 5x5. Tuy nhiên, lưu ý rằng số lượng vị trí mà thuật toán cần kiểm tra tăng lên rất nhanh. Bạn sẽ cần phải tìm cách làm cho chức năng đánh giá thông minh hơn bằng cách xác định các giá trị cho các vị trí không phải là vị trí cuối cùng, dựa trên khả năng vị trí đó tốt hay xấu đối với người chơi được đề cập. Bạn cũng có thể cố gắng làm cho việc tìm kiếm trở nên thông minh hơn bằng cách dừng quá trình đệ quy sớm nếu một bước đi không đáng để khám phá thêm so với các bước thay thế.

Arduino có lẽ không phải là nền tảng tốt nhất cho các phần mở rộng như vậy vì bộ nhớ hạn chế của nó. Đệ quy cho phép ngăn xếp phát triển trong quá trình thực thi chương trình và nếu ngăn xếp phát triển quá nhiều, nó có thể làm hỏng bộ nhớ chương trình, dẫn đến treo máy hoặc hành vi thất thường. Tôi chọn Arduino cho dự án này chủ yếu vì tôi muốn xem liệu nó có thể thực hiện được hay không và cho mục đích giáo dục, chứ không phải vì đó là lựa chọn tốt nhất cho loại vấn đề này.