Chiến lược tối ưu cho Connect 4

WeakC4 hoặc Chưng cất một vật thể mới nổi

2swap

Xem giải pháp Kết nối 4 tại đây

WeakC4 là giải pháp không cần tìm kiếm, có kiến thức thấp cho 7x6 Connect 4, được xây dựng bằng cách xác định ngôn ngữ mô tả cách chơi hoàn hảo cho một tập hợp con nhỏ các nút, và sau đó xác định một cây mở nhỏ chỉ chứa các nút đó dưới dạng lá.

Trang web này cung cấp chiến lược chính thức cho người chơi đầu tiên tối ưu Kết nối bốn , về cơ bản khác với giải pháp mạnh và yếu như Fhourstones :

Nó phụ thuộc vào rất ít thông tin đến mức nó phù hợp với khoảng 150 kilobyte như được hiển thị, ngay cả trước khi các cặp đối xứng không trùng lặp.
Nó không sử dụng tìm kiếm trong thời gian chạy, chạy ở O(wh) thời gian phức tạp để chọn di chuyển.
Nó có thể được hiển thị toàn bộ và hiển thị trong thời gian thực.
]Nó minh họa trực quan và xác nhận sự tồn tại của các khe hở, đường kẻ và các biến thể đặc biệt khó khăn đã được biết đến để kết nối 4 người chơi.

Giải pháp mạnh và yếu

Trang web này hiển thị giải pháp yếu cho trò chơi Connect Four. Nói tóm lại, điều này có nghĩa là nó cung cấp đầy đủ thông tin để đảm bảo chiến thắng cho lần đầu tiên nếu người chơi đầu tiên chơi theo đề xuất của giải pháp yếu, nhưng không bình luận về các vị thế tùy ý. (Nếu có, điều đó sẽ làm cho nó trở thành một giải pháp mạnh ).

Như một ví dụ động lực: người chơi 1 (sau đây gọi là "Đỏ") có thể giành chiến thắng bằng cách chơi ở cột trung tâm ở nước đi đầu tiên và sau đó làm theo đề xuất của giải pháp yếu, nhưng sẽ không được đảm bảo để giành chiến thắng nếu đĩa đầu tiên được chơi ở nơi khác. Giải pháp yếu không chứa thông tin về những gì sẽ xảy ra trong các cột khác - Đối với Red quan tâm, sẽ là dư thừa để tìm hiểu những nhánh đó, vì chúng không tốt.

Một giải pháp mạnh sẽ chứa giá trị lý thuyết trò chơi cho mọi vị trí, trong khi giải pháp yếu này chỉ chứa đủ thông tin để đảm bảo chiến thắng cho Red, không bao gồm bất kỳ vị trí nào khác.

Về mặt lý thuyết đồ thị, chúng ta có thể nghĩ các loại giải pháp này là đồ thị, trong đó giải pháp mạnh là toàn bộ cây trò chơi và giải pháp yếu là biểu đồ con đóng dưới một vài ràng buộc quan trọng cho mỗi nút sẽ được thảo luận sau.

Kết nối 4 đã được giải quyết mạnh mẽ và thoạt nhìn dường như làm cho cuộc thảo luận về các giải pháp yếu kém trở nên tranh cãi. Trong thực tế, tôi nghĩ điều ngược lại thường đúng hơn. Một giải pháp yếu có rất nhiều lợi thế so với một giải pháp mạnh, chẳng hạn như:

Dấu chân dữ liệu nhỏ hơn. Bạn cần phải "ghi nhớ" ít thông tin hơn để có thể chơi một cách hoàn hảo.
Tiết lộ cấu trúc cơ bản. Một giải pháp yếu phụ thuộc vào, và phơi bày, sự hiểu biết về cấu trúc của trò chơi.
Hình dung. Một giải pháp yếu có thể được hình dung theo cách mà một giải pháp mạnh (14tb không nén, 350gb nén) không thể.

Một giải pháp mạnh mẽ là một cách tiếp cận chung, ngây thơ để giải quyết bất kỳ trò chơi nào không đòi hỏi sự hiểu biết về cấu trúc. Một giải pháp yếu, tùy thuộc vào việc lựa chọn các nhánh chiến thắng để bao gồm và bỏ qua, để lại chỗ cho sự lựa chọn sáng tạo và có thể được sử dụng để thể hiện những hiểu biết sâu sắc về cấu trúc của trò chơi được đề cập.

