Chomp ©

Một khoảng rộng là điểm giao của hàng ngang và cột dọc, được dán nhãn là (row, col).
Một ô gạch là hình ảnh ở một số khoảng rộng.
Một thế cờ bao gồm tất cả những khoảng rộng với ô gạch.

Hãy bắt đầu với những vấn đề dễ, tức là những thế cờ nhỏ. Để tạo ra những thế cờ này, chúng ta nhấp vào 'Máy tính: Tắt': Nếu sau đó chúng ta nhấp vào (2,1) thì chỉ còn một hàng gạch còn lại.

Người chơi tiếp theo, tức là đối thủ của bạn có thể làm gì?
- Bằng cách nhấp vào (1,2), chỉ có ô gạch ở (1,1) còn lại, nên bạn đã thua.

Chúng ta hãy nhấp vào 'Trò chơi mới' và nhấp vào (3,1) và (2,2) để có một ô gạch ở hàng 2 và toàn bộ hàng 1.

Người chơi tiếp theo có thể làm gì?
- Bằng cách nhấp vào (1,3) chỉ còn lại ba ô gạch. Bạn có thể thấy rằng mình không còn cơ hội thắng không?

Hãy nhấp vào 'Trò chơi mới' và nhấp vào (3,1) và (2,3)

Người chơi tiếp theo có thể làm gì?
- Đối phương của bạn nhấp vào (1,4). Bạn có thể thấy rằng mình không còn cơ hội thắng không?

Bạn có thể tóm tắt lại xem thế nào có những ô gạch ở 2 hàng ngang, thì bạn không có cơ hội nào để thắng trò chơi không?
- Nếu hàng ngang trên cùng có nhiều hơn hàng ngang thứ 2 một ô gạch, thì cho dù bạn có làm gì, đối thủ của bạn luôn luôn có thể thực hiện một bước đi để hàng ngang trên cùng có nhiều hơn một ô gạch so với hàng ngang thứ 2. Sau đó, dù bạn có làm gì, cuối cùng thì bạn sẽ cần phải chọn ô (1,1) và thua trò chơi.

Nếu một ô gạch đã được nhấp vào, tất cả các ô gạch ở dưới và về phía bên phải đều bị xoá. Quy tắc này có một tính đối xứng; tức là cả trò chơi có tính đối xứng sau: Nếu chúng ta hoán đổi hàng ngang với cột dọc thì các quy tắc được giữ nguyên: tất cả các ô gạch ở phía bên phải trở thành tất cả các ô gạch phía dưới và tất cả các ô gạch phía bên phía dưới trở thành tất cả các ô gạch nằm phía bên phải của ô gạch bị xoá. Nói một cách khác, nếu ta phản chiếu một thế dọc theo đường thẳng đi xuyên qua (1,1) và (2,2) thì thế mới trông khác, nhưng nó vẫn có trạng thái y nguyên. Nước đi chiến thắng cũng sẽ vẫn là nước đi như vậy, chỉ là nó cũng bị phản chiếu.

Như ta đã biết, thế cờ với 3 ô gạch ở hàng đầu và 2 ô gạch ở hàng 2 là không có hi vọng (vô vọng). Những thế cờ bị phản chiếu có những ô gạch nào?
- Sau khi phản chiếu, nó có 3 ô gạch ở cột bên trái và 2 ô gạch ở cột thứ 2.

Chúng ta biết được tất cả các thế cờ vô vọng có các ô gạch ở hai hàng ngang đầu tiên. Tính đối xứng nói cho chúng ta điều gì về tất cả những thế cờ vô vọng với những ô gạch chỉ ở hai cột dọc đầu tiên?
- Những thế cờ vô vọng với những ô gạch ở hai cột dọc đầu tiên là những thế cờ mà cột dọc đầu có nhiều hơn cột dọc hai một ô gạch.

Đây là một thế cờ khác mà không có cơ hội nào: Nhấp vào 'Trò chơi mới' và vào (4,1), (2,2) và (1,4).

Nếu đối phương thực hiện một nước đi ở thế cờ này, bạn sẽ đáp trả như nào?
- Bạn cần phải chắc chắn rằng sau khi bạn di chuyển thì hàng ngang và cột dọc đầu tiên lại một lần nữa có cùng một độ dài. Bằng cách lặp lại kiểu mẫu này, đối phương cuối cùng sẽ phải chọn ô (1,1) và thua.

Do đó, nếu hàng ngang đầu tiên và cột dọc đầu diên có cùng số ô gạch và không có ô gạch nào khác thì thế cờ này là vô vọng. Thế cờ nào có thể được biến thành một thế cờ như vậy?
- Nếu một thế cờ có cùng số lượng hàng ngang và hàng dọc, bất kể có bao nhiêu ô ở bất kỳ nơi nào khác: một nước đi ở (2,2) chỉ để lại hàng đầu tiên và cột đầu tiên có độ dài bằng nhau, khiến đối thủ không còn cơ hội nào. Vì vậy, nếu một thế cờ có cùng số ô gạch ở hàng ngang trên cùng với số ô gạch ở cột bên trái thì sau đó bạn có thể chơi ở (2,2) và thắng trò chơi.

Để chơi được Chomp giỏi, một người cần biết về các thế cờ thắng và thế cờ thua. Một thế cờ thắng là một thế cờ mà một người có thể giành được chiến thắng nếu họ chơi một cách tối ưu, bất kể bên kia có làm gì đi nữa. Một thế cờ thua là một thế cờ mà một người không có cơ hội nào để thắng nếu đối phương chơi một cách tối ưu. Những điểm sau đây được gọi trong toán học là một định lý. Trong Chomp, các thế cờ thua và thắng được xác định thông qua 3 điểm sau:
1. Nếu chỉ còn lại duy nhất một ô gạch (ở góc trên cùng bên trái), thì đây là một thế cờ thua.
2. Một thế cờ là một thế cờ thắng nếu tồn tại một nước đi dẫn tới một thế cờ thua cho đối thủ.
3. Một thế cờ là thế cờ thua nếu tất cả nước đi dẫn đến một thế cờ thắng cho đối phương.
Thoạt nhìn ban đầu, những điểm phía trên trông có vẻ vô dụng vì các thế cờ thắng được giải thích bởi những thế cờ thua, và những thế cờ thua được giải thích bởi các thế cờ thắng. Tuy nhiên, định nghĩa được dựa trên việc thực hiện các nước đi, và mọi chuỗi di chuyển cuối cùng đều dẫn đến một thế cờ có 1 ô gạch duy nhất mà theo điểm 1 là một thế cờ thua.

