iChomp

Trò chơi tổ hợp: trò chơi hai người với thông tin hoàn hảo và kết quả thắng hoặc thua và không có cơ hội di chuyển.

Trò chơi vô tư: các trò chơi tổ hợp trong đó các bước di chuyển được phép chỉ phụ thuộc vào vị trí chứ không phụ thuộc vào một trong hai người chơi hiện đang di chuyển. Ngoài ra, các khoản thanh toán là đối xứng. Nói cách khác, sự khác biệt duy nhất giữa người chơi 1 và người chơi 2 là người chơi 1 đi trước. Ví dụ: Chomp.

Trò chơi đảng phái: trò chơi không vô tư. Ví dụ: Cờ vua.

Chơi bình thường: Người chơi thực hiện nước đi cuối cùng sẽ thắng, tức là người chơi không thể di chuyển, tức là người không có gì để lấy đi, sẽ thua.

Misère Play: Người chơi thực hiện nước đi cuối cùng THUA.

Chomp: trò chơi được giới thiệu trên trang web trò chơi của chúng tôi sử dụng một góc phần tư và Misère Play.

Trò chơi Nim như nó được chơi trên trang trò chơi của chúng tôi sử dụng chơi bình thường hay sai?
- Trò chơi Nim của chúng tôi sử dụng lối chơi misère, bởi vì người chơi tham gia trận đấu cuối cùng sẽ thua trò chơi.
Trò chơi Chomp như được chơi trên trang trò chơi Chomp của chúng tôi sử dụng cách chơi bình thường hay sai?
- Trò chơi Chomp như được chơi trên trang trò chơi của chúng tôi sử dụng trò chơi misère, vì người chơi lấy kẹo cuối cùng sẽ thua.
Tại sao nó không có ý nghĩa để sử dụng chơi bình thường cho Chomp?
- Sử dụng cách chơi bình thường có nghĩa là ai lấy ô cuối cùng sẽ thắng. Do đó, người chơi di chuyển trước có thể giành chiến thắng ngay lập tức bằng cách lấy ô ở góc trên bên trái.
Trò chơi iChomp như được chơi trên trang web này có sử dụng Normal hay Misère Play không?
- Trong iChomp, người chơi lấy ô cuối cùng sẽ thắng, vì vậy trò chơi này sử dụng Chơi bình thường.
Bạn có gợi ý về cách người ta có thể thay đổi bảng Chomp để sử dụng Chơi bình thường và vẫn chơi cùng một trò chơi không?
- Người ta có thể bắt đầu với một vị trí mà kẹo (bị nhiễm độc) ở góc trên bên trái đã bị thiếu ngay từ đầu. Lấy viên kẹo cuối cùng từ một bảng như vậy có nghĩa là người ta sẽ giành chiến thắng trong Chơi bình thường. Trong Misère Play và với ô này thì người chơi khác sẽ phải lấy nó và thua, đó là kết quả tương tự.
  
  Do đó, có một ô góc trên bên trái và sử dụng Misère Play hoặc không có ô này ngay từ đầu trò chơi và sử dụng Chơi bình thường đều chính xác là cùng một trò chơi.

Trò chơi iChomp được thiết kế để trở thành sự kết hợp của bốn Chomp các trò chơi được chơi cùng một lúc, tất cả đều theo luật Chơi bình thường. Điều này làm cho trò chơi đẹp hơn ở hai khía cạnh, sẽ được giải thích dưới đây. Ngoài ra, iChomp không khó chơi hơn Chomp nếu người ta áp dụng lý thuyết Sprague-Grundy, cũng được mô tả dưới đây.