Giải pháp yếu "tốt"

Hãy tưởng tượng mục tiêu của bạn là tham dự một giải đấu Cờ vua và chơi thật hoàn hảo. Một lựa chọn, chiến lược A, sẽ đến mà không cần bất kỳ sự chuẩn bị nào và đọc qua mọi biến thể có thể có của trò chơi khi ngồi. Một lựa chọn khác, chiến lược B, sẽ xuất hiện trong giải đấu đã ghi nhớ giá trị lý thuyết trò chơi của từng vị trí, điều này sẽ cho phép bạn chơi hoàn hảo mà không cần bất kỳ tìm kiếm nào cả.

Theo một nghĩa nào đó, hai cách tiếp cận này trái ngược nhau. Mối quan hệ quá mức đầu tiên về tính toán không phụ thuộc vào kiến thức, trong khi mối quan hệ quá mức thứ hai về kiến thức không phụ thuộc vào tính toán.

Tuy nhiên, theo một nghĩa khác, chúng rất giống nhau - trong cả hai trường hợp, chúng ta có thể coi 'sản phẩm dữ liệu' của hai chiến lược là giống hệt nhau - bất kể khi nào giá trị của một vị trí được tính toán, trước giải đấu hoặc trong thời gian đó, người chơi được yêu cầu trong thời điểm này để đến cùng một lượng thông tin - cùng một cây, cùng một 'sản phẩm dữ liệu'. Cả hai người chơi sẽ xây dựng cây một cách hiệu quả kết quả từ việc cắt tỉa alpha-beta, một người sẽ làm như vậy trong suốt cuộc thi và một người sẽ làm như vậy trước đó.

Thay vào đó, một người chơi thông minh hơn sẽ chọn chiến lược X để cân bằng hai cách tiếp cận. Khi lượng kiến thức cần thiết để ghi nhớ đến một độ sâu nhất định tăng theo cấp số nhân và lượng tính toán cần thiết để đọc ra một trò chơi kết thúc cũng tăng theo cấp số nhân, chúng ta có thể giảm thiểu cả hai số lượng thông qua một chiến lược liên quan đến việc ghi nhớ một nửa trò chơi và dựa vào tính toán cho phần còn lại. Nói cách khác, người chơi này sẽ giảm tổng lượng dữ liệu được xử lý bằng cách tối ưu hóa sự cân bằng giữa ghi nhớ và tính toán.

A Tuyệt vời Giải pháp yếu

Cho đến nay, chúng ta đã coi cây trò chơi, hoặc 'sản phẩm dữ liệu' như một loại đối tượng entropic vô hạn chỉ có thể tiếp cận chính thức thông qua tìm kiếm ngây thơ. Trong thực tế, có rất nhiều chỗ cho việc áp dụng trực giác của con người và phân tích heuristic, đó là bằng chứng cho thấy cây trò chơi này dư thừa thông tin - nó có một số cấu trúc với nó, và do đó nó có thể được nén. Điều này không phải là một bất ngờ - trong chừng mực nó được tạo ra tương ứng với một bộ quy tắc nhất quán, (các quy tắc của chính trò chơi), nó nên được dự kiến sẽ thể hiện một mức độ tự tương tự.

Mục tiêu thiết kế của dự án này là không dựa vào tính toán thời gian thực vì tôi hy vọng sẽ hình dung ra một giải pháp đầy đủ. Sự tồn tại của một bước tính toán ngầm ẩn thông tin tồn tại trong giải pháp của chúng tôi, và do đó chúng tôi sẽ không hình dung trung thực toàn bộ cây trò chơi.

Nếu chúng ta thông minh, chúng ta có thể loại bỏ hoàn toàn bước tính toán.

Không có gì trong cuộc sống là miễn phí. Nói một cách đơn giản, điều này có nghĩa là cần phải tính toán trước sâu hơn nhiều để chọn một cách thông minh những nhánh cần đề xuất để ghi nhớ, bởi vì hóa ra một số nhánh thưa thớt trong cây trò chơi khổng lồ này mang lại ]hoàn toàn đều đặn và có khuôn mẫu - tiếp tục có "thủ thuật đơn giản" đòi hỏi cả tính toán và ghi nhớ.

