Thuật toán giải quyết trò chơi (Buttonia, biến thể tắt đèn)

Question

Tôi đang cố gắng tạo ra một chức năng giải thể cho một thuật toán trò chơi. Về cơ bản một hàm trả về true hoặc false cho một game nào đó nếu nó có khả năng giải được hay không.

Trò chơi là Buttonia.com (hiện không triển khai thuật toán), một loại trò chơi tắt đèn. Về cơ bản Bạn có một mạng lưới các nút, mỗi nút, khi được nhấn, sẽ thay đổi trạng thái của một số hàng xóm của nó. Hiện tại tôi tạo ra một cấu hình trò chơi ngẫu nhiên và sau đó áp dụng chẩn đoán càng nhiều càng tốt. Phần còn lại được quyết định bằng tìm kiếm bạo lực.

Tiến trình của tôi cho đến nay là tạo ra một hệ phương trình để mô hình hóa trò chơi. Khi mỗi nút cần phải thay đổi trạng thái một số lẻ lần để kết thúc trong tình trạng xuống, Đó là phương trình sẽ là:

button_A = 1 - (button_1 + button_2 + ... + button_X)% 2

Trong đó nút_1 qua nút_X là trạng thái của các nút có hiệu ứng trên button_A. Một số nút có thể được giải quyết ngay lập tức, nếu chúng không phụ thuộc vào người khác. Đối với phần còn lại, tôi thử một cấu hình cho đến khi tôi nhận được một cuộc xung đột và sau đó trở lại theo dõi.

Thuật toán hiện tại này là thiết thực cho các cấu hình trò chơi nhỏ hơn. Tôi đã thử nghiệm nó từ trò chơi 3x3 lên đến kích thước 10x10. Trường hợp 6x6 gần với giới hạn trên để chơi thực tế.

Các phương trình vô cùng cắt giảm không gian tìm kiếm từ vũ lực, làm cho nó thực tế. Có thể có một cách hoàn toàn toán học để giải quyết hệ phương trình.

---

mẫu 3x3 trò chơi trong ascii (từ buttonia.com/?game=2964):

||# 
-o- 
+#| 

Legend: 
o = affect only self 
- = affect left and right neighbors 
| = affect above and below neighbors 
+ = affect left, right, above and below neighbors 
# = affect all 8 surrounding neighbors 

Solution, nhấn các nút này: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

phương trình cho trò chơi này:

Button_0_0 = 1 - (0) % 2 
Button_1_0 = 1 - (Button_2_0) % 2 
Button_2_0 = 1 - (0) % 2 
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2 
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2 
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2 
Button_0_2 = 1 - (Button_1_2) % 2 
Button_1_2 = 1 - (Button_0_2) % 2 
Button_2_2 = 1 - (Button_1_2) % 2 

giải pháp tiềm năng:

Thay đổi các hàm toán học để tránh sự cần thiết của mô đun cho phép chúng ta di chuyển các từ bên trái sang phải, tạo ra thiết lập ma trận gọn gàng mà chúng ta cần cho phương thức Gaussian. Vì vậy, hai phương trình đầu tiên sẽ lần lượt chuyển sang:

-1 = -1*B00 + 0*B10 + 0*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22 
-1 = 0*B00 + -1*B10 + -1*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22 

giải pháp thảo luận ở đây: Gaussian Elimination with custom operators

Bắt gần hơn. Hầu như đã sẵn sàng để đăng giải pháp đầy đủ: Inverting binary networks

Answer 1

Đây là một hệ phương trình tuyến tính trên F , lĩnh vực khác có chứa hai nguyên tố 0 và 1.

Bạn có thể giải quyết nó giống như phương trình tuyến tính bình thường, nhưng bạn phải làm số học modulo 2 .

Edit: Đại số tuyến tính đối với trường hợp này hoạt động giống hệt như đối với số thực, ngoại trừ việc bạn phải thay thế các hoạt động:

• cộng và trừ trở thành độc quyền hoặc, tức là 0 + 0 = 0 , 0 + 1 = 1, 1 + 1 = 0.

• Nhân trở nên VÀ: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• Division chỉ có thể bởi một: 0/1 = 0, 1/1 = 1.

Tất cả các hệ số trong phương trình của bạn và các giá trị có thể có của ẩn số là 0 hoặc 1.

Vì vậy, các modulo không tát ở bên ngoài các phương trình như bạn đã viết, nó là ẩn trong các hoạt động.

Nếu hệ phương trình của bạn không thể giải được, bạn sẽ nhận được một phương trình 0 = 1, rõ ràng là không thể giải được.

Answer 2

Thay vì bắt đầu bằng trạng thái ngẫu nhiên, tại sao không tạo vị trí bắt đầu bằng cách lật công tắc ngẫu nhiên, tức là làm việc ngược trở lại từ trạng thái đã giải quyết sang trạng thái bắt đầu. Bằng cách đó bạn chỉ tạo ra các câu đố có thể giải quyết được.

Answer 3

Vì đây không phải là vấn đề giới hạn thời gian (giả sử nó có thể được thực hiện trong vòng chưa đầy một ngày), tôi có thể tìm kiếm chiều rộng giới hạn chiều sâu sau đó mỗi động thái tiếp theo sau mỗi lần di chuyển.

Nó sẽ chậm, tuy nhiên gần như chắc chắn sẽ tìm thấy câu trả lời, nếu có!