Lớp trò chơi mà nó áp dụng là Trò chơi tổ hợp vô tư. Lý thuyết này làm hai điều cho chúng ta:
1. Nó cung cấp cho chúng ta một thuật toán xác định cho mỗi trò chơi (tức là mỗi vị trí) một số (chúng ta sẽ gọi nó là giá trị SG) sao cho số là 0 nếu và chỉ khi đó là vị trí thua cuộc (được gọi là 'vị trí P' trong tài liệu về lý thuyết trò chơi tổ hợp với 'P' chỉ ra rằng 'người chơi 'p' đã chơi một nước đi chiến thắng). Điều đó có nghĩa là nếu giá trị SG này là 1, 2, 3,... thì đây là một vị trí chiến thắng (được gọi là vị trí 'N' trong văn học). Trong trường hợp đó, bất cứ ai di chuyển 'n'ext có thể thực thi chiến thắng nếu chơi tối ưu.
2. Mục đích thứ hai của lý thuyết SG là mô tả cách giành chiến thắng trong một trò chơi bao gồm nhiều vị trí được chơi cùng một lúc. Một nước đi trong một trò chơi kết hợp như vậy được thực hiện bằng cách thực hiện một bước di chuyển ở bất kỳ vị trí nào được kết hợp.
  
  Những gì người ta cần biết là giá trị SG của mỗi vị trí kết hợp. Để có được chúng, người ta cần biết giá trị SG sau mỗi lần di chuyển ở bất kỳ một trong những vị trí kết hợp này. Đây cũng là những điều cần thiết để chơi tối ưu.
  
  Ví dụ: Trong trò chơi Nim, người ta có một hoặc hai hoặc nhiều đống diêm. Nếu chúng ta biết giá trị SG để chơi từng cọc riêng lẻ, thì lý thuyết SG cho chúng ta biết cách chơi tối ưu với tất cả các cọc này bằng cách lấy đi số lượng trận đấu thích hợp từ bất kỳ cọc nào trong số này.
Điều đáng kinh ngạc về lý thuyết SG là các vị trí có thể được kết hợp với một trò chơi không chỉ là đống của trò chơi Nim mà là bất kỳ vị trí nào của bất kỳ trò chơi nào Trò chơi tổ hợp vô tư. Ví dụ: người ta có thể kết hợp một số vị trí chomp thành một trò chơi "siêu chomp" hoặc người ta có thể chơi một trò chơi tối ưu bắt đầu với 5 vị trí chomp khác nhau và 3 đống trận đấu và bất kỳ một trong 8 vị trí có thể được chơi bất cứ lúc nào.

iChomp là một phiên bản mới của Chomp được giới thiệu bởi Caribou Contests được chơi trên trang web này. Chữ 'i' trong iChomp là viết tắt của 'đẳng hướng', tức là tất cả các hướng đều được đối xử như nhau.

Trong Chomp bình thường, việc loại bỏ một viên gạch cũng loại bỏ tất cả các gạch ở phía Đông và Nam của nó. Vì vậy, các hướng Đông và Nam đóng một vai trò đặc biệt.

Trong iChomp, tất cả các ô theo các hướng khác cũng có thể được loại bỏ tùy thuộc vào vị trí gạch bị loại bỏ gần trung tâm nhất. Nếu gạch này, ví dụ, theo hướng Tây Bắc của trung tâm thì tất cả các gạch ở phía Bắc hoặc phía Tây cũng bị loại bỏ.

Loại bỏ các quy tắc nhân tạo, ví dụ, quy tắc Đông và Nam là đặc biệt thường được coi là làm cho một trò chơi đẹp hơn về mặt toán học.

Có một cách làm đẹp khác mà iChomp có so với Chomp.

Ở Chomp, gạch ở góc trên bên trái đóng một vai trò đặc biệt so với các loại gạch khác. Nếu đó là ô duy nhất trên bảng, trò chơi đã kết thúc. Nếu một ô khác bị xóa, trò chơi sẽ tiếp tục. Người ta có thể bắt đầu Chomp mà không có ô góc đó để tất cả các ô được xử lý như nhau, nhưng bản thân điều này sau đó sẽ là một quy tắc nhân tạo về lý do tại sao bắt đầu trò chơi mà không có ô đó và không phải không có các ô khác.

Trong iChomp, tất cả các ô đều có mặt khi bắt đầu và tất cả đều được xử lý như nhau. Bất kỳ ô nào cũng có thể được gỡ bỏ mà không tự động kết thúc trò chơi.

Một số câu hỏi phát sinh:

iChomp là một trò chơi tầm thường vì nó là sự kết hợp hay 4 trò chơi Chomp tầm thường trong 'Chơi bình thường'?
- Câu trả lời là không. Ví dụ, trò chơi Nim với một đống trận đấu duy nhất là tầm thường. Trong 'Chơi bình thường', người ta có thể loại bỏ toàn bộ đống trong một lần di chuyển và giành chiến thắng. Trong Nim dưới 'Misère Play', Người ta có thể loại bỏ tất cả trừ một trận đấu và giành chiến thắng. Tuy nhiên, sự kết hợp của các trò chơi Nim 1 cọc như vậy với một trò chơi Nim nhiều cọc như trên trang trò chơi Nim của chúng tôi là không tầm thường.
  
  Tương tự ở đây: Một trò chơi chomp duy nhất sử dụng ô góc và 'Chơi bình thường' là tầm thường vì người ta có thể loại bỏ tất cả các ô trong một lần di chuyển và giành chiến thắng. Nhưng sự kết hợp của 4 trò chơi như vậy là không tầm thường.
Tóm tắt so sánh
- IChomp đẹp hơn Chomp về mặt toán học vì nó không chỉ ra các hướng Đông Nam một cách giả tạo và không cho một ô một vai trò đặc biệt. Giá có vẻ như là iChomp khó chơi hơn nhiều so với Chomp nhưng SG-theory giúp đỡ. Chỉ cần biết giá trị SG của các vị trí Chomp lên đến một kích thước nào đó là đủ để dễ dàng tính toán giá trị SG của các vị trí iChomp lên đến 4 lần kích thước đó và do đó biết cách chơi iChomp tối ưu lên đến kích thước lớn hơn 4 lần đó.

Độc quyền Hoặc, hay viết tắt là XOR, là một hoạt động logic được thực hiện trên dữ liệu nhị phân. Sử dụng dữ liệu nhị phân, chúng ta có thể có một trong hai giá trị, true (=1) hoặc false (=0). Hoạt động XOR trên hai giá trị nhị phân được xác định thông qua bảng sau.

a b a XOR b
1 1 0
1 0 1
0 1 1
0 0 0

Mặc dù rất dễ sử dụng thao tác này trên các giá trị 1 (true) hoặc 0 (false), nhưng đối với các tính toán của chúng tôi, chúng tôi cần có khả năng thực hiện XOR trên hai số. Điều này cũng có thể được thực hiện, tuy nhiên cần có một bước mới trước khi chúng tôi có thể thực hiện XOR.

Điều đầu tiên phải xảy ra là các số sẽ cần phải được chuyển đổi thành nhị phân, tức là để chuyển đổi nó từ cơ số 10 sang cơ số 2.

Làm thế nào người ta có thể chuyển đổi một số từ cơ số 10 thành cơ số 2?
- Thuật toán sau đây có thể được sử dụng để chuyển đổi một số n trong cơ số 10 thành định dạng cơ số 2. (Được nhắc nhở rằng 2⁰ = 1):
  1. Tìm số mũ p cao nhất của 2, sao cho 2^p ≤ n.
  2. Ghi 1 và trừ 2^p từ n.
  3. Nếu p = 0 thì dừng lại, trừ 1 khỏi p và tiếp tục.
  4. Nếu 2 p > n thì ghi 0 trừ 2^p cho n và ghi 1.
  5. Quay lại bước 3.
  Chuỗi 1 và 0 bạn ghi lại theo thuật toán này sẽ là biểu diễn nhị phân của số n. Ví dụ:
  
  Hãy để chúng tôi chuyển đổi số 13 thành định dạng cơ sở 2. Chúng tôi bắt đầu bằng cách tìm lũy thừa cao nhất của 2 nhỏ hơn hoặc bằng 13, đó là 2,³ hoặc 8. Sau đó, chúng tôi ghi lại 1 và trừ 8 từ 13, cho chúng tôi 5. Tiếp theo ta kiểm tra 2⁽³⁻¹⁾ = 2² = 4. Vì 4 ≤ 5, chúng tôi ghi lại 1 và trừ 4 từ 5, cho chúng tôi 1. Công suất thấp hơn tiếp theo của 2 là 2:¹ = 2. 2 > 1, vì vậy chúng tôi ghi lại số 0. Lũy thừa tiếp theo của 2 là 2 0 = 1, bằng n của 1, vì vậy chúng ta ghi lại 1 và trừ 1 từ 1, cho chúng ta⁰. Vì p = 0, chúng tôi dừng thuật toán. Do đó, 13 (cơ số 10) = 1101 (cơ số 2).
  
  Sau khi chúng ta chuyển đổi hai số thành biểu diễn nhị phân, bây giờ chúng ta có thể thực hiện thao tác XOR trên các chữ số tương ứng của hai số nhị phân. Kết quả là một số nhị phân sau đó có thể được chuyển đổi trở lại thành cơ số 10 nếu điều đó thuận tiện hơn cho việc sử dụng giá trị XOR đó trong tương lai. Ví dụ:
  
  Chúng ta hãy tính XOR của các số 6 và 13. Biểu diễn nhị phân cho hai số này là 6 = 110 và 13 = 1101. Lúc đầu, chúng ta thêm 0 ở bên trái của số nhỏ hơn để cả hai đều có cùng số chữ số, vì vậy 6 = 0110. Sau đó, chúng ta có thể thực hiện XOR bằng cách xếp chúng lại và thực hiện thao tác trên từng chữ số riêng lẻ:
  
  0110
  XOR 1101
  ------
  1011
  
  Như vậy, 6 XOR 13 = 1011 (cơ số 2) = 1×2³+0×2²+1×2 1+1×2⁰ = 8+2+1 = 11 (cơ số¹⁰).
Hãy để chúng tôi kiểm tra sự hiểu biết của chúng tôi về XOR với một vài câu hỏi.

m XOR m cho bất kỳ số m nào là gì?
- Với bất kỳ số m nào, chúng ta có m XOR m = 0 vì 0 XOR 0 = 0 và 1 XOR 1 = 0.
N XOR m = m XOR n cho bất kỳ số nào n, m?
- Có, vì 1 XOR 0 = 0 XOR 1 (=1).
0 XOR m cho bất kỳ số m nào là gì?
- 0 XOR m = m vì 0 XOR 0 = 0 và 0 XOR 1 = 1.
Nếu một số m là XOR với một số n đến m XOR n thì những chữ số nào của m bị lật?
- Nếu một chữ số trong m là XOR'ed với 0 thì chữ số không thay đổi (vì 0 XOR 0 = 0 và 1 XOR 0 = 1). Nếu một chữ số trong m là XOR'ed với 1 thì chữ số được lật (vì 0 XOR 1 = 1 và 1 XOR 1 = 0). Do đó, XOR n lật tất cả các chữ số mà chữ số tương ứng trong n là 1.

a	b	a XOR b
1	1	0
1	0	1
0	1	1
0	0	0

Thuật toán sau đây tính giá trị SG của bất kỳ vị trí P nào trong bất kỳ trò chơi tổ hợp vô tư nào. Chúng tôi giải thích nó bằng cách sử dụng trò chơi Chomp.
- Mỗi vị thế trò chơi là vị trí thua sẽ nhận được giá trị SG 0. Trong Chomp, một ô duy nhất (ở góc Tây Bắc) là vị trí duy nhất không có động thái tiếp theo và do đó là vị trí thua với giá trị SG 0.
- Chúng ta cần các giá trị SG của tất cả các vị trí có thể đạt được từ vị trí P trong một lần di chuyển. Vì vậy, nếu vị trí P có n ô thì có thể có n-1 di chuyển: ngoại trừ ô ở góc Tây Bắc, tất cả các ô khác có thể được loại bỏ cùng với tất cả các ô ở Nam / Đông của ô đó.
- Giá trị SG của vị trí P là số không âm nhỏ nhất không có trong danh sách các giá trị SG có thể đạt được n-1 này.
Thuật toán này đệ quy vì để tính giá trị SG của vị trí P, chúng ta cần các giá trị SG của tất cả các vị trí có thể truy cập từ P trong một lần di chuyển. Nó vẫn hoạt động vì các giá trị SG cần thiết liên quan đến các vị trí nhỏ hơn của ít gạch hơn và giá trị SG của vị trí nhỏ nhất có thể (một ô ở góc Tây Bắc) được biết đến.

Hãy thử xác minh thuộc tính thứ 3 trong trò chơi ở trên bằng cách chọn chiều rộng và chiều cao bảng lớn hơn và nhấp vào 'Bảng ngẫu nhiên'.
- Khi bạn di chuyển chuột qua một ô, thì ô này và các ô khác sẽ bị xóa sẽ được tô sáng. Số trong ô đó là giá trị SG của góc phần tư trong 'Phát bình thường' (không phải 'Misère Play') sẽ dẫn đến nếu nhấp vào ô này. Bạn có thể kiểm tra xem số được hiển thị trong văn bản 'Giá trị SG Cơ số Mười:' bên cạnh góc phần tư có phải là số nhỏ nhất không được hiển thị trong góc phần tư hay không. Bạn cũng có thể kiểm tra xem nếu bạn nhấp vào một ô thì số trong đó bây giờ hiển thị là 'Giá trị SG Cơ số Mười:' của vị trí mới.
Cách tăng tốc độ xác định giá trị SG:

Bởi vì cùng một vị trí có thể đạt được từ các vị trí khác nhau trong một lần di chuyển và có thể xuất hiện nhiều lần khi tính giá trị SG của một vị trí lớn hơn, sẽ là một sự lãng phí nỗ lực để tính toán nó nhiều lần. Do đó, một khi giá trị SG của vị trí P được tính toán, nó nên được lưu trữ để sử dụng sau này.

Nếu một người muốn tính giá trị SG của tất cả các vị trí lên đến một số kích thước, thì cách tiếp cận sau đây rất hữu ích. Chúng ta bắt đầu bằng cách gán vị trí duy nhất với một ô (ở góc Tây Bắc) giá trị SG bằng không. Sau đó, chúng tôi sử dụng thuật toán trên để tính các giá trị SG của tất cả các vị trí với 2 ô, sau đó với 3 ô, v.v.

Một vị trí iChomp bao gồm 4 vị trí Chomp, một vị trí trong mỗi góc phần tư của bảng.
- Đầu tiên, chúng tôi xác định giá trị SG của mỗi một trong 4 vị trí Chomp bằng cách sử dụng quy tắc Chomp 'Misère Play'. Góc phần tư trống không phải là vị trí Chomp, vì vậy chúng ta cho nó giá trị −1.
- Sau đó, chúng tôi thêm 1 vào mỗi giá trị.
- Đối với mỗi một trong 4 số kết quả, chúng tôi tính toán biểu diễn nhị phân.
- Chúng tôi tính giá trị XOR của 4 giá trị nhị phân và thu được giá trị SG của vị trí đó (ở dạng nhị phân). Nếu giá trị này bằng không, đó là một vị trí thua lỗ, nếu không nó là một vị trí chiến thắng.

Tại sao chúng tôi thêm '1'?

Chúng tôi thêm 1 để có được giá trị SG của vị trí Chomp trong 'Chơi bình thường' từ giá trị SG trong 'Misère Play'. Định lý sau đây giải thích nó.

Định lí:
--------
Để có được giá trị SG của vị trí Chomp trong 'Chơi bình thường' (tức là lấy ô cuối cùng thắng trò chơi không phải là cách phổ biến để chơi Chomp), người ta cần thêm 1 vào giá trị SG của cùng một vị trí trong 'Misère Play' (tức là lấy ô cuối cùng thua, đó là cách phổ biến để chơi Chomp).

Bạn có thể thử chứng minh định lý bằng quy nạp không?
- Bằng chứng (bằng cảm ứng (và nhiều chi tiết)):
  
  Trường hợp cơ sở (1 gạch):
  -------------------
  Trong 'Chơi bình thường', một bảng trống không có ô là một vị trí thua lỗ và do đó có giá trị SG bằng không. Hơn nữa, trong 'Chơi bình thường' cho bảng có một ô (ở góc trên bên trái), động thái duy nhất có thể là loại bỏ ô này mang lại vị trí có giá trị SG 0. Vì vậy, trong 'Chơi bình thường', giá trị SG không âm nhỏ nhất không thể đạt được bằng cách di chuyển là 1, do đó, đó là giá trị SG của một vị trí có một ô trong 'Chơi bình thường'.
  
  Trong 'Misère Play', có một ô là vị trí thua với giá trị SG 0.
  
  Do đó, đối với 1 ô, giá trị SG 'Chơi bình thường' lớn hơn 1 so với giá trị 'Misère Play'.
  
  Bước quy nạp
  ---------------
  
  Giả thuyết cảm ứng (n gạch):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Chúng tôi giả định rằng tồn tại một số n sao cho đối với tất cả các vị trí có ô ≥1 và ≤n, giá trị SG trong 'Chơi bình thường' lớn hơn giá trị trong 'Misère Play'. Yêu cầu cảm ứng (n + 1 ô):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Chúng tôi sẽ chỉ ra rằng đây cũng là trường hợp cho tất cả các vị trí có ô n + 1.
  
  Bước cảm ứng (n gạch → n+1 gạch):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  Đối với bất kỳ vị trí nào, 'Misère Play' và 'Normal Play' cho phép di chuyển giống nhau ngoại trừ 'Chơi bình thường' cũng cho phép lấy tất cả các ô qua ô góc trên bên trái.
  
  Nếu vị trí có n+1 ô, thì việc di chuyển sẽ tạo ra một vị trí có nhiều nhất n ô mà chúng ta có thể áp dụng giả thuyết quy nạp:
  
  Do đó, danh sách các giá trị SG có thể đạt được trong 'Chơi bình thường' được lấy từ danh sách các giá trị SG có thể đạt được trong 'Misère Play' mỗi giá trị tăng thêm 1 và bằng cách thêm giá trị 0 thông qua việc lấy tất cả các ô.
  
  Do đó, số không âm nhỏ nhất KHÔNG thể đạt được trong 'Chơi bình thường' cao hơn 1 số không âm nhỏ nhất KHÔNG thể đạt được trong 'Misère Play'. Nói cách khác, đối với vị trí ban đầu có ô n + 1, giá trị SG trong 'Chơi bình thường' cao hơn giá trị SG trong 'Misère Play'. ∎ (Điều này hoàn thành bằng chứng.)

Mục đích là để thực hiện một động thái sao cho giá trị SG của vị trí kết quả bằng không. Bất cứ động thái nào một người thực hiện, nó phải ở một trong 4 góc phần tư. Điều đó có nghĩa là giá trị SG của vị trí nơi di chuyển đã được thực hiện và giá trị SG của 3 góc phần tư không thay đổi khác mà tất cả XOR đều phải cho 0. Đây là trường hợp nếu và chỉ khi 3 giá trị SG khác XOR cung cấp chính xác giá trị SG của góc phần tư mới sau khi thực hiện di chuyển (xem thêm bên dưới để chứng minh cho tuyên bố này). Do đó, thủ tục như sau:
- (đơn giản) Trường hợp: Hai trong số 4 góc phần tư có cùng giá trị SG. Sau đó, XOR của hai giá trị bằng nhau này sẽ cho 0, vì vậy cả hai góc phần tư sẽ bị bỏ qua.
- (tổng hợp) Trường hợp:
Tại sao đó là một động thái chiến thắng?
- Vui lòng nhắc nhở bản thân về các thuộc tính của XOR như được hiển thị trước đó để trả lời các câu hỏi sau.
  
  nếu bạn = w XOR x XOR y XOR z, thì y XOR u là gì?
  - Bằng cách sử dụng các quy tắc XOR đã học trước đó, chúng tôi nhận được
       y XOR u
    = y XOR w XOR x XOR y XOR z
    = y XOR y XOR w XOR x XOR z
    =        0     XOR w XOR x XOR z
    =            w XOR x XOR z.
  Nếu y được thay thế bằng y XOR u thì XOR mới của cả 4 giá trị SG là gì?
  - XOR mới sẽ là
    (y XOR u) XOR w XOR x XOR z
    = (w XOR x XOR z) XOR (w XOR x XOR z)
    = 0
    vì m XOR m = 0 cho bất kỳ số m nào.
    
    Điều đó có nghĩa là giá trị SG mới của toàn bộ hội đồng quản trị sẽ bằng không, vì vậy đó sẽ là một vị trí thua lỗ như dự định.
  Tại sao phải có một động thái làm thay đổi giá trị SG y thành giá trị thấp hơn?
  - Theo định nghĩa: Một vị trí có giá trị SG là y nếu và chỉ khi tồn tại các di chuyển tạo ra các vị trí có giá trị SG 0,1,..,(y-1). Vì vậy, nếu y > (y XOR u), thì phải tồn tại một di chuyển tạo ra giá trị SG (y XOR u) < y.
  Điều còn lại cần được trả lời là:
  
  Tại sao phải tồn tại một góc phần tư với giá trị SG y thỏa mãn y > (y XOR u)?
  - Một lời nhắc nhở:
    Trước đó, khi chúng ta tìm hiểu về các thuộc tính của XOR, chúng ta đã thấy: XOR u lật tất cả các chữ số mà chữ số tương ứng trong u là 1.
    
    Nếu bạn ≠ 0, thì u chứa lũy thừa cao nhất là 2, giả sử 2^p. Lũy thừa 2 này phải xảy ra trong một số lẻ của 4 giá trị SG, vì vậy trong ít nhất một, giả sử y.
    
    Điều này có nghĩa là, khi tính y XOR u, 1 trong y này được lật thành 0 bởi 1 trong u tương ứng. Có thể có các chữ số nhị phân khác được lật trong y nằm ở bên phải của 1 này. Giá trị lớn nhất có thể có của y − (y XOR u) xảy ra nếu các chữ số trong y ở bên phải của 1 này là số không và các chữ số trong u ở bên phải của 1 đó là các chữ số. Trong trường hợp đó, u = 111..111 thay đổi y = *100..00 (trong đó * là viết tắt của bất kỳ số chữ số nào) thành y XOR u = *011..11. Sự khác biệt của họ là:
    
    y − (y XOR u)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)× (2-1)/(2-1)
    = 2^p − (2^p−1)/(2-1)
    = 1.
    Điều đó có nghĩa là y lớn hơn ít nhất một (y XOR u). ∎