Có thể có những thế cờ mà cả hai bên đều không thể giành được chiến thắng hay không? (khó)
- Ta sẽ xây dựng một định lý nhỏ và chứng minh nó. Bằng chứng sẽ cho chúng ta thấy cách đạt được sức mạnh chơi trò chơi hoàn hảo. Bằng chứng là một minh chứng bằng phép quy nạp mà trong đó chỉ ra rằng mệnh để mà ta muốn chứng minh là đúng với một ô gạch và sau đó cho thấy rằng nếu nó đúng với bất kỳ số N ô gạch bất kỳ nào, thì nó cũng phải đúng với một ô gạch nữa, tức là N+1 ô gạch. Vì mệnh đề này là đúng với N=1 ô gạch, nó cũng phải đúng với N+1=1+1=2 ô gạch. Nhưng vì nó đúng với N=2, thì nó cũng phải đúng với N+1=2+1=3 ô gạch, và v.v; tức là đối với bất kỳ số lượng ô gạch nào.
- Bổ đề (định lý nhỏ): Mỗi thế cờ đều là thế cờ thắng hoặc thế cờ thua.
- Minh chứng bằng phép quy nạp:
- Cơ sở quy nạp: Nếu thế cờ đó chỉ có một ô gạch thì ô gạch này nằm ở góc trên cùng bên trái và khi đó thế cờ đó là thế cờ thua dựa theo quy tắc của Chomp (cho thấy rằng bổ đề là đúng nếu chỉ có N=1 ô gạch).
- Giả thuyết quy nạp: Chúng ta giả sử rằng bổ đề là đúng với tất cả các thế cờ có tối đa N ô gạch, tức là các thế cờ với 1,2,..., N ô gạch là các thế cờ thắng hoặc thua.
- Bước quy nạp: Bây giờ chúng ta muốn chứng minh rằng tất cả các thế cờ với N+1 ô gạch phải là thế cờ thắng hoặc thua.
- Trong phần sau đây, P là một thế cờ tuỳ ý với N+1 ô gạch. Nếu P được giảm đi một nước đi thì thế cờ mới phải có ≤ ô gạch, do đó nó là thế cờ thua hoặc thắng theo giả thuyết quy nạp. Nếu P có thể giảm một nước đi đến thế cờ thua thì P sẽ là một thế cờ thắng. Nếu không thì P chỉ có thể được giảm một nước đi về một thế cờ thắng. Nhưng nếu một thế cờ có thể được giảm chỉ trong một nước đi về thế cờ chiến thắng thì P phải là thế cờ thua. Điều này chứng minh rằng P (có N+1 ô gạch) là một trong hai: thế cờ thắng hoặc thế cờ thua. Điều này chứng minh rằng tất cả các thế cờ (với N+2, N+3,...ô gạch) là thế cờ thắng hoặc là thế cờ thua.
  
  Kết thúc chứng minh ∎
- Nhận xét bổ sung: Bước quy nạp cung cấp một phương pháp để quyết định cho tất cả các thế cờ (đến một kích thước nhất định) dù chúng ở thế cờ thắng hay thế cờ thua. Nó được định nghĩa như sau:
  
  Ta bắt đầu với N=1 và gắn nhãn cho thế cờ đó là thế cờ thua. Sau đó ta xác định trạng thái của tất cả các thế cờ với 2 ô gạch, sau đó với 3 ô gạch, v.v, mỗi lần sử dụng kiến thức về trặng thái của các thế cờ nhỏ hơn, và thêm những thế cờ thua mới được tìm thấy vào danh sách các thế cờ thua đã biết.
- Đây là một cách rất hiệu quả để tìm tất cả các thế cờ thắng và thế cờ thua lớn đến một kích thước nhất định. Khi các con số trở nên lớn hơn về kích cỡ, một chương trình máy tính sẽ rất hữu ích. Những thành phần cần thiết như sau:
  - Một quy trình có thể tạo ra tất cả các thế cờ của N ô gạch một cách hiệu quả từ việc biết được tất cả thế cờ có ít hơn N ô gạch.
  - Một quy trình có thể kiểm tra một cách hiệu quả xem liệu một thế cờ có thể được giảm xuống một thế cờ đã cho khác không.
  Chúng tôi sẽ để bạn nghĩ thêm về vấn đề này và có thể viết một chương trình máy tính như vậy.

Có bao nhiêu thế cờ thua và thế cờ thắng có chính xác 2 ô gạch?
- Chỉ có hai thế cờ có thể có mà có chính xác 2 ô gạch, 2 ô gạch ở hàng ngang trên cùng, hoặc hai ô gạch dọc theo cột dọc bên trái. Cả hai thế cờ này đều là thế cờ thắng.

Có bao nhiêu thế cờ thua và thế cờ thắng có chính xác 3 ô gạch?
- Có tổng cộng 3 thế cờ có thể có mà có chính xác 3 ô gạch. Chúng bao gồm 2 thế cờ thắng, và 1 thế cờ thua. Bạn có thể xác định được đó là những thế cờ nào không?

Có bao nhiêu thế cờ thua và thế cờ thắng có chính xác 4 ô gạch?
- Có 5 thế cờ có thể có mà có chính xác 4 ô gạch. Tất cả những thế cờ này đều là thế cờ thắng.

Có bao nhiêu thế cờ thua và thế cờ thắng có chính xác 5 ô gạch?
- Có tất cả 7 thế cờ có thể có mà có chính xác 5 ô gạch. Từ những thế cờ này, 3 thế cờ trong số đó là thế cờ thua và có 4 thế cờ thắng. Bạn có thể xác định được chúng là những cái nào không?