Đây là một câu đố đầy động lực để chứng minh thách thức kỹ thuật đằng sau tính toán trả trước này:

Đây là một cây trò chơi có hướng, trong đó các nước đi của Red được hiển thị bằng màu Đỏ và Yellow được hiển thị bằng màu Vàng. Các nút có "thủ thuật đơn giản" được gạch chéo với màu xanh lá cây và đã được vẽ dưới dạng các nút lá.

Cố gắng xác định cây con nhỏ nhất có thể đóng vai trò là một giải pháp yếu thay mặt cho Red cho trò chơi này. Nói cách khác, công việc của bạn là loại bỏ các cạnh màu đỏ để mọi nút từ đỏ đến di chuyển còn lại duy trì chính xác một cạnh màu đỏ đi ra, mà không cắt xén bất kỳ cạnh màu vàng nào. Nhấp vào hình ảnh để tiết lộ câu trả lời.

Thách thức cơ bản của dự án này khi đó là gấp đôi:

Để tìm một ngôn ngữ thể hiện "các thủ thuật đơn giản" cho một khối lượng nút quan trọng đủ lớn trong cây trò chơi và
Để tìm một cây "cuốn sách mở" để ghi nhớ, tất cả các nút lá đều có "thủ thuật đơn giản" như vậy.

Tôi nghĩ rằng đáng để suy ngẫm về thực tế là cách tiếp cận này không chỉ đơn thuần là một "chiến lược" để kết nối hoàn hảo 4 lần chơi, mà quan trọng hơn là một bài tập trong thực sự hiểu hình dạng của cây trò chơi của cấu trúc có hoa văn phức tạp này xuất hiện từ các quy tắc của Connect 4. Làm thế nào bạn có thể xác định các thủ thuật thông minh, hoặc ngôn ngữ để mô tả chúng, hoặc một cái cây nhỏ có lá chứa tất cả những thủ thuật thông minh đó, mà không hiểu về hình thức nội tại của trò chơi? Tìm hiểu thêm về điều này trong phần "Suy ngẫm".

Giải pháp điểm yếu tối thiểu

Có một sự tinh tế ở đây cần được giải quyết. Câu đố trên yêu cầu giải pháp yếu tối thiểu. Tuy nhiên, dự án này không tìm kiếm một biểu đồ có kích thước tối thiểu mà là một biểu đồ đòi hỏi ít thông tin hơn để thể hiện. Theo cùng một cách mà một tệp văn bản lặp đi lặp lại có thể được nén, chúng tôi lạm dụng thực tế là cây trò chơi liên quan đến dự phòng thông tin để giảm kích thước của biểu đồ và đưa ra một giải pháp không phải là đồ thị nhỏ về mặt lý thuyết, mà là thông tin về mặt lý thuyết nhỏ.

Claimeven

Trước khi tôi xác định toàn bộ ngôn ngữ để thể hiện những "thủ thuật đơn giản" này, hãy để tôi cung cấp một vị trí kết nối thúc đẩy 4. Đến lượt của Yellow, nhưng Red đã có một mánh khóe đơn giản trong đầu. Bạn có thể tìm thấy nó không?

[liên kết tương tác]

Bí quyết là Red chỉ đơn thuần chơi call-and-response với Yellow, chơi trong cùng một cột với nước đi cuối cùng của Yellow. Nếu Red làm điều này, Red sẽ giành chiến thắng trong cột trung tâm sau vài chục lượt. Chúng ta có thể hình dung bảng trò chơi cuối cùng, bất kể Vàng tiếp tục như thế nào:

Lưu ý rằng vị trí của câu đố chỉ có một cột duy nhất với một số khoảng trống còn lại, và đó là hàng mà Red cần để giành chiến thắng. Tất cả các cột khác đều có số khoảng trắng chẵn còn lại. Điều này rất quan trọng cần lưu ý, bởi vì nếu một số cột có số khoảng trống lẻ, thì Yellow có thể cố tình lấp đầy một trong số chúng và Red sẽ buộc phải di chuyển, phá vỡ mô hình gọi và trả lời.

