Tôi nghĩ rằng minimax không phải là lựa chọn tốt nhất của thuật toán cho dấu chấm và hộp. Đối với những câu chuyện đầy đủ về trò chơi này, bạn thực sự cần phải đọc cuốn sách The Dots and Boxes Game: Sophisticated Child's Play by Elwyn R. Berlekamp, nhưng tôi sẽ cung cấp cho bạn một bản tóm tắt ngắn gọn ở đây.
Berlekamp thực hiện một số quan sát mạnh mẽ. Đầu tiên là chiến lược chéo chéo , mà tôi cho rằng bạn biết (được mô tả trong số Wikipedia page on the game).
Nguyên tắc thứ hai là quy tắc chẵn lẻ cho chuỗi dài. Điều này theo sau ba sự kiện về phần lớn các trò chơi được chơi tốt:
- Chuỗi dài sẽ được phát ở cuối trò chơi.
- Sẽ có một hình chữ thập kép trong mỗi chuỗi ngoại trừ chuỗi cuối cùng.
- Người chơi đầu tiên phải chơi trong bất kỳ chuỗi dài nào mất trò chơi.
cộng với ràng buộc rằng số lượng dấu chấm bạn bắt đầu, cộng với số lượng chéo kép, bằng số lượt trong trò chơi. Vì vậy, nếu có mười sáu chấm để bắt đầu, và có một chéo đôi, sẽ có mười bảy lượt. (Và trong phần lớn các trò chơi, điều này có nghĩa là người chơi đầu tiên sẽ thắng.)
Điều này đơn giản hóa việc phân tích vị trí giữa trò chơi rất lớn. Ví dụ, hãy xem xét vị trí này với 16 dấu chấm và 11 di chuyển được chơi (vấn đề 3.3 từ cuốn sách của Berlekamp). Di chuyển tốt nhất ở đây là gì?
Vâng, nếu có hai chuỗi dài, sẽ có một lai kép, trò chơi sẽ kết thúc sau khi thêm sáu di chuyển (16 + 1 = 11 + 6), và các cầu thủ phải di chuyển sẽ mất . Nhưng nếu chỉ có một chuỗi dài, sẽ không có đường chéo kép và trò chơi sẽ kết thúc sau 5 lần di chuyển khác (16 + 0 = 11 + 5) và người chơi sẽ di chuyển sẽ thắng. Vậy làm thế nào người chơi có thể di chuyển đảm bảo rằng chỉ có một chuỗi dài? Động thái này chỉ giành hy sinh hai hộp:
Minimax sẽ tìm thấy động thái này nhưng với công việc nhiều hơn nữa.
Quan sát thứ ba và mạnh mẽ nhất là các dấu chấm và hộp là impartial game: các chuyển động có sẵn giống nhau bất kể lượt chơi của ai và ở vị trí điển hình phát sinh trong quá trình chơi (tức là, có chứa chuỗi dài hộp) cũng là một normal game: người chơi cuối cùng sẽ chiến thắng. Sự kết hợp của các thuộc tính này có nghĩa là các vị trí có thể được phân tích tĩnh bằng cách sử dụng Sprague–Grundy theory.
Đây là ví dụ về cách tiếp cận này mạnh mẽ như thế nào, sử dụng hình 25 từ cuốn sách của Berlekamp.
Có 33 di chuyển tốt ở vị trí này, và một trò chơi nổi chơi kéo dài khoảng 20 di chuyển nhiều hơn, vì vậy tôi sẽ ngạc nhiên nếu nó là khả thi cho minimax để hoàn thành phân tích của mình một cách hợp lý thời gian. Nhưng vị trí có một chuỗi dài dài (chuỗi sáu ô vuông trong nửa trên) để có thể phân tích tĩnh. Vị trí chia thành ba phần có giá trị là nimbers:
Những nimbers có thể được tính bằng cách lập trình năng động trong thời gian O (2 n) cho một vị trí với n di chuyển còn lại, và bạn có thể sẽ muốn lưu lại kết quả cho nhiều vị trí nhỏ thông dụng.
Nimbers thêm bằng cách sử dụng độc quyền hoặc: * 1 + * 4 + * 2 = * 7. Vì vậy, di chuyển chiến thắng duy nhất (một động thái làm giảm nim-sum thành * 0) là thay đổi * 4 thành * 3 (để tổng số vị trí là * 1 + * 3 + * 2 = * 0). Bất kỳ trong ba màu đỏ di chuyển chấm được chiến thắng:
Edited thêm: Tôi biết rằng bản tóm tắt này không thực sự tạo thành một thuật toán như vậy, và lá rất nhiều câu hỏi chưa trả lời.Đối với một số câu trả lời bạn có thể đọc cuốn sách của Berlekamp. Nhưng có một chút khoảng trống khi nói đến việc mở đầu: chuỗi đếm và lý thuyết Sprague – Grundy thực sự chỉ thực tế ở giữa và cuối cùng. Để mở, bạn sẽ cần phải thử một cái gì đó mới: nếu nó là tôi tôi muốn bị cám dỗ để thử Monte Carlo tree search đến điểm mà các chuỗi có thể được tính. Kỹ thuật này làm việc kỳ diệu cho các trò chơi của Go và có thể được sản xuất ở đây quá.
Đây là một gợi ý tuyệt vời, nhưng có vẻ quá phức tạp đối với dự án của tôi. –
@CaseyPatton: sau đó bạn sẽ có xác suất 100% bị mất một chương trình thực hiện điều này, trừ khi có một heuristic được biết đến cho trò chơi này hoàn toàn ra lệnh chơi tối ưu. Ngay cả một tìm kiếm brute-force ngụ ý làm điều này. – ninjagecko
@CaseyPatton: Đây thực tế là thuật toán tốt nhất và được sử dụng nhiều nhất cho tất cả các trò chơi tổng bằng không. ** Sự khác biệt giữa các đại lý ngày nay là các chẩn đoán được sử dụng, và không phải là sử dụng nó hay không **. Ngoài ra, tôi tin rằng bạn có thể tìm thấy một thực hiện hiện có cho nó trên trăn trên mạng, và thực hiện các thuật toán min-max không phải là khó anyway. – amit