Các thế cờ hình chữ nhật là thế cờ thắng hay thế cờ thua?
- Bổ đề sau đây trả lời cho câu hỏi này. Bằng chứng này là một chứng minh tồn tại. Nó sẽ chỉ chứng minh sự tồn tại của một nước đi chiến thắng mà không cần chỉ ra nước đi đó là gì. Tuy nhiên, việc biết được bổ đề sẽ hữu ích cho cách chơi của bạn như được giải thích ở phía bên dưới.
- Bổ đề: Tất cả những thế cờ hình chữ nhật ngoại trừ thế cờ 1 ô gạch đều là thế cờ chiến thắng.
- Minh chứng: Để chứng minh điều này là đúng chúng ta cần xem xét hai trường hợp có thể xảy ra:
  1. Loại bỏ ô gạch ở góc dưới bên phải của bàn chơi là một nước đi chiến thắng.
  2. Loại bỏ ô gạch ở góc dưới bên phải không phải là nước đi chiến thắng.
- Nếu trường hợp 1 là đúng, thì nó có nghĩa là hình chữ nhật là thế cờ chiến thắng, và điều này hỗ trợ bổ đề.
- Nếu trường hợp 1 là sai, thì chúng ta cần xem xét trường hợp 2. Dựa theo bằng chứng ta đã chứng minh trước đó, thề cờ là kết quả của việc loại bỏ ô gạch nằm ở góc dưới bên phải là thế cờ chiến thắng, có nghĩa là nó phải tồn tại một nước di chuyển chiến thắng. Tuy nhiên, vì mỗi nước đi trong một hình chữ nhật sẽ loại bỏ ô gạch ở góc dưới bên phải, thế cờ thua là kết quả của nước đi thứ 2 (nước đi chiến thắng) sẽ y nguyên dù nước đi chiến thắng có được thực hiện sau nước đi ở góc hay nước đi đó sẽ thay thế nước đi ở góc. Điều này có nghĩa là nước đi thắng có thể đã được thực hiện ngay lập tức, do đó chứng minh rằng nước đi chiến thắng đã tồn tại cho thế cờ hình chữ nhật.
- Kết thúc chứng minh ∎
- Nhận xét bổ sung: Mặc dù bổ đề không cho chúng ta biết được nước đi chiến thắng là gì, nó đã rất hữu ích khi cho ta biết được các thế cờ hình chữ nhật là các thế cờ chiến thắng. Do đó, ta không nên thực hiện một nước đi tạo ra thế cờ hình chữ nhật (ngoại trừ thế cờ 1x1).

Bạn có thể xác định nước đi chiến thắng cho bất kỳ bàn chơi vuông nào không?
- Đối với tất cả các ô vuông với kích thước >1, nước đi chiến thắng duy nhất là (2,2).

Đối với thế cờ giống như một hình vuông nào thì một nước đi tương tự là nước đi chiến thắng?
- Nước đi (2,2) cũng là nước đi chiến thắng đối với bất kỳ thế cờ nào mà hàng ngang thứ nhất và cột dọc thứ nhất có cùng một độ dài.

Một thế cờ có thể có nhiều hơn một nước đi chiến thắng hay không?
- Có, một thế cờ có thể có nhiều hơn một nước đi chiến thắng. Hãy xem xét những thế cờ sau:
  
  ###
  ##
  #
  
  Thế cờ trong bàn chơi này có 3 bước đi chiến thắng khác nhau có thể được thực hiện. Bạn có thể xác định chúng là gì không?

Chiến lược chung để thắng Chomp là tạo ra một thua cho đối phương của bạn để họ không có cơ hội chiến thắng. Chúng ta cũng muốn tránh tạo ra các thế cpwf chiến thắng mà đối thủ có thể biến thành thế cờ thua cho chúng ta.

Chìa khoá để chiến thắng là biết càng nhiều thế cờ thua càng tốt, và phát hiện cách tạo ra một thế cờ trước đối thủ của bạn. Hãy xem xét bàn chơi có thể xảy ra sau đây, đây là một thế cờ thua mà ta đã biết:

#######
###
###
#
#
Hình 1

Đâu là tất cả các thế cờ có thể biến thành thế cờ thua trong một nước đi?

Thế cờ thua ở trên có thể là kết quả của bất kỳ nước đi nào được đánh dấu + ở dưới:

#######+
###
###
#
#

#######
###+
###
#
#

#######
###
###
#+
#

#######
###
###
#
#
+

Hình 2

Những nước đi này đều nằm ở thế cờ góc đã bị cắt. Những nước đi được đánh dấu + như vậy cũng sẽ cắt bỏ những ô gạch có thể xuất hiện ở trong hình ảnh bên dưới với dấu ?:

#######+?
###
###
#
#

#######
###+???
###????
#
#

#######
###
###
#+?
#??

#######
###
###
#
#
+
?

Hình 3

Những ô gạch có dấu + là cần thiết, và những ô gạch có dấu ? là tuỳ chọn. Ở thế cờ thắng cuộc ở bên trái, hàng ngang trên cùng có thể được mở rộng tuỳ ý sang bên phải với nhiều dấu '?' hơn, và ở thế cờ thắng cuộc bên phải, cột dọc đầu tiên có thể được mở rộng tuỳ ỳ về phía dưới với nhiều dấu '?' hơn. Tất cả những thế cờ này đều là thế cờ thắng cuộc. Nếu chúng ta thực hiện một nước đi ở một thế cờ như vậy, chúng ta sẽ lấy ô gạch +, và do đó tất cả các ô gạch ? được liên kết với ô gạch + đó cũng sẽ bị loại bỏ, dẫn đến thế cờ thua mà chúng ta đã bắt đầu với.

Có nhiều thế cờ thắng hay thế cờ thua hơn?
- Với mỗi thế cờ thua có vô số thế cờ có thể được chuyển đổi thành thế cờ thua chỉ trong một nước đi. Do đó, tất cả các thế cờ đó đều là thế cờ chiến thắng.
- Do đó, có nhiều thế cờ thắng hơn thế cờ thua. Do đó, việc ghi nhớ càng nhiều thế cờ thua càng tốt được coi là hiệu quả nhất, tất cả những thế cờ khác đều là thế cờ thắng.

Tạo một danh sách các thế cờ thua mà bạn đã biết, và với mỗi thế cờ đó hãy viết lại tât cả những thế cờ thắng tương ứng và cách phát hiện chúng

Ví dụ sau đây giải thích cho ý của chúng tôi:

Như đã được hiển thị ở phía trên, khi thế cờ chỉ còn 2 hàng ngang, và hàng ngang trên cùng có nhiều hơn hàng ngang thứ hai một ô gạch, thì đây là một thế cờ thua, như được biểu thị ở phần dưới:

#####
####
Lấy thế cờ thua đã biết này, ta có thể xác định được thế cờ thắng tương ứng là:

#####+?
####

#####
####+

#####
####
+???
????

Ở thế cờ bên trái, có thể có số lượng bất kỳ dấu ? ở phía bên phải hàng ngang trên cùng, và ở thế cờ bên phỉa, có thể có số lượng bất kỳ các hàng ngang tạo bởi dấu ? ở bên dưới. Ta có thể kết luận cách xác định những thế cờ thắng này (mà bạn nên nhớ):

- Một thế cờ là thế cờ thắng khi:
  #####
  ####
- - Nếu thế cờ có hai hàng ngang, và hàng ngang đầu không dài hơn hàng ngang thứ hai chính xác một ô gạch, hoặc
- - Nếu thế cờ có nhiều hơn hai hàng ngang, và hàng ngang đầu tiên dài hơn hàng ngang thứ hai chính xác một ô gạch.
Nhưng có nhiều điều cần phải nghĩ về hơn. Ta không chỉ muốn chơi một cách chính xác ở những thế cờ thắng, mà ta còn muốn tránh tạo ra những nước đi tạo ra những thế cờ thắng như vậy. Điều này có nghĩa là ta không nên thực hiện một nước đi ở nơi chỉ còn lại hai hàng ngang, hoặc ở nơi hàng ngang thứ hai có hơn hàng ngang thứ nhất chính xác một ô gạch.

Để kết luận, ta muốn tạo ra các thế cờ thua, những ta cũng muốn tránh tạo ra các thế cờ cách thế cờ thua chỉ một nước đi.

Một điều nữa cần phải lưu ý: do tính phản chiếu đối xứng được nhắc tới ở trên, tất cả những nhận xét trên có thể được lặp lại chỉ bằng cách thay từ "hàng ngang" với từ "cột dọc".

Điều bạn cần làm là thu thấp thêm các thế cờ thua và các thế cờ thắng tương ứng với chúng, mà những thế cờ này cách những thế cờ thua chỉ một nước đi.

Nếu bạn phải thực hiện một bước đi tạo ra thế cờ thua thì sao?
- Nếu bạn nhận ra bạn phải thực hiện một nước đi ở thế cờ thua, thì về lý thuyết, bạn không còn cơ hội thắng. Điều duy nhất bạn có thể làm là hi vọng rằng đối thủ của bạn không biết tất cả các nước đi giành chiến thằng với các thế cờ mà bạn có thể thực hiện với nước đi tiếp theo. Điều bạn có thể làm là loại bỏ một ô gạch duy nhất từ một góc. Điều này sẽ cho đối thủ của bạn một thế cờ kết quả với kích thước tối đa, và khiến nó khó hơn cho đối thủ của bạn trong việc nhận biết nước đi chiến thắng tương ứng.

Làm thế nào để tự học các thế cờ thua?
- Ta sẽ phải thực hiện một thứ được gọi là một cây tìm kiếm hoàn chỉnh. Người chơi đầu tiên bắt đầu bằng cách đoán một nước đi, sau đó người chơi thứ hai đoán một nước đi và cứ thế cho đến khi một người chơi, giả sử là người chơi A, giành chiến thắng. Sau đó người chơi B được phép thay đổi nước đi cuối cùng mà họ đã thực hiện và đến lượt người chơi A. Nếu ở trong một thế cờ mà người chơi sẽ chơi tiếp theo, giả sử là B, hết nước đi do tất cả các nước đi đều dẫn đến thất bại, thì đây là một thế cờ thua, và người chơi B có thể thay đổi nước đi cuối cùng được thực hiện trước khi đạt đến thế cờ thua này.
- 'Cây tìm kiếm' này sẽ được tiếp tục cho đến khi thế cờ bắt đầu là một thế cờ thua, hoặc khi một nước đi nào đó của người chơi 1 biến nó trở thành một thế cờ thua.
- Đây có thể là một quá trình kéo dài nếu một người cố gắng thực hiện điều đó trên bàn chơi ban đầu với rất nhiều ô gạch. Tuy vậy, chúng ta càng biết nhiều thế cờ thua thì chuỗi các nước đi trước khi đạt đến một thế cờ như vậy càng ngắn, và do đó cuộc tìm kiếm trở nên nhanh hơn rất nhiều. Nếu ta biết tất cả các thế cờ thua, thì một là thế cờ bắt đầu sẽ được coi là thế cờ thua, hoặc hai là chỉ một nước đi là cần thiết để dẫn đến một thế cờ thua.

Làm thế nào để học các thế cờ thua với máy tính?
- Ở mức độ khó 'Rất khó' và các thế cờ không lớn hơn 8 x 15 thì máy tính sẽ chơi hoàn hảo nên mỗi thế cờ là kết quả của một nước đi của máy tính đều là một thế cờ thua! Ta nên bắt đầu với những bàn chơi rất nhỏ và chơi với máy tính ở chế độ 'Rất khó' và học hỏi tất cả những thế cờ mà máy tính tạo ra. Với mỗi thế cờ như vậy hãy nghĩ cách để một nước đi của bạn sẽ được máy tính trả lời như thế nào, biến nó trở thành những thế cờ thua nhỏ hơn. Với mỗi thế cờ thua, thế cờ được đối chiếu của nó (hàng ngang <--> cột dọc) là một thế cờ thua.
- Một nước đi đầu tối ưu là gì?
  - Trong cuộc thi, thế cờ đầu sẽ là một hình chữ nhật được tạo ra bởi những viên kẹo. Như đã được chứng minh ở trên, một hình chữ nhật là một thế cờ chiến thắng, những nước đi đầu tiên biến nó trở thành một nước đi thua cho đối thủ của bạn là gì? Ta đã học được ở trên rằng nước đi tối ưu cho một hình vuông là ô gạch (2,2) nhưng nếu hình chữ nhật không phải là một hình vuông thì sao?
  - Chỉ cần chuyển sang chế độ 'rất khó' và để máy tính thực hiện nước đi đầu tiên. Miễn là hình chữ nhật không lớn hơn 8x15, máy tính sẽ chơi một cách tối ưu và sẽ hiển thị nước đi đầu tiên hoàn hảo. Hãy thử các kích cỡ hình chữ nhật khác nhau và nhớ nước đi đầu tiên tối ưu vì nước đi của máy tính sẽ không khả dụng vào những buổi thi :).