Vì chiến lược này liên quan đến việc tô đỏ các hàng 2, 4 và 6, chiến lược này được Victor Allis đặt tên là Claimeven trong bài báo của mình Một cách tiếp cận dựa trên kiến thức về Connect-Four.

Thật không may, không có đủ nhiều vị trí trong Connect 4 có thể được giải quyết chỉ bằng Claimeven thuần túy, vì vậy chúng ta cần khái quát hóa thêm một chút.

Ngôn ngữ trạng thái ổn định

Ngôn ngữ tôi chọn để diễn đạt những "thủ thuật đơn giản" này sử dụng "Sơ đồ trạng thái ổn định", trông như thế này:

Điều này nên được coi là một "bảng cheat" cho Red biết làm thế nào để tiếp tục chơi cho đến khi chiến thắng, cho vị trí được rút ra trong hình. Sơ đồ có chú thích trên các ô vuông lưới sẽ được Red sử dụng để xác định những việc cần làm tiếp theo. Khi Đỏ chơi, sơ đồ không thay đổi.

Để xác định Red nên làm gì, chúng tôi xem xét tất cả các động thái pháp lý mà Red có thể thực hiện ngay bây giờ. Chúng tôi hoàn toàn bỏ qua các chú thích "trôi nổi".

Động thái đã chọn của Red được chọn bằng cách làm theo danh sách các thứ tự ưu tiên sau:

Thực hiện nước đi chiến thắng, nếu có.
Chặn một nước đi chiến thắng của đối thủ, nếu có.
Chơi trên! (phát âm là 'khẩn cấp'), nếu có.
Chơi trên @ (phát âm là 'miai'), chỉ khi có sẵn chính xác .
Chỉ chơi trên | (phát âm là 'claimodd') nếu nó nằm trên một hàng lẻ (nếu không bỏ qua nó), hoặc một ô trống (phát âm là'claimeven') nếu nó nằm trên một hàng chẵn. Lưu ý rằng claimeven được biểu diễn bằng một khoảng trống vì nó hiển thị một lô , vì vậy thật tốt khi nghĩ về claimeven như một loại 'hành vi mặc định'.
Chơi trên dấu +, nếu có.
Chơi trên an =, nếu có.
Chơi trên -.

Khi tạo các sơ đồ này, tôi đảm bảo rằng luôn có chính xác một động thái duy nhất được đề xuất bởi danh sách ưu tiên này. Nói cách khác, trong số các sơ đồ nổi bật trên trang web của tôi, bạn sẽ không bao giờ tìm thấy một sơ đồ có hai trường hợp khẩn cấp. Điều này tương ứng với trình độ chuyên môn trước đó rằng một nút chuyển đổi màu đỏ sang di chuyển có chính xác một cạnh đi.

Tôi sẽ không thảo luận về tất cả các quyết định thiết kế đã hướng dẫn tôi sử dụng ngôn ngữ cụ thể này. Để có được một số trực giác, tôi khuyên bạn nên xem biểu đồ và tự mình khám phá một số sơ đồ trạng thái ổn định.

Tôi cũng không đưa ra tuyên bố rằng nó hoàn hảo, hoặc tối ưu, hoặc bất cứ điều gì tương tự. Tôi hội tụ vào thiết kế này chủ yếu thông qua rất nhiều thử nghiệm và sai sót. Ngoài ra còn có một loạt các vị trí được coi là đơn giản bởi các chuyên gia Connect 4 không có Sơ đồ trạng thái ổn định - chủ yếu trong số đó là các vị trí sử dụng chiến lược "ba tỷ lệ cược". Triple-odds đòi hỏi một chút kiến thức toàn cầu, mà ngôn ngữ Steady State của tôi quá đơn giản để diễn đạt. Tôi nghi ngờ biểu đồ có thể bị thu nhỏ theo hệ số 4 hoặc hơn nếu một ngôn ngữ được tìm thấy có thể chỉ đơn giản là thể hiện tỷ lệ ba.

Hãy dành một chút thời gian để xem xét rằng có một giao dịch giữa sự phức tạp và biểu cảm của ngôn ngữ và kích thước biểu đồ của Trạng thái ổn định. Tôi đã chọn sự cân bằng tốt nhất có thể. Nếu bạn có ý tưởng hay hơn, tôi khuyên bạn nên thử :)

