Tic-Tac-Toe là trò chơi dành cho 2 người, những người này thay phiên nhau đánh dấu các khoảng trống trong lưới 3x3. Người chơi thành công trong việc đặt ba điểm của họ thành một hàng ngang, dọc hoặc chéo sẽ thắng trò chơi
TIC Tac Toe. py là triển khai python của trò chơi. Có hai chế độ để chơi
- Người chơi đơn [Chống lại máy tính]
- 2 người chơi
Chế độ 2 người chơi lặp đi lặp lại lấy thông tin đầu vào từ cả hai người chơi, đồng thời đảm bảo xem có ai thắng hay không. Dưới đây là một đoạn của trò chơi 2 người chơi
Chế độ chơi đơn sử dụng thuật toán MiniMax khiến máy tính vô địch. Ngay cả khi người chơi chơi nước đi tối ưu nhất mọi lúc, kết quả cuối cùng sẽ là hòa. Cách chơi của chế độ Một người chơi được hiển thị bên dưới. Mỗi khi bạn di chuyển, máy tính sẽ tự động chơi
Trong bài viết này, bạn tìm hiểu về Thuật toán Minimax và cách A. I. đại lý làm cho trò chơi Tic-Tac-Toe của bạn trở nên vô địch. Sau đây, tôi sẽ giới thiệu các khái niệm về Minimax và mã python để triển khai Minimax. [Đối với toàn bộ mã, hãy truy cập liên kết GitHub ở phía dưới. ]
Con người [X] vs Đặc vụ Minimax [O]
Đề cương
- TIC Tac Toe
- thuật toán tối thiểu
- giá trị tối thiểu
- giá trị tối đa
- Mã Python cho Minimax
- Cái gì tiếp theo
TIC Tac Toe
Tic-Tac-Toe là một trò chơi trong đó hai người chơi tìm kiếm các lượt luân phiên để hoàn thành một hàng, một cột hoặc một đường chéo với ba chữ O hoặc ba chữ X được vẽ trong khoảng trống của một lưới gồm chín ô vuông
Xem xét kịch bản Tic-Tac-Toe sau đây
thuật toán tối thiểu
Bạn sẽ chơi trò chơi Tic-Tac-Toe với máy tính bằng Thuật toán Minimax mà nó không bao giờ thua nếu thực hiện đúng. Bây giờ, Thuật toán Minimax chính xác là gì và tại sao bạn nên sử dụng nó? . Nhìn vào sự hiện diện của omi trong tương lai. Còn về game thì Minimax thường dùng cho game đối kháng. Có hai giá trị tiện ích được gọi là giá trị tối thiểu và tối đa giúp A. I. đại lý để quyết định bước đi tối ưu tiếp theo của nó. Đối với trường hợp này, Đại lý ưu tiên di chuyển với giá trị tối đa là 10 và sau đó chọn giá trị tối thiểu là -10. [Đại lý muốn giành chiến thắng hơn là ngăn đối thủ của mình giành chiến thắng] Nếu không có bất kỳ nước đi nào có giá trị tối thiểu hoặc tối đa lớn hơn hoặc nhỏ hơn 10, nó sẽ chọn nước đi có giá trị tuyệt đối cao nhất của giá trị tối thiểu cộng với giá trị tối đa. Một lần nữa, Minimax giả định rằng đối thủ của nó chơi tối ưu
- giá trị tối thiểu
Đây là giá trị mà A. I. đại lý tìm cách giảm thiểu tổn thất có thể xảy ra trong trường hợp xấu nhất. Đối với mỗi làn ngang, dọc, chéo trên vị trí bàn cờ, giá trị tối thiểu -1 cho mỗi làn nếu 3 vị trí không có nước đi nào của bạn. Sau đó, đối với mỗi đối thủ di chuyển thêm trên một làn, bạn -1 [Chỉ khi bạn không di chuyển trên làn đó]. Tuy nhiên, nếu có 2 nước đi của đối thủ, giá trị tối thiểu của bạn sẽ trở thành -10 [Kẻ thù của bạn sẽ thắng nếu bạn không chặn vị trí đó. ]
Giả sử bạn là người chơi [ X ], hãy xem xét kịch bản bảng sau
bảng tiện ích tối thiểu
Đối với vị trí bàn cờ 1, không có X trên hàng [làn ngang] và cột [làn dọc] của nó. Điều này có nghĩa là bằng cách đặt dấu X ở đó, bạn đã loại bỏ 2 làn có thể dành cho O để giành chiến thắng. Ngoài ra, trên hàng đó [làn ngang], có chữ O nên bạn -1 ngoài -2. Chúng tôi không trừ điểm từ đường chéo vì nó chứa dấu X mặc dù có dấu O. Đối với vị trí bàn cờ 6, giá trị tối thiểu là -10 vì cột của nó [làn dọc] có 2 Os
- giá trị tối đa
Đây là giá trị mà A. I. tìm cách tối đa hóa lợi ích có thể cho một tình huống tốt nhất. Đối với mỗi làn ngang, dọc, chéo trên vị trí bàn cờ, bạn +1 mỗi làn nếu 3 vị trí không có nước đi của đối thủ. Sau đó, với mỗi bước di chuyển bổ sung mà bạn thực hiện trên làn đường, bạn +1 lại [Chỉ khi kẻ thù của bạn không thực hiện bất kỳ bước di chuyển nào trên làn đường đó]. Tuy nhiên, nếu có 2 nước đi của bạn, giá trị tối đa của bạn sẽ trở thành +10 [Bạn thắng bằng cách di chuyển ở đó. ]
Giả sử bạn là người chơi [ X ], hãy xem xét kịch bản bảng sau
bảng tiện ích tối đa
Đối với vị trí bàn cờ 1, bạn thêm 2 nếu không có đối thủ [O] di chuyển trên cột của nó [đường dọc] và đường chéo. Ngoài ra, bạn đã di chuyển [ X ] trên đường chéo để bạn thêm 1 vào giá trị tối đa dẫn đến 3. Đối với vị trí bàn cờ 8, giá trị tối đa là 10 vì bạn đã thực hiện 2[ X ] di chuyển trên cột của nó [làn dọc]. Bằng cách đặt nước đi của bạn ở vị trí 8, bạn thắng
Mã Python cho Minimax
Hãy xem Mã để tạo các giá trị tối thiểu và tối đa
- Dòng 1–7
Đã nhập bản sao thư viện. Đã định nghĩa một lớp gọi là Ô để chuyển đổi từng vị trí trên bảng được truyền ở dòng 9 thành các đối tượng riêng biệt lưu trữ 4 mục. vị trí, chỉ mục 2D của vị trí đó, giá trị tối đa và giá trị tối thiểu để truy cập dễ dàng hơn
2. Dòng 9–19
Đã xác định một hàm có tên là generate_cells nhận đầu vào của bảng Tictactoe [phải là 2 chiều] và trả về một bảng tiện ích cho từng vị trí trên bảng. Bảng tiện ích là một danh sách 2D, mỗi vị trí là một danh sách chứa 3 mục. vị trí, giá trị tối đa và giá trị tối thiểu của nó. Hàm tạo giá trị max và min bằng cách gọi hàm max_val[dòng 21] và hàm min_val[dòng 32] trên dòng 15–16
3. dòng 21–30
Đã xác định một hàm gọi là max_val đảm nhận vị trí bảng và chỉ mục 2D của nó và trả về giá trị tối đa. Trên dòng 24, hàm check_horizontal tạo giá trị tối đa bằng cách kiểm tra làn đường ngang của vị trí
Trên dòng 25, hàm check_vertical tạo giá trị tối đa bằng cách kiểm tra làn dọc của vị trí
Ở dòng 27, hàm left_diagonal tạo ra các giá trị lớn nhất bằng cách kiểm tra làn đường chéo từ trên cùng bên trái xuống dưới cùng bên phải của vị trí
Trên dòng 28, hàm right_diagonal tạo ra các giá trị tối đa bằng cách kiểm tra làn đường chéo trên cùng bên phải đến dưới cùng bên trái của vị trí
4. Dòng 32–40
Đã xác định một hàm có tên là min_val đảm nhận vị trí bảng và chỉ mục 2D của nó và trả về một giá trị tối thiểu. Ở dòng 35, hàm check_horizontal tạo ra các giá trị tối thiểu bằng cách kiểm tra làn ngang của vị trí. Ở dòng 36, hàm check_vertical tạo ra các giá trị tối thiểu bằng cách kiểm tra làn dọc của vị trí. Ở dòng 37, hàm left_diagonal tạo ra các giá trị tối thiểu bằng cách kiểm tra làn đường chéo từ trên cùng bên trái sang dưới cùng bên phải của vị trí. Ở dòng 38, hàm right_diagonal tạo ra các giá trị nhỏ nhất bằng cách kiểm tra đường chéo trên cùng bên phải đến dưới cùng bên trái của vị trí
Cái gì tiếp theo
Bây giờ bạn đã có thể hiểu các khái niệm chung đằng sau Minimax. Chương trình của tôi tương đối đơn giản và nó có thể được tối ưu hóa hơn nữa bằng cách triển khai các khái niệm nâng cao hơn như cây tiện ích và cắt tỉa alpha-beta
cây tiện ích. Về cơ bản, một cây quyết định chứa các trạng thái bảng có thể được cung cấp cho một bảng, được đánh giá bằng các giá trị tối thiểu và tối đa. Xem xét ví dụ sau
cắt tỉa alpha-beta. Thuật toán tìm kiếm tìm cách giảm số lượng nút được đánh giá bởi thuật toán minimax trong cây tìm kiếm của nó để cải thiện hiệu quả thời gian của chương trình
Ghi chú. Thuật toán Minimax phù hợp với Tic-Tac-Toe trong đó A. I. đại lý làm cho trò chơi này không thể đánh bại. Tuy nhiên, tic-tac-toe không tận dụng hết tiềm năng của Minimax nơi trò chơi cờ vua có thể là một đại diện tốt hơn. Cờ vua vận dụng hoàn toàn sức mạnh của Minimax. điều khiển hoàn hảo sức mạnh của máy tính, có khả năng thu hồi hoàn hảo, có bộ nhớ hoàn hảo, không có tình huống nào là không được tính toán và tạo ra rất nhiều tình huống có thể xảy ra trước so với con người. So với Cờ vua… Tictactoe có ít tình huống khả thi hơn mà máy tính có thể đưa ra với bàn cờ 3 nhân 3
Mã python có trên GitHub. https. //github. com/729557989/MiniMax-Algorithm-with-tictactoe-optimized
Câu hỏi? . Vui lòng để lại nhận xét hoặc phản hồi của bạn trong phần bình luận. Cảm ơn vì đã đọc nó