- Bạn sẽ sớm trở nên bất bại ở mức độ dễ và trung bình.

Có phải có các tập vô hạn các thế cờ thua không?
- Chúng ta đã gặp hai tập các thế cờ thua này. N là số nguyên dương bất kỳ.
- Đây là những tập khác:

Người chơi máy tính được tích hợp ở trong trò chơi sử dụng các kĩ thuật khác nhau cho các cấp độ chơi khác nhau.

- Dễ - Mỗi lượt, hãy thực hiện các nước đi bất kỳ. Nếu một thế cờ thắng được phát hiện, nó sẽ thực hiện một nước đi tới đó.
- Trung bình - Vẫn thực hiện những nước đi bất kỳ, nhưng với lượng kiến thức rộng hơn về các thế cờ thắng và thua. Sẽ tránh các nước đi giúp đối thủ có thể tiếp cận với một nước đi chiến thắng đơn giản.
- Khó - Có lượng kiến thức về các thế cờ thắng thậm chí còn lớn hơn những cấp độ trước đó. Chủ động tìm trên bàn chơi những nước đi có thể ép đối phương phải thực hiện một nước đi dẫn đến thua cuộc.
- Rất khó - Sẽ luôn luôn thực hiện các nước đi tối ưu với bất kỳ thế cờ nào có thể cho vừa vào một hình chữ nhật có kích thước 8x15.
Mức độ khó càng cao, sẽ càng khó để ép máy tính vào thế cờ thua. Mỗi mức độ khó sẽ biết nhiều thế cờ thắng và thế cờ thua hơn mức độ trước nó, và với mức độ càng khó, thì bạn càng phải biết thêm nhiều thế cờ thắng và thế cờ thua để cố gắng và ép máy tính vào một thế cờ thua.

Những nhận xét sau đây sẽ không giúp bạn chơi Chomp giỏi hơn, nhưng nó sẽ cho ta một số kiến thức thú vị và cho ta một cơ hội khác để thực hành minh chứng bằng phép quy nạp.

Có bao nhiêu thế cờ, bao gồm cả bàn chơi trống, có thể cho vừa một hình chữ nhật với P hàng ngang và Q hàng dọc?
- Nếu chúng ta bao gồm cả hình chữ nhật trống, chúng ta có thể tính được tổng số các thế có thể có bằng cách sử dụng công thức sau: \[\frac{(P+Q)!}{P!Q!}\]Bạn có thể tính một con số cho P và Q nhỏ không, và xác nhận là số đó là chính xác không?
- Phép lấy đạo hàm đầu tiên của một công thức đệ quy
  - Gọi f(P,Q) là số thế cờ trong một hình chữ nhật với kích thước PxQ. Một sự quan sát quan trọng là tất cả các thế cờ đều có hình dáng của một cầu thang, trong đó mỗi hàng có số lượng ô gạch bằng hàng ngang trên cùng, nhưng không có nhiều ô gạch hơn.
  - Hãy bắt đầu với cách ta có thể miêu tả tất cả những bậc thang này. Một cách để tạo ra những bậc thang này một cách dễ dàng là bắt đầu ở góc dưới bên dưới bàn chơi, và di chuyển sang phải hoặc di chuyển lên trên. Một người có thể tiếp tục thực hiện những nước đi sang phải hoặc lên trên cho đến khi họ có thể đạt đến góc trên cùng bên phải của bàn chơi. Ta sẽ gọi đây là đường đi mà chúng ta đã đi từ (P,0) tới (0,Q).
  - Số lượng thế cờ bằng số lượng các đường đi từ (P,0) đến (0,Q), miễn là một người chỉ được di chuyển lên trên hoặc về bên phải. Số f(P,Q+1) đường đi để đi từ (P,0) tới (0,Q+1) là số f(P,Q) đường đi để đi từ (P,0) tới (0,Q) và sau đó tói (0,Q+1) + số f(P-1,Q) đường đi để đi từ (P,0) tới (1,Q), và sau đó tới (1,Q+1) và (0,Q+1), v.v Công thức tương ứng như sau:\[f(P,Q+1) = f(P,Q) + f(P-1,Q) + f(P-2,Q) + \ldots + f(1,Q) + f(0,Q)\]
  - Chúng ta sẽ lấy công thức này và thay thế P với P+1. Nếu ta cho P + 1 vào một công thức thay vì P, chúng ta sẽ có: \[f(P+1,Q+1) = f(P+1,Q) + f(P,Q) + f(P-1,Q) + \ldots + f(0,Q)\] \[f(P+1,Q+1) = f(P+1,Q) + f(P,Q+1)\]Từ dẫn xuất mới này, ta có thể xác định được công thức \(f(P,Q) = f(P,Q-1) + f(P-1,Q)\) nơi \(f(P,0) = 1\) và \(f(0,Q) = 1\).
- Một phép lấy đạo hàm khác của một công thức đệ quy
  - Thông thường thì có một vài cách để đến trong các bài toán tổ hợp. Phép lấy đạo hàm sau sẽ cung cấp một cách khác biệt và tao nhã hơn để rút ra công thức.
  - Ta sẽ sử dụng sự biểu diễn tương tự với trước đó, mà chúng ta muốn tìm tổng các đường đi dẫn chúng ta từ (P,0) tới (0,Q). Ta có thể sắp xếp những đường đi sau thành hai nhóm.
  - Các đường đi bắt đầu với nước đi sang bên phải từ điểm (P,0) tới (P,1). Ta biết được rằng trong nhóm này, ta sẽ có tổng của f(P,Q-1) đường đi từ điểm (P,1) tới (0,Q). Ta biết điều này vì hình chữ nhật còn lại sau khi di chuyển sang bên phải có kích thước là P x (Q-1).
  - Nhóm còn lại là các đường đi bắt đầu bằng nước đi đầu tiên là nước đi lên một bước từ (P,0) tới (P-1,0). Trong nhóm này, ta biết được có tổng cộng f(P-1,Q) đường đi, vì hình chữ nhật thu được sẽ có kích cỡ là (P-1) x Q.
  - Do đó, vì mỗi đường đi có thể có sẽ rơi vào một trong hai nhóm này, tổng số các đường đi sẽ là tổng của các nhóm trên. Điều này sẽ cho chúng ta công thức tương tự \(f(P,Q) = f(P,Q-1) + f(P-1,Q)\).