Hãy thử thuật toán này bằng cách chơi và chiến thắng 'Khó khăn: Khó'.
- Để bắt đầu, hãy chọn 'Độ khó: Khó' đảm bảo chơi trên máy tính tối ưu. Nếu bạn vẫn giành chiến thắng thì bạn đã chơi từng nước đi một cách tối ưu.
  
  Giá trị SG của mỗi góc phần tư được thể hiện trong cơ số 10 và cơ số 2. Kiểm tra xem số này có phải là giá trị nhỏ nhất không được hiển thị trong góc phần tư hay không.
  
  Bên dưới, XOR của cả 4 giá trị SG được gọi là u được hiển thị. Xác minh giá trị của bạn bằng cách chỉ cần thay đổi bất kỳ cặp nào của hai 1 trong 4 giá trị SG thành 0 nếu hai số 1 ở cùng một vị trí. Sau đó đặt 1 số còn lại vào một số nhị phân và chuyển đổi nó thành cơ số 10.
  
  Để thực hiện một động thái tiến hành như mô tả ở trên:
  - Tìm một trong 4 giá trị SG, giả sử y, có 1 ở cùng vị trí với 1 ngoài cùng bên trái trong u.
  - Tính y XOR u ở dạng nhị phân và sau đó chuyển đổi nó thành cơ số 10.
  - Trong góc phần tư y, bấm vào ô xếp có y XOR u được tính toán.
  - Chơi di chuyển của bạn theo cách này cho đến khi bạn giành chiến thắng.
  - Chơi lại nhưng lần này bắt đầu với một bước di chuyển ngẫu nhiên. Trừ khi bạn may mắn và chơi một cách tình cờ một nước đi chiến thắng, bạn sẽ không thể giành chiến thắng trong trò chơi này ngay cả khi sau đó bạn cố gắng chơi tối ưu.

