'Othello' đã được giải chưa?
(arxiv.org)- Đã được chứng minh bằng tính toán rằng Othello/Reversi 8×8 có kết quả cuối cùng là hòa khi cả hai bên chơi hoàn hảo, qua đó đạt trạng thái được xem là giải yếu theo tiêu chuẩn của nhóm nghiên cứu
- Không gian tìm kiếm rất lớn, với khoảng 10^58 biên bản ván đấu khả dĩ và khoảng 10^28 trạng thái bàn cờ, nên đây vẫn là bài toán khó hơn nhiều so với các trường hợp đã được giải trước đó như checkers
- Kết quả lần này tìm ra giá trị lý thuyết trò chơi của vị trí khởi đầu và chiến lược để đạt được giá trị đó, chứ không phải giải mạnh bằng cách tính toàn bộ các vị trí trung gian
- Nhóm nghiên cứu cho biết họ đã dùng tìm kiếm heuristic dựa trên phần mềm Othello và alpha-beta search, đồng thời quy mô tìm kiếm cần cho lời giải chính xác nhỏ hơn dự đoán trước đây
- Dữ liệu gốc và chương trình để tái hiện kết quả đã được công bố trên GitHub, Zenodo và figshare, nên có thể được dùng như một trường hợp có thể kiểm chứng trong nghiên cứu giải các trò chơi chiến lược thuần túy
Lời giải bằng tính toán cho Othello
- Othello trên bàn 8×8 đã được giải yếu, và giá trị lý thuyết trò chơi của vị trí khởi đầu được tính là hòa
- Nếu cả hai bên chơi tối ưu và không mắc sai lầm, ván đấu sẽ kết thúc với kết quả hòa, và nghiên cứu này đã chứng minh điều đó bằng tính toán
- Figure 1 trình bày một biên bản ván đấu tối ưu cùng kết quả cuối cùng
- Nếu có bất kỳ sai lệch nào khỏi chuỗi nước đi đó ở bất kỳ thời điểm nào, phần mềm của nhóm nghiên cứu có thể đảm bảo hòa hoặc thắng khi đóng vai bên đối thủ
- Kết quả này phù hợp với dự đoán hòa từ lâu của các chuyên gia Othello, nên nhóm nghiên cứu cho rằng bản thân kết quả không phải điều quá bất ngờ
Phạm vi lời giải và giá trị lý thuyết trò chơi
- Giải một trò chơi thông tin hoàn hảo nghĩa là xác định kết quả cuối cùng khi cả hai bên đều chơi hoàn hảo, tức giá trị lý thuyết trò chơi
- Các trò chơi đã được giải thường được chia thành ba mức
- Giải siêu yếu (ultra-weakly solved): chỉ biết giá trị lý thuyết trò chơi của vị trí bàn cờ ban đầu
- Giải yếu (weakly solved): biết giá trị lý thuyết trò chơi của vị trí khởi đầu và chiến lược để hai bên đạt được giá trị đó trong giới hạn tài nguyên tính toán hợp lý
- Giải mạnh (strongly solved): đã tính được kết quả của mọi vị trí khả dĩ có thể xuất hiện trong ván đấu
- Nghiên cứu lần này là trường hợp giải yếu cho Othello, không phải giải mạnh bằng cách tính mọi thế cờ có thể có
- checkers cũng được nêu như một trò chơi đã được giải yếu theo đúng nghĩa này
Vì sao Othello tồn tại quá lâu như một bài toán chưa giải
- Othello là trò chơi phổ biến có chiều sâu chiến thuật lớn, được phát minh ở Anh vào thế kỷ 19, rồi ở thế kỷ 20 lan rộng dưới hình thức hiện nay tại Nhật Bản và được chơi trên toàn thế giới
- Giải vô địch thế giới đã được tổ chức hằng năm từ 1977, cho thấy mức độ phổ biến toàn cầu của trò chơi
- Không gian tìm kiếm là cực kỳ lớn
- Trung bình khoảng 10 nước đi cho mỗi vị trí
- Trung bình khoảng 58 nước đi cho toàn bộ một ván
- Khoảng 10^58 biên bản ván đấu khả dĩ
- Khoảng 10^28 trạng thái bàn cờ khả dĩ
- Quy mô này được cho là lớn hơn rất nhiều so với các trò chơi khó đã được giải cho đến nay, đặc biệt là checkers
- Chính vì không gian tìm kiếm quá lớn, Othello đã là một bài toán dài hạn của khoa học máy tính
Cách tìm kiếm và hiệu quả tính toán
- Nhóm nghiên cứu đã dùng alpha-beta search để hướng tới mục tiêu giải yếu
- Thuật toán giải trò chơi thay đổi tùy theo mục tiêu và đặc tính của trò chơi
- Với giải yếu, alpha-beta search thường được sử dụng
- Với giải mạnh, retrograde analysis thường được áp dụng
- Với các câu đố có chuỗi lời giải rất dài, những phương pháp như df-pn search đã được phát triển
- alpha-beta search là thuật toán duyệt đồ thị trò chơi tuần tự theo chiều sâu, nên chỉ song song hóa đơn thuần thì khó cải thiện mạnh hiệu quả tìm kiếm
- Nhiều phương pháp đã được nghiên cứu cho tìm kiếm song song
- Trong môi trường bộ nhớ chia sẻ, YBWC và Lazy SMP là những cách tiếp cận phổ biến
- Trong môi trường bộ nhớ phân tán, APHID và ABDADA được nêu là các thuật toán liên quan
- Trong môi trường bộ nhớ phân tán, các điều kiện như băng thông và độ trễ giữa các nút khác biệt rất lớn, nên nhà phát triển có thể phải chọn thuật toán phù hợp với môi trường hoặc tự phát triển thuật toán mới
- Ngay cả khi dùng cụm máy tính hiện đại, việc giải Othello vẫn là rào cản lớn, và bước đột phá đến từ việc chỉnh sửa phần mềm Othello hiện đại để nâng hiệu quả tìm kiếm
Các trò chơi khác đã được giải và khả năng ứng dụng
- Trước Othello, trường hợp gần đây nhất trong số các bài toán khó được giải là checkers
- Connect Four, Qubic, Go-Moku, Nine Men’s Morris, Awari cũng được liệt kê là những trò chơi không tầm thường đã được giải
- Độ khó của việc giải trò chơi nhìn chung phụ thuộc rất lớn vào số lượng vị trí hay tình huống bên trong trò chơi
- Việc giải trò chơi không chỉ dùng để làm rõ kết quả cuối cùng mà còn có thể được ứng dụng để tạo puzzle dựa trên trò chơi đó
- Nhóm nghiên cứu cung cấp dữ liệu gốc và chương trình phục vụ tái lập kết quả trên GitHub, Zenodo, figshare
1 bình luận
Ý kiến trên Hacker News
Nói rằng “trong số 2.958.551 vị trí, đã chọn 2.587 vị trí để đặt giả thuyết về kết quả, và nếu tất cả các giả thuyết này đều đúng thì chứng minh được vị trí ban đầu là hòa”, nhưng lại không giải thích chi tiết hơn
Nghe giống như trò chơi chưa được giải hoàn toàn, mà tác giả đã rất cố gắng tìm chuỗi nước đi thắng nhưng không tìm ra
Có viết rằng “có nhiều cách chọn một tập con có thể chứng minh vị trí ban đầu là hòa, nhưng chúng tôi đã thu được một tập con nhỏ bằng Algorithm 1”
Algorithm 1 được mô tả là nhận điểm số dự đoán của mọi vị trí còn 50 ô trống, rồi trả về một tập con sao cho nếu mọi vị trí trong tập con đó được giải và lời giải khớp với dự đoán, thì vị trí ban đầu cũng được giải theo hệ quả
Nhìn chung cách trình bày của bài báo không trực quan. Có thể tác giả đúng, nhưng có lẽ cần ngồi xuống tử tế để lần theo logic; ấn tượng ban đầu của tôi là hoài nghi
Kiểu chứng minh này cũng có ở nơi khác. Chẳng hạn định lý bốn màu cũng được quy về một số hữu hạn cấu hình rồi tô màu thủ công
Script ở https://github.com/eukaryo/reversi-scripts/blob/main/reversi... chơi hoàn hảo với giả định rằng toàn bộ dữ liệu là đúng. Các script khác trong kho dùng dữ liệu được tính từ lời giải các vị trí còn 36 ô trống, và mức này có vẻ máy phổ thông cũng làm được
Về bản chất, cấu trúc có vẻ là tra cứu một bảng dưới 300GB chứa mọi vị trí còn 37–64 ô trống có thể đạt tới từ lời giải yếu, còn các vị trí còn tối đa 36 ô trống thì giải bằng
-solvecủa edaxOthello là một trò chơi rất hay để cho thấy chỉ với heuristic cơ bản cũng có thể mạnh đến mức nào
Khi ván chơi diễn ra, có những ô tuyệt đối không nên đi, và ngược lại cũng có những ô nên đi nếu có thể
Chỉ cần triển khai những quy tắc như vậy cũng đã thành một đối thủ khá ổn, và thật thú vị khi thấy con người nhanh chóng gán “trí tuệ” cho cả những thứ rất đơn giản
Bài đó nói họ cho một ứng dụng dùng heuristic đơn giản tương tự đấu với một ứng dụng có chiến lược “lật được nhiều quân nhất” cũng đơn giản y hệt nhưng tệ thảm hại
Thuật toán heuristic thắng áp đảo; tôi nhớ là 60–4 hoặc còn tệ hơn thế
Khi còn 19 ô trống, nó giải hoàn toàn phần còn lại của ván, và điều đó khá đáng kinh ngạc
Othello từng có cả trên máy chơi game LCD 10 đô la chạy bằng hai viên pin AA
Nếu bạn quan tâm đến trò chơi này, Giải vô địch Othello thế giới, vốn cũng được các nhà nghiên cứu khoa học máy tính và trí tuệ nhân tạo ưa thích, hiện đang diễn ra tại Rome, Ý
Các trận đấu được phát trực tiếp trên liveothello.com và YouTube @WorldOthello
Tôi cũng tự hỏi liệu Othello có giống cờ đam, tức là phần lớn các trận đỉnh cao kết thúc hòa, hay không
Tuyệt
Khoảng 15 năm trước, tôi từng giải một trò đơn giản hơn mà tôi chơi với anh/chị/em mình. Đó là một trò châu Phi với khoảng 10 hố ở mỗi bên bàn và các viên đá bên trong
Tôi viết một engine alpha-beta và nó tìm ra một chiến lược luôn thắng phi lý đúng với cách chơi của chúng tôi. Sau đó tôi bỗng thắng mọi ván, và anh/chị/em tôi không bao giờ muốn chơi cùng nữa. Một cuộc đối đầu điển hình giữa nhà khoa học máy tính và bác sĩ đo thị lực
Nhìn những người châu Phi lớn tuổi chơi Mancala thì có rất nhiều điều để học. Họ đi rất nhanh, và trò này cũng có cảm giác giống poker, nơi gian lận trở thành một phần của cuộc chơi
Nếu rải đá đủ nhanh, bạn có thể bỏ qua một bát hoặc thả thêm một viên đá để kiếm lợi thế
Tôi không thành thạo đến mức đó và chơi với gia đình nên không gian lận. Dù vậy nó trở thành một trò rất khác. Giống như khác biệt giữa các quý bà Anh thong thả chơi Mahjong bên tách trà và chơi ăn tiền trong sòng bạc Trung Quốc
Nếu thắng quá nhiều hoặc thua quá nhiều thì sẽ không còn thích chơi nữa
Nhưng tôi không hiểu nghề bác sĩ đo thị lực thì liên quan gì ở đây
Chuyện này có thật không? Việc tác giả chỉ có một người và thuộc một startup deep learning mà tôi chưa từng nghe tới khiến tôi thấy hơi lạ
Có lẽ nó đang trong quá trình bình duyệt?
Và Othello không hẳn ở tầm như giả thuyết Riemann. Nó chưa được nghiên cứu nhiều đến vậy, và có thể vẫn còn vài “quả thấp dễ hái” sót lại
Othello là một trong những trò chơi rất phù hợp để chơi cùng trẻ nhỏ
Luật đơn giản, có các mẫu hình đáng để học, và cảm giác lật được hàng loạt quân cũng rất thú vị. Quan trọng hơn cả, nó vui như nhau không chỉ với trẻ em mà cả người lớn
Tôi vẫn có thể tận hưởng đủ nhiều mà không áp đảo một đứa trẻ 6 tuổi, đồng thời cũng không cảm thấy như một trò chơi thuần may rủi đơn giản
https://mancala.fandom.com/wiki/Hus
Về lý thuyết không có yếu tố may rủi, nhưng trên thực tế vì các phản ứng dây chuyền nên không thể tính xa đến vậy
Bàn chơi có thể dễ dàng tự làm
Nếu muốn chơi thử, đây là thứ tôi đã làm cùng bọn trẻ: https://jawj.github.io/fliptiles
Người chơi “AI” rất yếu
Tôi đã học được một trò chơi mới
Máy tính được 33 điểm, tôi được 31 điểm
Nếu nghĩ Othello là tầm thường, hãy thử Zebra
Trang web của tác giả gốc: http://radagast.se/othello/
Mã nguồn GitHub: https://github.com/hoshir/zebra
Điều tôi thích ở Othello là mâu thuẫn giữa hành động và lãnh thổ
Trong suốt ván chơi, việc đặt một nước trong lượt của mình theo nghĩa nào đó lại bất lợi cho mình, nhưng vẫn bắt buộc phải đặt
Vì vậy, cho đến khi không gian trở nên quá nhỏ và đến lúc phải giành lại ảnh hưởng chắc chắn, bạn cần chiếm giữ nhưng vẫn giữ vị trí nhỏ và ở phía trong
Liên quan đến điều này, cũng có việc chơi Reversi 6x6 một cách hoàn hảo
https://mame.github.io/6x6-reversi-oracle/
Nguồn: https://twitter.com/mametter/status/1476379841004183556
Trước giờ tôi không biết rằng 8x8 vẫn chưa được giải