- Phép lấy đạo hàm của một công thức hiện
  - Thay vì bắt đầu các đường đi từ góc dưới cùng bên phải, hãy xoay hình chữ nhật sao cho điểm (P,0) nằm ở phía trên. Ta có thể hình dung ra các đường đi bằng sơ đồ sau:
  - Dạng sơ đồ này được biết đến là một sơ đồ cây. Mô hình này sẽ tiếp tục được lặp lại cho đến khi ta đã di chuyển từ (P,0) tới (0,Q). Khi điều này xảy ra, sơ đồ cây sẽ chứa mọi đường đi mà một người có thể thực hiện trên bàn chơi.
  - Số lượng các cách để đi từ đỉnh (P,1) đến một giao điểm (I,J) trong sơ đồ cây là cách để đi tới (I-1,J) và sau đó đi xuống bên phải tới (I,J), công với số lượng các cách để đi tới (I,J-1), và rồi đi xuống bên trái tới (I,J). Nói cách khác, đây là số trong Tam giác Pascal.
  - Mỗi một số trong Tam giác Pascal là tổng của hai số bên trên nó. Các số ở trong cột dọc bên trái đang đếm các hàng của bàn chơi, bắt đầu với số 0 với một bàn chơi trống. Các số phía dưới hình tam giác đại diện cho vị trí từ bên trái, cũng bắt đầu từ số 0. Số ở hàng thứ N ở vị trí K bằng với \({N \choose K} = \frac{N!}{(N-K)!K!}\).
  - Ta muốn tìm số f(p,q), là số các cách để đi từ (P,0) tới (0,Q). Để là được điều đó, một người phải đi từ trên cùng P lần xuống dưới bên phải và Q lần xuống dưới bên trái. Bằng cách sử dụng cấu trúc sơ đồ cây mà ta đã xác định ở trước đó, điều này giống như việc đi từ (0,0) tới (P,Q), chỉ đi sang trái và sang phải trong sơ đồ cây.
  - Dù vậy, điều này khiến chúng ta thực hiện P+Q bước đi, nên chúng ta đang ở hàng P+Q ở trong sơ đồ cây. Do ta biết rằng ta đã di chuyển được Q lần sang bên phải, số nằm trong Tam giác Pascal ở vị trí này là \({P+Q \choose Q} = \frac{(P+Q)!}{P!Q!}\).