Để tính giá trị SG của một vị trí, người ta cần biết giá trị SG của tất cả các vị trí có thể đạt được từ nó trong một lần di chuyển. Đây là một quá trình đệ quy. Do đó, chúng ta cần bắt đầu với các vị trí có số lượng gạch ít nhất và làm việc theo cách của chúng ta.

Bạn có thể tìm thấy các giá trị SG của 1,2,3 không,... Gạch trong một hàng?
- Chỉ có 1 ô (ở góc trên bên trái) là vị trí thua với giá trị SG 0.
  
  Có 2 ô (ở hàng trên cùng hoặc cột bên trái), bước di chuyển duy nhất có thể là lấy một ô có được vị trí được đề cập với giá trị SG 0. Vì vậy, giá trị SG không âm nhỏ nhất không thể đạt được bằng cách di chuyển là 1, do đó, đó là giá trị SG của một vị trí có 2 ô là 1.
  
  Có 3 ô tất cả ở hàng trên cùng, người ta có thể lấy 1 hoặc 2 ô và thu được giá trị SG 1 và 0, do đó, giá trị SG là 2.
  
  Tương tự, giá trị SG của n ô ở hàng trên cùng là n-1.
  
  Chúng ta hãy xem xét 3 ô, 2 ở hàng trên cùng và 2 ở cột bên trái. Chúng ta chỉ có thể loại bỏ 1 ô và đạt giá trị SG là 1 chứ không phải 0, vì vậy giá trị SG nhỏ nhất không thể lấy được là 0, do đó là giá trị SG của vị trí này. Đây là một vị trí thua cuộc.