Answer 4

Điều này trông gần giống như một hệ phương trình tuyến tính (ngoại trừ mod 2), vì vậy bạn có thể điều chỉnh một trong các kỹ thuật thông thường để giải quyết chúng - ví dụ: giảm hàng của hệ thống ở dạng ma trận (wikipedia).

Answer 5

Giả sử bạn đã xây dựng hệ phương trình và giải quyết chúng tốt nhất có thể, nhưng một số hàng kết thúc bằng tất cả 0 ở bên trái phương trình (tôi đại diện cho phương trình như ma trận tăng cường) Giả sử bạn đã cố gắng giải quyết hệ thống trong vòng Z2 (trong điều kiện thực tế cho ví dụ cụ thể này có nghĩa là thay đổi duy nhất là 1 + 1 = 0, mọi thứ khác vẫn giữ nguyên ... ergo toán tử duy nhất chúng ta cần là XOR) và kết thúc với ma trận sau:

1001 1 
0100 1 
0011 0 
0000 0 

Như bạn có thể thấy trong ví dụ này, hàng thứ 4 là 0, có nghĩa là chúng tôi chưa có câu trả lời. Tuy nhiên hãy nghĩ về nó theo cách này: một hàng của tất cả 0 có nghĩa là biến đó không ảnh hưởng đến giải pháp. Đó thực sự là một sự lựa chọn từ ngữ nghèo nàn ... nó chỉ có nghĩa là chúng có thể có giá trị (và chúng ta may mắn ở đây, vì tất cả các giá trị có nghĩa là 1 hoặc 0, không giống với số thực ... Vì vậy, điều này có nghĩa là chúng ta có 2 các giải pháp cho hệ thống này).

Đây là lý do tại sao: những gì bạn cần biết tại thời điểm này là cột ngoài cùng bên phải vẫn chứa giải pháp hợp lệ cho trò chơi của bạn. Hãy lấy dòng đầu tiên chẳng hạn. Nó nói rằng

button_0 + button_3 = 1 

nhưng chúng ta biết rằng nút 3 có thể là bất cứ điều gì (vì dòng 3 là tất cả 0). Tại điểm này nút 3 là 0 (cột ngoài cùng bên phải trên hàng 3 là 0 tại thời điểm này) vì vậy bây giờ chúng tôi biết điều đó có nghĩa là

button_0 + 0 = 1 

vì vậy chúng tôi biết thực tế là button_0 là 1.Do đó trong hệ thống này mặc dù chúng tôi không thể tìm ra trực tiếp button_3, chúng tôi vẫn có một giải pháp hợp lệ.

Ma trận được tạo ở trên đủ để kiểm tra khả năng giải thể. Nếu một hàng chứa tất cả 0s sau đó nó được về cơ bản nói rằng

nothing = nothing 

hay, để hình dung rõ hơn lý do tại sao các công trình này,

0x = 0 

có ý nghĩa, hệ thống vẫn còn hiệu lực. Tuy nhiên, nếu chúng ta gặp phải một hàng đó là tất cả 0s trừ bit ngoài cùng bên phải, tức là

0000 1 

đó sẽ được nói

0x = 1 

đó là không thể vì vậy bây giờ chúng ta biết rằng hệ thống không thể được giải quyết, vì chúng ta không thể giải quyết một tình huống không thể như thế này. Vì vậy, trong một nutshell, cố gắng và giải quyết các phương trình là tốt nhất bạn có thể, đừng lo lắng nếu bạn không thể tìm hiểu chính xác những gì một số các biến được, miễn là bạn không gặp phải, bất cứ lúc nào, các hàng không thể tôi chỉ đề cập sau đó trò chơi là giải quyết được.

Nhưng điều gì sẽ xảy ra nếu chúng tôi muốn giải pháp ngắn nhất cho hệ thống? Ở đây chúng tôi sẽ phải kiểm tra tất cả các giải pháp có thể. Chúng ta có button_3 có thể là bất kỳ giá trị nào, do đó có nghĩa là bất kỳ 1 nào trong cột 3 có nghĩa là hàng mà nó được tìm thấy, bị ảnh hưởng bởi button_3. Giả sử chúng tôi muốn kiểm tra xem giải pháp sử dụng button_3 có ngắn hơn không. Chúng tôi tạo một ma trận khác, nhưng đặt button_3 thành 1 bây giờ (vì chúng tôi đã thiết lập trước đó rằng nó có thể là bất kỳ thứ gì và chúng tôi đã có 0 trong đó, vì vậy bây giờ chúng tôi kiểm tra 1). Bây giờ chúng ta kết thúc với ma trận sau:

1001 1 
0100 1 
0011 0 
0001 1 

Chúng tôi giảm mà nhiều như chúng tôi có thể và bây giờ kết thúc với ma trận này:

1000 0 
0100 1 
0010 1 
0001 1 

này vẫn còn là một giải pháp hợp lệ, tuy nhiên chúng ta có thể thấy rằng giải pháp dài hơn (yêu cầu 3, thay vì 2 lần nhấn nút) do đó chúng tôi loại bỏ nó. Chúng ta phải làm điều này cho mỗi hoán vị thiết lập các hàng chúng ta tìm thấy là tất cả 0 đến 1. Do đó nếu chúng ta có x hàng là tất cả 0, thì hệ thống có x^2 giải pháp, và chúng ta phải kiểm tra tất cả chúng.