- Chứng minh công thức hiện bằng phương pháp quy nạp
  - Ta sẽ chứng minh rằng những công thức dưới đây là tương đương. \[f(P,Q) = \begin{cases}1 & for & P=0 \\1 & for & Q=0 \\f(P,Q-1) + f(P-1,Q) & for & \text{P>0 and Q>0}\end{cases} = \Bigg\{{P+Q \choose Q} = \frac{(P+Q)!}{P!Q!}\]
  - Cơ sở quy nạp: Ta đã biết rằng f(0,0) = 1 bằng định nghĩa công thức. Nếu ta cho P=0 và Q=0 vào trong công thức, ta sẽ có \(\frac{(0+0)!}{0!0!} = \frac{0!}{1} = 1\). Điều này cho thấy rằng các công thức cơ sở là tương đương, điều này làm kết thúc cơ sở quy nạp.
  - Giả thuyết quy nạp: Hãy giả sử rằng các công thức là tương đương với tất cả giá trị của P,Q với P+Q = N.
  - Bước quy nạp: Sử dụng giả thuyết quy nạp, ta chứng minh được sự tương đương với tất cả giá trị P,Q với P+Q=N+1. Với bất kỳ giá trị P,Q với P+Q=N+1, ta sẽ có 3 trường hợp:
  - Trường hợp 1:
  - Trường hợp 2:
  - Trường hợp 3: \(P,Q > 0\) \[ \begin{align} f(P,Q) &= f(P,Q-1) + f(P-1,Q)\qquad\qquad (+)\\ &= \frac{(P+Q-1)!}{P!(Q-1)!} + \frac{(P-1+Q)!}{(P-1)!Q!}\\ &= \frac{(P+Q-1)!Q}{P!(Q-1)!Q} + \frac{(P-1+Q)!P}{(P-1)!PQ!}\\ &= \frac{(P+Q-1)!}{P!Q!} (Q+P)\\ &= \frac{(P+Q)!}{P!Q!} \end{align} \]
  - (+): Nếu P + Q = N + 1, thì P + Q-1 = N, tức là sử dụng giả thuyết quy nạp.
    f(P,Q-1) = \(\frac{(P+(Q-1))!}{(P!(Q-1)!)}\), và tương tự với f(P-1, Q)
  - Điều này cho thấy hai công thức của f(P,Q) là tương đương nhau.
  - Kết thúc chứng minh. ∎

Có bao nhiêu vị trí khác nhau có P hàng ngang và Q hàng dọc?
- Một người chỉ cần sử dụng công thức tương đương cho tất cả các thế cờ cho vừa một hình chữ nhật với P-1 hàng ngang và Q-1 cột dọc, đó là f(P-1, Q-1).

Có nhiều thế cờ thua hay thế cờ thắng hơn?
- Nếu một thế cờ có N ô gạch, thì người chơi 1 có N lựa chọn cho nước đi đầu tiên. Được di chuyển đầu tiên sẽ cho người chơi 1 lợi thế, và điều đó có nghĩa là sẽ có nhiều thế cờ thắng hơn là thế cờ thua. Trong một mục trước đó, ta đã xác định được có bao nhiêu thế cờ thua trong những thế cờ với 2,3,4 hoặc 5 ô gạch. Đây là một số con số xác nhận được xu hướng rằng một thế cờ có càng nhiều ô gạch, thì khả năng đó là thế cờ thắng càng cao.
- # ô gạch # thế cờ # thế cờ thua % thế cờ thua
  20 627 42 6.69
  30 5604 220 3.92
  40 37338 1022 2.73
  50 204226 4976 2.43
  60 966467 20106 2.08
  70 4087968 76688 1.87
  80 15796476 270142 1.71
  90 56634173 897964 1.58
- Chức năng nào của 2 đối số '# thế cờ' và '# thế cờ thua' mang lại giá trị gần như giống nhau cho mỗi hàng của bảng trên?
  - Đáp án được cung cấp ở mục khám phá sau.

# ô gạch	# thế cờ	# thế cờ thua	% thế cờ thua
20	627	42	6.69
30	5604	220	3.92
40	37338	1022	2.73
50	204226	4976	2.43
60	966467	20106	2.08
70	4087968	76688	1.87
80	15796476	270142	1.71
90	56634173	897964	1.58

Giả thuyết bởi Caribou

Trước đó, ta đã cho thấy được rằng mỗi thế cờ là một thế cờ thắng hoặc thế cờ thua. Minh chứng này cung cấp cho ta một phương pháp trực tiếp để xác định được từng bước với tất cả các thế cờ dù nó là thế cờ thua hay thắng. Điều đặc biệt là phương pháp này không cần phải tìm kiếm (thử các nước đi). Điều này làm ta nhớ đến 'Sàng Eratosthenes' để xác định tất cả các số nguyên tố lớn đến một kích thước nào đó.

Đọc vê Sàng Eratosthenes, chẳng hạn như ở trên Internet
- Để tìm tất cả các số nguyên tố với kích cỡ lên đến N², trong đó N là một số nguyên nào đó, ta sẽ làm như sau:
- - A: Bắt đầu với số nguyên tố p=2.
  - B: Gạch đi tất cả các bội của p cho đến N².
  - C: Tìm số lớn nhất tiếp theo > p mà chưa bị gạch bỏ. Nếu số đó > N, thì thuật toán dừng lại. Nếu không, gọi đây là số p và tiếp tục với bước B.
- Tất cả các số lên tới N² mà không bị gạch bỏ đều là các số nguyên tố < N². Người ta có thể tìm một bản mô phỏng của thuật toán này trên https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Phân tích này tạo cảm hứng cho ta nghĩ về thêm các điểm tương đồng giữa các số nguyên tố và các thế cờ thua. Điều này dẫn đến một giả thuyết cho thế cờ thua giống như 'Định lý số nguyên tố'. Đây là các chi tiết.

Bảng: Sự giống nhau giữa các thế cờ thua trong Chomp và các số nguyên tố:

Các số	Chomp
Có vô hạn các số nguyên.	Có vô hạn thế cờ Chomp.
Có các số nguyên tố và các số có thể phân giải thành thừa số.	Có các thế cờ thua và thế cờ thắng.
Có vô hạn các số nguyên tố.	Có vô hạn các thế cờ thua.
Một số có thể phân giải thành thừa số là kết quả của một số nguyên tố và một số khác.	Một vị trí thắng là tổng của một vị trí thua và một vị trí khác (vì hình được cắt ra từ một nước đi mang dạng hình bậc thang. và do đó là một thế cờ).
Khi một số nguyên tố được xác định, ta sẽ ngay lập tức biết được vô hạn các số có thể phân giải thành thừa số (tất cả các bội số của số nguyên tố).	Khi một thế cờ thua được xác định, ta sẽ ngay lập tức biết được vô hạn các thế cờ thắng (tất cả các thế cờ là kết quả của việc lấp đầy các hình chữ nhật ở góc, bao gồm các hình chữ nhật dài vô hạn nằm ở hàng ngay trên cùng và cột bên trái).
Một số lớn có khả năng bị chia bởi một số nguyên tố nhỏ cao hơn là bởi một số nguyên tố lớn.	Một thế cờ lớn có khả năng bị giảm về một thế cờ thua nhỏ cao hơn bị giảm về thế cờ thua lớn.
Để xác định xem số N có phải một số nguyên tố không, sẽ là hiệu quả nếu biết tất cả các số nguyên tố P lên tới căn bậc hai của N. Sau đó, ta có thể kiểm tra xem N có thể bị giảm về P hay không bằng phép chia, tức là bằng phép chia thử N / P.	Để xác định xem thế cờ P có phải là một thế thua hay không, việc biết tất cả các thế cờ thua L nằm trong P là cần thiết. Sau đó, ta có thể kiểm tra một cách hiệu quả xem liệu P có thể bị giảm thành L trong một nước đi hay không.
'Sàng Eratosthenes' là một cách thức hiệu quả để xác định tất cả các số nguyên cho đến một số N, nhưng cũng để kiểm tra xem liệu một số cho sẵn có phải là một số nguyên tố hay không. Thuật toán này đã được miêu tả ở trên.	Tương tự với 'Sàng Eratosthenes', một người bắt đầu với thế cờ thua {1}, và loại bỏ tất cả các thế cờ thắng mà sẽ biến thành thế cờ thua đó chỉ trong một nước đi. Sau đó, người đó kiểm tra tất cả các thế cờ với nhiều hơn một ô gạch. Tất cả các thế cờ không bị loại bỏ đều là thế cờ thua.
Sự không hiệu quả còn lại của thuật toán sàng bao gồm việc loại bỏ được lặp đi lặp lại của các số có thể phân giải thành thừa số.	Sự không hiệu quả còn lại của thuật toán sàng bao gồm việc loại bỏ được lặp đi lặp lại của các thế cờ thắng.
Mật độ của các số nguyên tố giảm dần theo kích cỡ của chúng, tức là tỉ lệ (# số nguyên tố cho đến một số nguyên N) / N giảm khi N tăng.	Mật độ của các thế cờ thua giảm dần theo kích cỡ của chúng, tức là tỉ lệ (# số thế cờ thua cho đến N ô gạch) / (# tất cả các thế cờ với N ô gạch) giảm khi N tăng. (Thử thách: Công thức cho sự phụ thuộc của tỷ lệ này vào N là gì và nó so sánh như thế nào với công thức tính mật độ của các số nguyên tố?)
Định lý số nguyên tố: (# nguyên tố ≤ N) / (N / log(N)) → 1 bằng N → vô hạn.	Giả thuyết tương đương: (# các thế cờ thua với N ô gạch) / ((# các thế cờ với N ô gạch) / log(# các thế cờ với N ô gạch)) → 0.283... bằng N → vô hạn.

Bảng: Sự khác nhau giữa các thế cờ thua trong Chomp và các số nguyên tố:

Các số	Chomp
Tập hợp tất cả các số nguyên là một tập hợp có thứ tự toàn phần; tức là giữa hai số bất kỳ, người ta biết số nào lớn hơn.	Tập hợp tất cả các thế cờ trong Chomp là một tập hợp có thứ tự một phần. Các thế cờ có thể được chứa hoàn toàn trong các thế cờ khác, nhưng điều này là không cần thiết.
Hoạt động rút gọn một số thành thừa số nguyên tố là phép chia	Hoạt động để giảm một thế cờ thành thế cờ thua là trừ đi các ô gạch.
Một số có thể được hình dung dưới dạng một đoạn thẳng trên trục số một chiều.	Một thế cờ được định nghĩa qua một danh sách các số được phân loại bởi kích thước của chúng, do đó nó là một vật thể 2D.

Câu hỏi mở:

Giải thuyết (số lượng các thế cờ thua với N ô gạch) / (số lượng tất cả các thế cờ với N ô gạch)) 0.283... là N → vô hạn đúng hay không?

Bạn có thể chứng minh điều đó không? (Chúng tôi chưa thể chứng minh điều đó :-) )

Trò chơi Chomp được chơi ở phía trên là phiên bản 2D của Chomp. Điều này có nghĩa là bàn chơi ở dạng 2 chiều, chỉ có chiều rộng và chiều dài.

Bạn có thể tưởng tượng một phiên bản 3D của Chomp hay không?
- Cách dễ nhất để tưởng tượng thêm một chiều không gian khác vào trò chơi là bằng cách thêm một chiều không gian thứ ba vào bàn chơi. Thay vì chỉ có chiều dài và chiều rộng, bàn chơi mới sẽ có chiều dài, chiều rộng và chiều cao. Nếu một người phải chơi với những khối lập phương nhỏ, như một con xúc xắc, thì người đó có thể chơi phiên bản 3D của trò chơi này như được biểu diễn ở bức tranh bên dưới.
- Khi thực hiện một nước đi, một người sẽ phải loại bỏ khối lập phương đã được chọn, cũng như tất cả các khối về phía bên trái, bên trên và ở trên cùng của khối được chọn. Một nước đi thử nghiệm được đánh dâu bằng màu vàng trong bức tranh, điều này cũng sẽ loại bỏ tất cả các ô gạch màu xanh lá trong bức tranh. Người chơi lấy ô gạch cuối cùng, được biểu diễn bởi ô gạch màu đỏ trong bức tranh, là người chơi thua cuộc.
- Để làm trò chơi này dễ hơn với các khối lập phương thật, một người có thể đẩy các khối lập phương sát vào góc, như góc của một hộp giày, để ô gạch đỏ nằm ở góc trong cùng của hộp, và chỉ có thể được tiếp cận khi tất cả các khối gạch khác đã bị loại bỏ. Sử dụng chiếc hộp là không cần thiết, nhưng nó sẽ làm ổn định các khối lập phương và giúp loại bỏ các khối mà không cần làm đổ toàn bộ cấu trúc.

Thế còn việc chơi trò Chomp trên những chiều không gian lớn hơn thì sao?
- Trước đây, chúng ta đã xác định rằng việc thêm một chiều không gian mới cho trò Chomp khá dễ dàng. Nếu ta muốn chơi trò Chomp ở một chiều không gian cao hơn 3D, ta sẽ tiếp tục thêm những chiều không gian mới cho bàn chơi Chomp. Tuy nhiên, nếu cao hơn 3D, sẽ không có cách để mô phỏng bàn chơi Chomp bằng việc sử dụng các khối. Vậy nhưng, có một cách để mô phòng trò Chomp bằng cách sử dụng bút chì và giấy, và phương pháp này cho phép chúng ta chơi trò chơi ở bất kỳ chiều không gian nào, không chỉ 2D hoặc 3D.
- Chúng ta sẽ bắt đầu bằng việc chơi trò 2D Chomp trên giấy. Một cách để mô phỏng trò chơi là lựa chọn một số chỉ có 2 cách phân giải thừa số nguyên tố trước tiên. Ví dụ, 2^P x 3^Q x 5^R. Sau đó, ta viết xuống tất cả các thừa số của số này ở dạng một hình chữ nhật, như được biểu diễn dưới đây.
- 72 36 18 9
  24 12 6 3
  8 4 2 1
- Bất kỳ số lân cận bên phải nào cũng nhỏ hơn theo hệ số 2 và bất kỳ số lân cận nào bên dưới cũng nhỏ hơn theo hệ số 3. Để thực hiện một nước đi trên bàn chơi này, ta sẽ chọn một số. Sau đó, ta sẽ loại bỏ một số, cùng với bất kỳ một thừa số nào của nó. Bất kỳ ai phải lựa chọn số 72 sẽ là người thua cuộc.
- Để có một hình chữ nhật ban đầu lớn hơn, ta có thể tìm một số lớn hơn bằng cách sử dụng công thức 2^P x 3^Q. Bằng việc thay thế P và Q với các số lớn hơn, ta có thể có được bàn chơi lớn hơn nữa cho trò 2D Chomp.
- Làm cách nào để tổng quát hoá sự mô phỏng này cho các chiều không gian cao hơn?
  - Để mở rộng phiên bản sử dụng bút chì và giấy này của trò Chomp từ 2D lên 3D, một người chỉ cần mở rộng công thức sử dụng để tìm số bắt đầu. Thay vì lựa chọn một số chỉ có 2 cách phân giải thừa số nguyên tố, ta sẽ chọn một số có 3 cách phân giải thừa số nguyên tố khác nhau. Chúng ta có thể dùng một công thức mới để tìm số này như sau: 2^P x 3^Q x 5^R. Sau đó, bằng cách sử dụng phương pháp tương tự như trước, trò chơi có thể được mô phỏng dưới dạng 3 chiều. Việc tăng chiều không gian đơn giản yêu cầu việc thêm các số nguyên tố mới vào công thức, phụ thuộc vào số chiều không gian mà bạn muốn có.