Bạn có thể tìm thấy giá trị SG của một vị trí với m + n − 1 ô trong đó n nằm ở hàng trên cùng và m ô ở cột bên trái không?
- Người ta chỉ có thể xóa các ô từ hàng trên cùng hoặc từ cột bên trái. Do đó, giá trị SG giống như có hai góc phần tư, một với n ô ở hàng trên cùng và một với m ô ở cột bên trái. Do đó, giá trị SG là (m-1) XOR (n-1). Điều này cũng giống như chơi NIM với hai cọc và quy tắc 'Chơi bình thường', nơi các trận đấu có thể được xóa khỏi chỉ một cọc trong một lần di chuyển.
Bạn có thể tìm thấy giá trị SG của một vị trí chỉ có các ô ở hai hàng trên cùng không?
- Các công thức cho các vị trí này phức tạp hơn. Theo như chúng tôi biết, chúng chưa được xuất bản trước đây. Bạn có thể thử xác minh chúng cho một số lượng nhỏ ô.
  
  Cho n và m là số ô ở hàng trên cùng và hàng thứ hai.
  
  Nếu n là chẵn
    k = (n-2)/2
    Nếu m là chẵn sau đó
      a = m/2
      Giá trị SG = 2*k+a+1
    else (m là lẻ)
      a = (m-1)/2
      nếu ≤ (k/2) thì giá trị SG = 2*k-a
      giá trị SG khác = 3*(k-a)
  else (n là lẻ)
    k = (n-1)/2
    Nếu m là chẵn sau đó
      a = m/2
      nếu ≤ (k/2) thì giá trị SG = 2*k-a
      giá trị SG khác = 3*(k-a)
    else (m là lẻ)
      a = (m-1)/2
      Giá trị SG = 2*k+a+1
  
  Kiểm tra xem các công thức có đúng không bằng cách sử dụng bảng trò chơi ở trên.
  - Chọn chiều cao bảng tối thiểu sao cho có các góc phần tư chỉ có hai hàng gạch. Sau khi áp dụng các công thức trên, bạn sẽ nhận được giá trị SG thấp hơn một giá trị được hiển thị trong 'SG Value Base Ten:' vì các công thức dành cho 'Misère Play' trong khi iChomp sử dụng 'Chơi bình thường'.