Phương pháp tiếp cận kỹ thuật

Tóm lại, đây là mô tả về phần còn lại của phương pháp kỹ thuật đã cho phép tôi tạo biểu đồ:

Một thuật toán di truyền đã được sử dụng để dự đoán nhanh các Trạng thái ổn định ứng cử viên cho một biểu đồ nhất định, sau đó được xác minh bằng vũ lực. [Mã
Tôi đã sử dụng mọi phương pháp để chọn ra những cành đẹp nhất và được cắt tỉa nhiều nhất có thể. Điều này liên quan đến rất nhiều tìm kiếm và quay lại, nhưng trên thực tế, tôi không thể tìm kiếm các nhánh tối thiểu ở độ sâu cao hơn khoảng 8 [Mã. Việc tìm kiếm các nhánh tốt nhất trong phần mở đầu bao gồm rất nhiều thử nghiệm và sai sót, một số trực giác của riêng tôi với tư cách là người chơi Connect 4 và thu hút các đề xuất về việc cắt bớt nút từ những người chơi khác. Tất nhiên, tôi không đảm bảo tính tối ưu của biểu đồ này. Tôi hy vọng nó có thể được nén thêm khoảng 25 phần trăm nữa mà không cần sửa đổi ngôn ngữ Trạng thái ổn định.
Sự trải rộng biểu đồ theo hướng lực đã được sử dụng để tạo trực quan hóa biểu đồ, trải rộng một cách thích hợp trong không gian 3d. [Mã. Lực phản chiếu được áp dụng để hướng dẫn biểu đồ phản ánh cấu trúc phản chiếu của trò chơi.

Kết quả

Chúng tôi đã phát triển giải pháp không cần tìm kiếm, ít kiến thức để kết nối 4 bằng cách xác định ngôn ngữ mô tả cách chơi hoàn hảo cho một tập hợp con nhỏ các nút rồi chọn một cây mở nhỏ chỉ chứa các nút đó làm lá.

Giải pháp thu được có các thuộc tính sau:

Nó không sử dụng tìm kiếm trong thời gian chạy, chạy ở độ phức tạp thời gian O(wh) để chọn nước đi ở bất kỳ vị trí hợp lệ nào.
Đã giảm xuống tổng số nút dưới 10.000 (có thể giảm thêm, hãy xem trang biểu đồ để biết số lượng trực tiếp.) Khoảng 2/3 trong số này các nút là các lá biểu thị trạng thái ổn định.
Nó phụ thuộc vào rất ít thông tin nên nó phù hợp với khoảng 150 kilobyte, thậm chí bao gồm cả các vị trí phản chiếu.
Mức nén này có thể được so sánh với Allis (1988), người đã tìm thấy cuốn sách mở đầu gồm 500.000 nút cho phép phát trong thời gian thực nhưng vẫn gọi tìm kiếm.
Việc duyệt cây này và xác nhận tính hợp lệ của nó chạy nhanh hơn một chút trên máy của tôi so với việc giải quyết trò chơi trực tiếp bằng Fhourstones, theo một nghĩa nào đó, ngụ ý rằng đây là "bằng chứng bằng tính toán" nhanh nhất cho tuyên bố rằng kết nối 4 là trò chơi một người chơi sẽ thắng. Điều này thậm chí xảy ra khi không có bất kỳ bằng chứng thông minh nào về tính chính xác của trạng thái ổn định mà tôi vẫn chưa triển khai - chúng tôi chỉ kiểm tra chúng bằng vũ lực.
Cả hai chỉ số này có thể giảm thêm khoảng một nửa vì chúng bao gồm tìm kiếm và lưu trữ các vị trí phản chiếu.
Sớm hay muộn, tôi sẽ làm bộ bài mở đầu Anki bằng cách sử dụng những cành cây đã phát hiện được để những người mong muốn nỗ lực ghi nhớ có thể làm được điều đó.
Nó có thể được hiển thị toàn bộ và hiển thị trong thời gian thực.
Nó minh họa và xác nhận một cách trực quan sự tồn tại của các đoạn mở, lời thoại và biến thể đặc biệt đầy thách thức đã được biết đến để kết nối 4 người chơi.

Tất cả các giải pháp connect 4 khác hiện có sẵn đều có một loại giao diện "có thể truy vấn", trong đó người dùng nhắc người giải một vị trí và người giải trả về một giá trị lý thuyết trò chơi. Thay vào đó, bằng cách chắt lọc giải pháp của chúng tôi thành một cấu trúc dữ liệu nhỏ, chúng tôi có thể vạch ra trò chơi trong không gian để khám phá bằng hình ảnh một cách trực quan.

Một Bộ bài Anki được tạo từ thân không có lá của biểu đồ, nhằm mục đích ghi nhớ phần mở đầu của con người!

Phản ánh

Cây trò chơi của Connect 4 là một đối tượng mới xuất hiện từ một bộ quy tắc đơn giản. Điều này tương tự với rất nhiều cấu trúc khác mà chúng ta giao tiếp. Vật lý có thể có cùng bản chất, trong đó một tập hợp phương trình khá đơn giản ở cấp độ lượng tử mang lại vô số hiện tượng vĩ mô bất ngờ như tay nắm cửa và ngón tay cái đối diện. Thông qua việc lặp lại các quy tắc tính toán, các hiện tượng khác nhau trở nên sống động ở độ phân giải quan sát khác nhau.

Và tôi nghĩ đó là một điểm quan trọng- độ phân giải. Những cấu trúc này thường có một "chồng" hiện tượng xuất hiện ở các mức độ phân giải khác nhau. Trong vật lý, chúng ta thấy các sinh vật bao gồm các tế bào được tạo thành từ các phân tử được tạo thành từ các nguyên tử, mỗi phân tử hoạt động theo cách được mô tả tốt nhất trong lĩnh vực nghiên cứu liên quan của nó. Hãy so sánh điều này với biểu hiện tối thiểu của chúng tôi về chiến lược chiến thắng của Connect 4, thể hiện hình thức khác nhau ở các cấp độ khác nhau. Trong phần cuối của trò chơi, có những thủ thuật đơn giản này phụ thuộc vào cấu trúc đều đặn, có khuôn mẫu của cây tiếp tục, nhưng được trừu tượng hóa xa hơn về phía phần mở, các cấu trúc vĩ mô nổi lên phát triển thành các biến thể dễ nhận biết và các phần mở đã được đặt tên. Tất nhiên, đây là do thiết kế nhưng tôi nghi ngờ đây là lựa chọn thiết kế cần thiết để đạt được kết quả mong muốn là thể hiện hình dạng của đối tượng với càng ít dữ liệu càng tốt.

Một nhà vật lý bi quan với thái độ giản lược có thể nói rằng thực tế chỉ bao gồm các hiện tượng hạt và thế giới vĩ mô có thể phân đoạn, có thể đặt tên là ảo ảnh hoặc sự xây dựng của phát minh của con người. Tuy nhiên, nhà vật lý này rơi vào cái bẫy triết học tương tự của các đối thủ Cờ vua khi theo đuổi các chiến lược A và B ngây thơ, loại bỏ phương thức hiểu biết dựa trên kiến thức thông qua nhận dạng mẫu, thay vào đó chuyển sang cơ học thô.

Connect 4 ở một vị trí khá kỳ diệu xét về độ phức tạp. Nó đã chín muồi với các đối tượng mới nổi, nhưng nó đủ đơn giản để hình dung và suy luận chính thức về mặt tính toán. Tôi không biết về bất kỳ nỗ lực nào khác nhằm tạo ra giải pháp yếu có ít thông tin cho Connect 4 mà không cần tìm kiếm, vì vậy cỡ mẫu của tôi là một, nhưng đối với tôi, có vẻ như kiểu nén này phụ thuộc vào cách tiếp cận đa độ phân giải, hoàn toàn trái ngược với triết lý của nhà vật lý giản lược như một phương tiện khả thi để tiếp cận các vật thể nổi tùy ý.

Tôi hy vọng người đọc có thể đánh giá cao điều này nỗ lực không chỉ đơn thuần như một chiến lược cho trò chơi Connect 4 mà quan trọng hơn là một bài tập chính thức trong việc rút ra sự hiểu biết từ một đối tượng mới xuất hiện- một vấn đề bị bỏ qua bởi các phương pháp tính toán truyền thống để giải các trò chơi trên bàn cờ.