Chúng tôi bắt đầu với một quan sát: Các quy tắc của Chomp không có sự khác biệt giữa hướng Đông và Nam.

Hệ quả đối với các giá trị SG của hai vị trí đối xứng với nhau khi phản chiếu trên đường chéo bắt đầu từ góc trên cùng bên trái là gì?
- Bởi vì hướng Đông và Nam được nhân đôi với nhau, điều này có nghĩa là cả hai phải có cùng giá trị SG.
Điều đó có ý nghĩa gì đối với iChomp khi 2 góc phần tư có vị trí đối xứng dưới sự quay của góc phần tư và / hoặc phản chiếu chéo?
- Cả hai góc phần tư có thể được bỏ qua. Tại sao? Cả hai góc phần tư đều có cùng giá trị SG khi chơi misère và sau khi thêm 1 cũng có cùng giá trị SG khi chơi bình thường. XOR của hai giá trị bằng nhau này cho số không. Do đó, cả hai góc phần tư đều không đóng góp vào giá trị SG của toàn bộ vị trí hội đồng quản trị.
Do đó, chiến lược chơi nào nên hiệu quả?
- Người ta nên thực hiện một động thái tạo ra hai cặp góc phần tư sao cho các góc phần tư trong mỗi cặp có vị trí đối xứng với các giá trị SG bằng nhau, giả sử A và A, và B và B. Sau đó, giá trị SG của tổ hợp của cả 4 góc phần tư là A XOR A XOR B XOR B = 0 XOR 0 = 0 hoặc (A XOR B) XOR (A XOR B) = 0 vì vậy luôn luôn là 0. Một người tạo ra một vị trí thua cuộc.
  
  Tương tự, người ta KHÔNG nên thực hiện một động tác để lại hai góc phần tư đối xứng và hai người khác trong đó một người có thể được thay đổi thành người kia trong một nước đi của đối thủ. Điều này sẽ cho phép đối thủ tạo ra một vị trí thua cuộc.

Dưới đây là một số câu hỏi mà bạn có thể kiểm tra sự hiểu biết của mình về Chomp, iChomp và lý thuyết SG.

Kiến thức về giá trị SG có đủ để chơi Chomp một cách hoàn hảo?
- Có. Nếu giá trị SG của một vị trí bằng không, thì đó là một vị trí thua lỗ (vì không có động thái nào tồn tại để làm cho nó bằng không, vì vậy không có nước đi chiến thắng nào tồn tại, vì vậy nó là một vị trí thua lỗ). Nếu giá trị SG lớn hơn 0, thì điều này có nghĩa là có một động thái để làm cho giá trị SG của vị trí kết quả bằng không, do đó có một động thái chiến thắng.
Người ta có cần biết giá trị SG của các vị trí Chomp để chơi Chomp một cách hoàn hảo không?
- Không. Để chơi Chomp, chúng ta cần tìm một nước đi tạo ra vị thế thua cuộc. Nếu không có động thái như vậy tồn tại thì đó là một vị trí thua cuộc và bất kỳ nước đi nào cũng có thể được chơi. Nhưng, nếu một động thái như vậy được tìm thấy, người ta có thể ngừng tìm kiếm. Giá trị SG là không cần thiết.
Vậy thì giá trị SG tốt cho điều gì?
- Họ chỉ cần chơi một số trò chơi Chomp song song như một trò chơi mới, như trong iChomp.
Chomp khó tính giá trị SG của một vị thế hơn là một nước đi chiến thắng khó khăn hơn bao nhiêu?
- Để chơi Chomp, chúng ta cần tìm một nước đi tạo ra vị thế thua cuộc. Nếu không có động thái như vậy tồn tại thì đó là một vị trí thua cuộc và bất kỳ nước đi nào cũng có thể được chơi. Nhưng, nếu một động thái như vậy được tìm thấy, người ta có thể ngừng tìm kiếm.
  
  Nỗ lực tìm giá trị SG của một vị trí thường cao hơn. Để tìm giá trị SG, người ta luôn phải tìm kiếm TẤT CẢ các bước di chuyển để tìm tất cả các giá trị SG của các vị trí kết quả và tìm giá trị không âm nhỏ nhất không thể đạt được trong một lần di chuyển. Giá trị này là giá trị SG của vị thế.
  
  Ví dụ: trong tính toán (Caribou) của chúng tôi, chúng tôi có thể xác định tất cả các vị trí thua lỗ (và do đó giành được vị trí) với tối đa 93 ô. Với nỗ lực tính toán tương đương, chúng tôi đã có thể tính toán giá trị SG của tất cả các vị trí Chomp với tối đa 82 ô.
  
  Theo nghĩa này, việc xác định giá trị SG đắt hơn về mặt tính toán so với việc xác định một nước đi chiến thắng.
Nếu Nim với 4 cọc khó chơi hơn NIM với 1 cọc, thì iChomp với 4 góc phần tư có khó chơi hơn nhiều so với Chomp với 1 góc phần tư không?
- Trong Nim, giá trị SG của một cọc chỉ đơn giản là số trận đấu trong đống đó. (Vui lòng xác nhận điều này bằng cách áp dụng các nhận xét ở trên cách tính giá trị SG cho một ngăn xếp duy nhất trong Nim.) Sự phức tạp duy nhất của việc chơi nhiều cọc trong Nim là XOR các giá trị SG khác nhau của các cọc này để có được giá trị SG của tất cả các cọc kết hợp.
  
  Trong Chomp, rất tốn kém về mặt tính toán để có được giá trị SG của một vị trí (nằm trong một góc phần tư). Trong iChomp, một khi các giá trị SG của 4 góc phần tư được biết, các giá trị này cũng cần phải được XOR, nhưng điều đó dễ dàng hơn nhiều so với việc tìm giá trị SG của một góc phần tư.
  
  Để chơi Chomp một cách tối ưu, người ta không cần biết giá trị SG của vị trí, biết một nước đi chiến thắng là đủ tốt, nhưng như được hiển thị ở trên sự khác biệt không phải là quá lớn.
  
  Vì vậy, câu trả lời là KHÔNG, không khó để chơi iChomp tối ưu hơn Chomp.
Trong Chomp, một nước đi có thể tạo ra một vị thế có giá trị SG cao hơn không?
- Có. Giá trị SG của một vị thế là giá trị nhỏ nhất không thể được tạo ra bởi một động thái.
Trong Chomp, có thể có những động thái khác nhau tạo ra vị trí có cùng giá trị SG không?
- Có. Bạn có thể xem các ví dụ bằng cách tăng kích thước bảng và nhấp vào nút 'Hiển thị giá trị SG của Di chuyển'. Ví dụ, vị trí
  
  ###
  ##
  #
  
  có 3 nước đi chiến thắng, tất cả đều tạo ra một vị thế với giá trị SG là 0. Chúng tôi thậm chí còn tìm thấy một vị trí với 7 nước đi chiến thắng:
```
 + 10  6 15  2 20 21 14 22 11  0 23  7 26
13  7 11  9 14  0 19  5
17 11 14 18  0 24 23  8
 3 19  2  0 20
11  4  0  5  1
 8  0
 0
 4
23
25
24
```