Free Time Remaining For Today: 4:59
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | Русский2048
Tổng số người chơi: 859180
Tổng số trận thắng: 104188
Tổng số trận thắng: 104188
Các trò chơi trước của bạn
Giới thiệu Mô tả &; Cách chơi2048 là một trò chơi một người chơi, nơi một người trượt và hợp nhất các ô. Trò chơi được chơi trên một bảng hình chữ nhật (4 x 4 theo mặc định), trong đó một số ô vuông của bảng có các ô được đánh số trong đó.
Để phát, trượt nhanh hoặc sử dụng các phím mũi tên để trượt tất cả các ô theo hướng tương ứng.
Gạch sẽ tiếp tục di chuyển cho đến khi chúng bị dừng lại bởi cạnh của bảng hoặc một ô dừng khác. Nếu hai ô có cùng số va chạm
, thì chúng sẽ hợp nhất với nhau thành một ô duy nhất được đánh số với tổng của hai ô đã va chạm. Gạch mới này sẽ di chuyển theo cùng một hướng cho đến khi dừng lại theo cách tương tự như các ô khác.
Sau khi di chuyển, một ô mới sẽ xuất hiện ngẫu nhiên. Giá trị số của ô mới có 90% cơ hội là 2 và 10% cơ hội là 4.
Nếu bạn thực hiện một động tác không di chuyển hoặc thay đổi bất kỳ ô nào trên bảng, thì di chuyển của bạn sẽ không được tính (tức là nó sẽ được coi là hoàn toàn không di chuyển). Nếu bạn không thể thực hiện một động thái, thì trò chơi kết thúc.
Để phát, trượt nhanh hoặc sử dụng các phím mũi tên để trượt tất cả các ô theo hướng tương ứng.
Gạch sẽ tiếp tục di chuyển cho đến khi chúng bị dừng lại bởi cạnh của bảng hoặc một ô dừng khác. Nếu hai ô có cùng số va chạm
, thì chúng sẽ hợp nhất với nhau thành một ô duy nhất được đánh số với tổng của hai ô đã va chạm. Gạch mới này sẽ di chuyển theo cùng một hướng cho đến khi dừng lại theo cách tương tự như các ô khác.
Sau khi di chuyển, một ô mới sẽ xuất hiện ngẫu nhiên. Giá trị số của ô mới có 90% cơ hội là 2 và 10% cơ hội là 4.
Nếu bạn thực hiện một động tác không di chuyển hoặc thay đổi bất kỳ ô nào trên bảng, thì di chuyển của bạn sẽ không được tính (tức là nó sẽ được coi là hoàn toàn không di chuyển). Nếu bạn không thể thực hiện một động thái, thì trò chơi kết thúc.
Quy tắc kỹ thuật bổ sungTrong phần sau đây, □ đề cập đến một hình vuông lưới trống. Nếu một ô là kết quả của sự hợp nhất trong một di chuyển, thì
nó không thể là một phần của một hợp nhất khác trong cùng một di chuyển (ví dụ: Nếu có một hàng có 2 2 4 8, thì việc di chuyển sang phải sẽ chỉ dẫn đến □ 4 4 8). Nếu 3 ô bằng nhau liên tiếp di chuyển cùng nhau, thì 2
ô xa nhất dọc theo hướng chuyển động sẽ hợp nhất (ví dụ: Nếu có một hàng có 2 2 2 □, thì việc di chuyển sang phải sẽ dẫn đến □ □ 2 4). Nếu 4 ô bằng nhau liên tiếp di chuyển cùng nhau, thì 2 ô
đầu tiên và 2 ô cuối cùng sẽ hợp nhất (ví dụ: Nếu có một hàng có 2 2 2 2, thì việc di chuyển sang phải sẽ dẫn đến □ □ 4 4).
nó không thể là một phần của một hợp nhất khác trong cùng một di chuyển (ví dụ: Nếu có một hàng có 2 2 4 8, thì việc di chuyển sang phải sẽ chỉ dẫn đến □ 4 4 8). Nếu 3 ô bằng nhau liên tiếp di chuyển cùng nhau, thì 2
ô xa nhất dọc theo hướng chuyển động sẽ hợp nhất (ví dụ: Nếu có một hàng có 2 2 2 □, thì việc di chuyển sang phải sẽ dẫn đến □ □ 2 4). Nếu 4 ô bằng nhau liên tiếp di chuyển cùng nhau, thì 2 ô
đầu tiên và 2 ô cuối cùng sẽ hợp nhất (ví dụ: Nếu có một hàng có 2 2 2 2, thì việc di chuyển sang phải sẽ dẫn đến □ □ 4 4).
Mục tiêu của trò chơiMục tiêu là tạo ra một ô có giá trị số cao nhất có thể. Trò chơi được gọi là 2048 vì trong phiên bản cổ điển của trò chơi, bạn giành chiến thắng khi đã tạo một ô có số 2048. Trong phiên bản trò chơi của chúng tôi, điểm số là tổng của tất cả các ô. Một mặt, tổng này có liên quan chặt chẽ đến giá trị hàng đầu. Mặt khác, điều này tốt hơn cho phép người ta đo lường tiến trình nhỏ hơn.
2048, giống như tất cả các trò chơi trong Cuộc thi Caribou, đôi khi được giới thiệu trong các cuộc thi toán học của chúng tôi. Chúng tôi sẽ thông báo trước khi điều này xảy ra. Khi 2048 được sử dụng như một câu hỏi cuộc thi tương tác, chiến thắng có thể dựa trên ô có giá trị cao nhất của bạn hoặc trên tổng số điểm của bạn.
2048, giống như tất cả các trò chơi trong Cuộc thi Caribou, đôi khi được giới thiệu trong các cuộc thi toán học của chúng tôi. Chúng tôi sẽ thông báo trước khi điều này xảy ra. Khi 2048 được sử dụng như một câu hỏi cuộc thi tương tác, chiến thắng có thể dựa trên ô có giá trị cao nhất của bạn hoặc trên tổng số điểm của bạn.
Thời gian tối thiểu để đạt được điểm số lớnHãy tưởng tượng bạn đang chơi 2048. Giả sử bạn thực hiện một bước di chuyển cứ sau 2 giây và quản lý để đạt được điểm số cao (tổng số), ví dụ: 2048.
Điều đó sẽ mất bao lâu?Khi thực hiện 10 nước đi thì trung bình sẽ có chín 2s và một 4 được tạo ra. Họ sẽ tăng tổng ô lên 9×2 + 4 = 22. Quá trình này sẽ mất trung bình 2048 điểm / (22 điểm / 10 nước đi) ≈ 930 nước đi và 930 nước đi×2 giây / di chuyển = 1860 giây = 31 phút. Trong thực tế, nó sẽ mất nhiều thời gian hơn. Sẽ cần nhiều nỗ lực vì trò chơi kết thúc sớm hơn.
Strategy Quan sát- Một ô mới xuất hiện mỗi khi di chuyển được thực hiện.
- Cách duy nhất để giảm số lượng ô trên bảng là hợp nhất chúng.
- Phải mất nhiều hợp nhất hơn để tạo số ô lớn hơn các ô nhỏ hơn.
Đặt gạch ở đâu?Điều quan trọng là phải định vị gạch của bạn một cách chính xác. Ví dụ: hãy xem xét một hàng trông như thế này: □ 2 8 2.
Nếu bạn di chuyển sang trái hoặc phải, sẽ không có sự hợp nhất nào diễn ra trên hàng đó. Điều này là do 8 'khối' 2s hợp nhất với nhau. Nếu chúng ta có số 8 trên hình vuông ngoài cùng bên trái hoặc hình vuông ngoài cùng bên phải, chẳng hạn như □ 2 2 8, thì việc hợp nhất sẽ dễ dàng. Do đó, chúng tôi muốn gạch lớn nằm trên các cạnh. Các ô nhỏ rất dễ hợp nhất, vì vậy vị trí của chúng không quan trọng bằng.
∴ Do đó, ô lớn nhất nên nằm ở một góc, bởi vì vùng lân cận của các số gạch rất khác nhau chỉ tốn không gian mà không có cơ hội hợp nhất trong tương lai.
Nhưng còn lớn thứ hai thì sao? Hãy xem xét một hàng khác có thể: 128 2 2 128. Di chuyển sang trái hoặc phải sẽ không kết hợp 128s. Sẽ rất khó để tạo ra một ô 128 khác và nó sẽ yêu cầu nhiều lần di chuyển để hợp nhất 128s.
Chúng ta cần hợp nhất các ô trong càng ít di chuyển càng tốt. Mỗi bước di chuyển, một ô khác xuất hiện. Càng có nhiều gạch, tình hình càng trở nên tồi tệ hơn và cách duy nhất để giảm số lượng gạch là hợp nhất chúng.
∴Do đó, gạch lớn thứ hai nên nằm cạnh gạch lớn nhất, bởi vì nó làm cho việc hợp nhất các ô lớn dễ dàng hơn.
∴Gạch nên được di chuyển sao cho chúng càng lớn, chúng càng gần góc với viên gạch lớn nhất.
Nếu bạn di chuyển sang trái hoặc phải, sẽ không có sự hợp nhất nào diễn ra trên hàng đó. Điều này là do 8 'khối' 2s hợp nhất với nhau. Nếu chúng ta có số 8 trên hình vuông ngoài cùng bên trái hoặc hình vuông ngoài cùng bên phải, chẳng hạn như □ 2 2 8, thì việc hợp nhất sẽ dễ dàng. Do đó, chúng tôi muốn gạch lớn nằm trên các cạnh. Các ô nhỏ rất dễ hợp nhất, vì vậy vị trí của chúng không quan trọng bằng.
∴ Do đó, ô lớn nhất nên nằm ở một góc, bởi vì vùng lân cận của các số gạch rất khác nhau chỉ tốn không gian mà không có cơ hội hợp nhất trong tương lai.
Nhưng còn lớn thứ hai thì sao? Hãy xem xét một hàng khác có thể: 128 2 2 128. Di chuyển sang trái hoặc phải sẽ không kết hợp 128s. Sẽ rất khó để tạo ra một ô 128 khác và nó sẽ yêu cầu nhiều lần di chuyển để hợp nhất 128s.
Chúng ta cần hợp nhất các ô trong càng ít di chuyển càng tốt. Mỗi bước di chuyển, một ô khác xuất hiện. Càng có nhiều gạch, tình hình càng trở nên tồi tệ hơn và cách duy nhất để giảm số lượng gạch là hợp nhất chúng.
∴Do đó, gạch lớn thứ hai nên nằm cạnh gạch lớn nhất, bởi vì nó làm cho việc hợp nhất các ô lớn dễ dàng hơn.
∴Gạch nên được di chuyển sao cho chúng càng lớn, chúng càng gần góc với viên gạch lớn nhất.
Hướng 'tốt' và 'xấu' để di chuyển vàoNgười ta nên cố gắng giữ viên gạch lớn nhất trong một góc. Tuy nhiên, gạch trượt có thể di chuyển nó ra khỏi góc, và nếu một ô sau đó ngẫu nhiên xuất hiện ở góc thì bạn đang gặp rắc rối.
Trước khi tiếp tục, chúng tôi sẽ chọn góc trên cùng bên trái vì lợi ích của cuộc thảo luận này. Bạn có thể chọn bất kỳ góc nào bạn thích và áp dụng logic tương tự như chúng tôi. Nếu ô lớn nhất bạn có nằm ở góc trên cùng
bên trái, thì nếu bạn di chuyển lên hoặc sang trái thì bạn sẽ luôn giữ ô lớn nhất ở góc trên cùng bên trái. Tuy nhiên, điều này chỉ hoạt động cho một vài động thái. Bạn sẽ nhanh chóng rơi vào tình huống không thể di chuyển lên hoặc rời đi.
Sau đó, chúng ta sẽ phải di chuyển theo hướng thứ ba. Đôi khi, có thể trượt các ô sao cho gạch lớn nhất không rời khỏi góc. Ví dụ: nếu trước tiên chúng ta đảm bảo rằng cột bên trái không chứa các ô trống □ cũng như các ô có giá trị bằng nhau sẽ hợp nhất, thì chúng ta có thể trượt xuống mà không cần di chuyển ô lớn nhất ra khỏi góc. Tương tự, chúng ta có thể trượt sang phải nếu chúng ta đảm bảo hàng trên cùng được lấp đầy mà không có hàng xóm bằng nhau trước.
Có một chi phí để di chuyển xuống hoặc phải. Nếu bạn di chuyển xuống, thì các ô ở hàng trên cùng sẽ di chuyển ra ngoài. Nếu bạn di chuyển sang phải, thì các ô ở cột bên trái sẽ di chuyển ra ngoài. Trừ khi, tất nhiên, họ bị chặn di chuyển như mô tả ở trên. Dù bằng cách nào, bạn sẽ phải dành các bước di chuyển để làm lại hàng trên cùng hoặc cột bên trái. Những gì người ta có thể làm là ưu tiên giữa việc di chuyển xuống hoặc sang phải, ví dụ, chỉ di chuyển sang phải nếu không thể di chuyển khác.
∴ Nói chung, bạn nên di chuyển theo hai hướng đẩy viên gạch lớn nhất vào góc mà nó đang ở. Cố gắng sắp xếp các ô được sắp xếp theo kích thước số lượng của chúng. Điền cột bên trái để bạn có tùy chọn di chuyển theo hướng thứ ba mà không cần di chuyển ô góc. Nếu bạn phải di chuyển theo hướng thứ tư (trong ví dụ của chúng tôi, sang phải) thì sẽ rất vui khi có hàng trên cùng được lấp đầy để giữ giá trị tối đa ở góc.
Trước khi tiếp tục, chúng tôi sẽ chọn góc trên cùng bên trái vì lợi ích của cuộc thảo luận này. Bạn có thể chọn bất kỳ góc nào bạn thích và áp dụng logic tương tự như chúng tôi. Nếu ô lớn nhất bạn có nằm ở góc trên cùng
bên trái, thì nếu bạn di chuyển lên hoặc sang trái thì bạn sẽ luôn giữ ô lớn nhất ở góc trên cùng bên trái. Tuy nhiên, điều này chỉ hoạt động cho một vài động thái. Bạn sẽ nhanh chóng rơi vào tình huống không thể di chuyển lên hoặc rời đi.
Sau đó, chúng ta sẽ phải di chuyển theo hướng thứ ba. Đôi khi, có thể trượt các ô sao cho gạch lớn nhất không rời khỏi góc. Ví dụ: nếu trước tiên chúng ta đảm bảo rằng cột bên trái không chứa các ô trống □ cũng như các ô có giá trị bằng nhau sẽ hợp nhất, thì chúng ta có thể trượt xuống mà không cần di chuyển ô lớn nhất ra khỏi góc. Tương tự, chúng ta có thể trượt sang phải nếu chúng ta đảm bảo hàng trên cùng được lấp đầy mà không có hàng xóm bằng nhau trước.
Có một chi phí để di chuyển xuống hoặc phải. Nếu bạn di chuyển xuống, thì các ô ở hàng trên cùng sẽ di chuyển ra ngoài. Nếu bạn di chuyển sang phải, thì các ô ở cột bên trái sẽ di chuyển ra ngoài. Trừ khi, tất nhiên, họ bị chặn di chuyển như mô tả ở trên. Dù bằng cách nào, bạn sẽ phải dành các bước di chuyển để làm lại hàng trên cùng hoặc cột bên trái. Những gì người ta có thể làm là ưu tiên giữa việc di chuyển xuống hoặc sang phải, ví dụ, chỉ di chuyển sang phải nếu không thể di chuyển khác.
∴ Nói chung, bạn nên di chuyển theo hai hướng đẩy viên gạch lớn nhất vào góc mà nó đang ở. Cố gắng sắp xếp các ô được sắp xếp theo kích thước số lượng của chúng. Điền cột bên trái để bạn có tùy chọn di chuyển theo hướng thứ ba mà không cần di chuyển ô góc. Nếu bạn phải di chuyển theo hướng thứ tư (trong ví dụ của chúng tôi, sang phải) thì sẽ rất vui khi có hàng trên cùng được lấp đầy để giữ giá trị tối đa ở góc.
Độ khó của trò chơiBạn có thể ngạc nhiên rằng một số chiến lược ngẫu nhiên khá hiệu quả. Ví dụ: nếu bạn lặp lại di chuyển Trái, Lên, Phải, Xuống,.. Sau đó, bạn sẽ có xu hướng nhận được 256 trước khi trò chơi kết thúc và đôi khi bạn sẽ nhận được 512 trước khi trò chơi kết thúc. Mặt khác, lặp lại Trái, Phải càng lâu càng tốt, sau đó Lên, Xuống càng lâu càng tốt, v.v. sẽ đạt điểm trung bình thấp hơn.
Tuy nhiên, bất kỳ chiến lược nào như vậy hầu như sẽ không bao giờ có được 1024 và gần như chắc chắn sẽ không bao giờ có được năm 2048. Vẫn tốt khi có một kế hoạch trò chơi cụ thể, ngay cả khi may mắn là một phần của trò chơi.
Khi bạn có được kinh nghiệm, bạn sẽ học cách suy nghĩ 2, 3 hoặc thậm chí 4 bước đi trước. Ví dụ: nếu hai hàng trên cùng là
128 64 32 4 □ □ 2 32 thì kế hoạch có thể là thay thế Trái + Phải cho đến khi có một số mới ở bên phải của 32
ở hàng thứ 2 và sau đó thực hiện Phải + Lên + Trái + Trái để hợp nhất 32s,
Những năm 64 và 128.
2048 bắt đầu dễ dàng, nhưng trở nên khó khăn rất nhanh. Đạt được 512 chỉ là một phần tư chặng đường đến gạch 2048, và nó chỉ trở nên khó khăn hơn từ đó. Hãy tiếp tục cố gắng! Bạn sẽ tự mình tìm thấy các chuỗi di chuyển hữu ích.
Tuy nhiên, bất kỳ chiến lược nào như vậy hầu như sẽ không bao giờ có được 1024 và gần như chắc chắn sẽ không bao giờ có được năm 2048. Vẫn tốt khi có một kế hoạch trò chơi cụ thể, ngay cả khi may mắn là một phần của trò chơi.
Khi bạn có được kinh nghiệm, bạn sẽ học cách suy nghĩ 2, 3 hoặc thậm chí 4 bước đi trước. Ví dụ: nếu hai hàng trên cùng là
128 64 32 4 □ □ 2 32 thì kế hoạch có thể là thay thế Trái + Phải cho đến khi có một số mới ở bên phải của 32
ở hàng thứ 2 và sau đó thực hiện Phải + Lên + Trái + Trái để hợp nhất 32s,
Những năm 64 và 128.
2048 bắt đầu dễ dàng, nhưng trở nên khó khăn rất nhanh. Đạt được 512 chỉ là một phần tư chặng đường đến gạch 2048, và nó chỉ trở nên khó khăn hơn từ đó. Hãy tiếp tục cố gắng! Bạn sẽ tự mình tìm thấy các chuỗi di chuyển hữu ích.
Thuật toánPhần này dành cho những sinh viên có nền tảng về mã hóa hoặc quan tâm đến việc trở thành nhà phát triển mã. Nó là kỹ thuật và chứa các chi tiết về các thuật toán không được dạy ở trường trung học nhưng nên dễ hiểu đối với bất kỳ ai quan tâm.
Với mức độ đơn giản về mặt cơ học của 2048, không có gì ngạc nhiên khi một số nhà phát triển đã viết AI (Trí tuệ nhân tạo) của riêng họ để chơi trò chơi.
Trong phần này, chúng tôi sẽ nói về một số chương trình và phương pháp để triển khai AI 2048 của riêng bạn.
Với mức độ đơn giản về mặt cơ học của 2048, không có gì ngạc nhiên khi một số nhà phát triển đã viết AI (Trí tuệ nhân tạo) của riêng họ để chơi trò chơi.
Trong phần này, chúng tôi sẽ nói về một số chương trình và phương pháp để triển khai AI 2048 của riêng bạn.
Một số chiến lược đơn giản là gì?Trong phần 'Độ khó của trò chơi' trong 'Chiến lược' ở trên, chúng tôi đã phác thảo một thuật toán chỉ đơn giản là di chuyển theo cùng một trình tự, 'trái, phải, lên, xuống' lặp đi lặp lại.
Làm thế nào bạn có thể viết chiến lược này bằng mã giả?
Việc triển khai mã giả có thể trông như thế này: họ phông chữm = 0 trong khi trò chơi chưa kết thúc:
đầu ra [trái, lên, phải, xuống] [m]
m = (m + 1) modulo 4 trong đó mục nhập thứ (m-1) của danh sách 4 hướng là đầu ra và m chu kỳ từ 0
đến 3. Điều này đặt ra một câu hỏi thú vị: có thuật toán 'đơn giản' nào khác có thể đạt được kết quả tốt hơn thuật toán này không?
Bạn có thể thử một cái gì đó như xen kẽ Lên và Xuống cho đến khi không thể di chuyển, sau đó sang Trái và Phải cho đến khi không thể di chuyển, v.v. Điều này có xu hướng mang lại điểm số tồi tệ hơn đáng kể. Hãy thử nó!
Cố gắng 'xấp xỉ' phần chiến lược bằng cách lặp lại 'di chuyển sang trái và lên cho đến khi không thể di chuyển, sau đó di chuyển sang phải và lên' không đạt được kết quả khác biệt đáng kể so với chiến lược đầu tiên của chúng tôi.
Tất cả các chiến lược đơn giản này không tính đến trạng thái của hội đồng quản trị. Để có được kết quả tốt hơn, chúng ta cần xây dựng một chương trình phức tạp hơn mà không di chuyển một cách vô mục đích độc lập với bố cục bảng. Một chương trình như vậy sẽ đủ điều kiện để được gọi là AI (Trí tuệ nhân tạo), được định nghĩa là một thiết bị có khả năng nhận biết môi trường và thực hiện các hành động để đạt được mục tiêu.
Làm thế nào bạn có thể viết chiến lược này bằng mã giả?
Việc triển khai mã giả có thể trông như thế này: họ phông chữ
đầu ra [trái, lên, phải, xuống] [m]
m = (m + 1) modulo 4 trong đó mục nhập thứ (m-1) của danh sách 4 hướng là đầu ra và m chu kỳ từ 0
đến 3. Điều này đặt ra một câu hỏi thú vị: có thuật toán 'đơn giản' nào khác có thể đạt được kết quả tốt hơn thuật toán này không?
Bạn có thể thử một cái gì đó như xen kẽ Lên và Xuống cho đến khi không thể di chuyển, sau đó sang Trái và Phải cho đến khi không thể di chuyển, v.v. Điều này có xu hướng mang lại điểm số tồi tệ hơn đáng kể. Hãy thử nó!
Cố gắng 'xấp xỉ' phần chiến lược bằng cách lặp lại 'di chuyển sang trái và lên cho đến khi không thể di chuyển, sau đó di chuyển sang phải và lên' không đạt được kết quả khác biệt đáng kể so với chiến lược đầu tiên của chúng tôi.
Tất cả các chiến lược đơn giản này không tính đến trạng thái của hội đồng quản trị. Để có được kết quả tốt hơn, chúng ta cần xây dựng một chương trình phức tạp hơn mà không di chuyển một cách vô mục đích độc lập với bố cục bảng. Một chương trình như vậy sẽ đủ điều kiện để được gọi là AI (Trí tuệ nhân tạo), được định nghĩa là một thiết bị có khả năng nhận biết môi trường và thực hiện các hành động để đạt được mục tiêu.
Bố cục của AI Một số đặc điểm của 2048 được chia sẻ bởi các trò chơi hội đồng khác là gì?- Bảng 2048 là một không gian trạng thái rời rạc, có nghĩa là có một số lượng hữu hạn các bố cục bảng có thể được kết nối với nhau thông qua các di chuyển có thể và các thế hệ ngẫu nhiên.
- Ngoài sự ngẫu nhiên, 2048 là một trò chơi thông tin hoàn hảo, có nghĩa là không có gì về những gì đã xảy ra hoặc đang xảy ra được ẩn khỏi người chơi. Để đưa ra một số ví dụ khác, cờ vua là một trò chơi thông tin hoàn hảo (vì cả hai người chơi có thể nhìn thấy tất cả các quân cờ và tất cả các nước đi được chơi), nhưng poker thì không (vì không người chơi nào có thể nhìn thấy thẻ của người kia). Lưu ý rằng một trò chơi thông tin hoàn hảo không bao gồm kiến thức về những gì sẽ xảy ra. Một trò chơi như vậy sẽ được gọi là một trò chơi thông tin hoàn chỉnh.
- 2048 là một trò chơi theo lượt. Trò chơi được phân chia thành các bước di chuyển, và người chơi có nhiều thời gian như họ muốn để phân tích và thực hiện một bước di chuyển.
Các đặc điểm của 2048 được chia sẻ bởi các trò chơi phổ biến khác, như cờ vua và cờ vây, vì vậy chúng ta có thể lấy ý tưởng từ AI cho các trò chơi đó.
Có nhiều cách để xây dựng AI cho các trò chơi như cờ vua, từ mạng thần kinh đến số lượng lớn tính toán ngoại tuyến. Giải thích tất cả sẽ mở rộng cuộc thảo luận về Thực phẩm cho Tư tưởng này thành một cuốn tiểu thuyết đầy đủ.
Sự khác biệt chính giữa các trò chơi này và năm 2048 là năm 2048 có yếu tố ngẫu nhiên. Trong trò chơi 2048, một người chơi cố gắng chơi tối ưu với máy tính chơi ngẫu nhiên. Nếu cả hai đều cố gắng chơi tối ưu thì người ta có thể sử dụng một kỹ thuật tìm kiếm được gọi là tìm kiếm minimax để xác định nước đi tiếp theo tốt nhất.
Có nhiều cách để xây dựng AI cho các trò chơi như cờ vua, từ mạng thần kinh đến số lượng lớn tính toán ngoại tuyến. Giải thích tất cả sẽ mở rộng cuộc thảo luận về Thực phẩm cho Tư tưởng này thành một cuốn tiểu thuyết đầy đủ.
Sự khác biệt chính giữa các trò chơi này và năm 2048 là năm 2048 có yếu tố ngẫu nhiên. Trong trò chơi 2048, một người chơi cố gắng chơi tối ưu với máy tính chơi ngẫu nhiên. Nếu cả hai đều cố gắng chơi tối ưu thì người ta có thể sử dụng một kỹ thuật tìm kiếm được gọi là tìm kiếm minimax để xác định nước đi tiếp theo tốt nhất.
Tìm kiếm Minimax tiêu chuẩnTrong tìm kiếm minimax, sau mỗi lần di chuyển mà người chơi thực hiện, tất cả các bước di chuyển của đối thủ có thể được điều tra, v.v., tức là cây đầy đủ các chuỗi di chuyển có thể được phát qua.
Một cái cây như vậy phát nổ về kích thước khi người ta tìm kiếm sâu hơn. Do đó, người ta giới thiệu độ sâu tìm kiếm tối đa, tức là, mỗi chuỗi được dừng lại ở độ sâu tìm kiếm tối đa, trừ khi trình tự đã kết thúc trước khi đạt đến độ sâu đó.
Nếu trò chơi đã kết thúc, thì kết quả trò chơi của chuỗi này được biết đến, nếu không, nếu trình tự được dừng lại ở độ sâu nghiên cứu tối đa thì kết quả phải được ước tính. Ước tính này có một số không chính xác không thể tránh khỏi.
Dựa trên những kết quả này, mỗi người chơi xác định nước đi tốt nhất vào những thời điểm sớm hơn liên tiếp. Chiêu thức tốt nhất là giảm thiểu tối ưu mà đối thủ có thể tiếp cận sau nước đi đó. Từ minimax là viết tắt của việc giảm thiểu kết quả tối đa mà đối thủ có thể đạt được sau khi di chuyển của chính mình.
Chúng ta hãy giả sử rằng tôi là một người chơi, và đối với một vị trí hội đồng quản trị nhất định, một trong những nước đi có thể của tôi đã được điều tra đầy đủ: Do đó, tôi biết đối thủ có thể đạt được vị trí tốt như thế nào sau nước đi đó. Nếu rõ ràng mà không cần tìm kiếm thêm rằng một nước đi tiềm năng là xấu, tức là, nó sẽ có lợi cho đối thủ của tôi nhiều hơn những nước đi tốt nhất mà tôi đã điều tra cho đến nay, thì nước đi này và toàn bộ cây di chuyển tiếp theo từ vị trí kết quả có thể bị bỏ qua. Do đó, không có thời gian hoặc công sức lãng phí để điều tra những gì được biết là một động thái bất lợi và các nhánh của nó. Thay vào đó, việc tiết kiệm thời gian và công sức có thể được áp dụng để điều tra thêm về những cây di chuyển có lợi.
Kỹ thuật này được gọi là cắt tỉa alpha-beta. Nó dẫn đến một cây tìm kiếm mỏng hơn, do đó có thể được tìm kiếm sâu hơn với cùng một nỗ lực để tránh các ước tính không chính xác ở độ sâu tìm kiếm tối đa và được thay thế bằng kết quả chính xác hơn từ các tìm kiếm.
Để quyết định xem một động thái có thể là tốt hay xấu mà không cần tìm kiếm, người ta sử dụng các ước tính được gọi là heuristics. Các heuristics càng đáng tin cậy, người ta càng có thể cắt tỉa cây tìm kiếm.
Một cái cây như vậy phát nổ về kích thước khi người ta tìm kiếm sâu hơn. Do đó, người ta giới thiệu độ sâu tìm kiếm tối đa, tức là, mỗi chuỗi được dừng lại ở độ sâu tìm kiếm tối đa, trừ khi trình tự đã kết thúc trước khi đạt đến độ sâu đó.
Nếu trò chơi đã kết thúc, thì kết quả trò chơi của chuỗi này được biết đến, nếu không, nếu trình tự được dừng lại ở độ sâu nghiên cứu tối đa thì kết quả phải được ước tính. Ước tính này có một số không chính xác không thể tránh khỏi.
Dựa trên những kết quả này, mỗi người chơi xác định nước đi tốt nhất vào những thời điểm sớm hơn liên tiếp. Chiêu thức tốt nhất là giảm thiểu tối ưu mà đối thủ có thể tiếp cận sau nước đi đó. Từ minimax là viết tắt của việc giảm thiểu kết quả tối đa mà đối thủ có thể đạt được sau khi di chuyển của chính mình.
Chúng ta hãy giả sử rằng tôi là một người chơi, và đối với một vị trí hội đồng quản trị nhất định, một trong những nước đi có thể của tôi đã được điều tra đầy đủ: Do đó, tôi biết đối thủ có thể đạt được vị trí tốt như thế nào sau nước đi đó. Nếu rõ ràng mà không cần tìm kiếm thêm rằng một nước đi tiềm năng là xấu, tức là, nó sẽ có lợi cho đối thủ của tôi nhiều hơn những nước đi tốt nhất mà tôi đã điều tra cho đến nay, thì nước đi này và toàn bộ cây di chuyển tiếp theo từ vị trí kết quả có thể bị bỏ qua. Do đó, không có thời gian hoặc công sức lãng phí để điều tra những gì được biết là một động thái bất lợi và các nhánh của nó. Thay vào đó, việc tiết kiệm thời gian và công sức có thể được áp dụng để điều tra thêm về những cây di chuyển có lợi.
Kỹ thuật này được gọi là cắt tỉa alpha-beta. Nó dẫn đến một cây tìm kiếm mỏng hơn, do đó có thể được tìm kiếm sâu hơn với cùng một nỗ lực để tránh các ước tính không chính xác ở độ sâu tìm kiếm tối đa và được thay thế bằng kết quả chính xác hơn từ các tìm kiếm.
Để quyết định xem một động thái có thể là tốt hay xấu mà không cần tìm kiếm, người ta sử dụng các ước tính được gọi là heuristics. Các heuristics càng đáng tin cậy, người ta càng có thể cắt tỉa cây tìm kiếm.
Tìm kiếm Minimax cho năm 2048Một tìm kiếm minimax tiêu chuẩn giả định rằng cả hai người chơi đều chơi tối ưu. Tuy nhiên, vào năm 2048, một trong những người chơi, máy tính, chơi ngẫu nhiên.
Phiên bản đầu tiên của một trình phát máy tính để thực hiện sẽ chỉ sử dụng heuristics để quyết định di chuyển mà không thực hiện bất kỳ tìm kiếm nào.
Phiên bản thứ hai có thể thực hiện tìm kiếm minimax tiêu chuẩn và do đó giả định chơi máy tính thông minh (ví dụ, trong đó di chuyển máy tính tốt nhất có thể là đặt một số vào góc ngay lập tức nếu ô lớn nhất di chuyển ra khỏi góc).
Sau đó, người ta có thể thử nghiệm với tìm kiếm minimax trong đó người chơi di chuyển tốt nhất giảm thiểu không phải thiệt hại tối đa có thể có của vị trí ngẫu nhiên máy tính mà thay vào đó là một số loại thiệt hại trung bình của vị trí ngẫu nhiên máy tính tiếp theo.
Trong mọi trường hợp, trước tiên người ta sẽ bắt đầu làm việc trên một heuristic cho các bước di chuyển của người chơi tốt bởi vì điều đó có lợi cho bất kỳ người chơi máy tính nào.
Phiên bản đầu tiên của một trình phát máy tính để thực hiện sẽ chỉ sử dụng heuristics để quyết định di chuyển mà không thực hiện bất kỳ tìm kiếm nào.
Phiên bản thứ hai có thể thực hiện tìm kiếm minimax tiêu chuẩn và do đó giả định chơi máy tính thông minh (ví dụ, trong đó di chuyển máy tính tốt nhất có thể là đặt một số vào góc ngay lập tức nếu ô lớn nhất di chuyển ra khỏi góc).
Sau đó, người ta có thể thử nghiệm với tìm kiếm minimax trong đó người chơi di chuyển tốt nhất giảm thiểu không phải thiệt hại tối đa có thể có của vị trí ngẫu nhiên máy tính mà thay vào đó là một số loại thiệt hại trung bình của vị trí ngẫu nhiên máy tính tiếp theo.
Trong mọi trường hợp, trước tiên người ta sẽ bắt đầu làm việc trên một heuristic cho các bước di chuyển của người chơi tốt bởi vì điều đó có lợi cho bất kỳ người chơi máy tính nào.
Các tìm kiếm như vậy được thực hiện hiệu quả hơn bởi Heuristics, mà chúng ta sẽ thảo luận trong phần tiếp theo.
HeuristicsPhỏng đoán là gì?
Một heuristic là một phỏng đoán có giáo dục chưa được chứng minh về những gì cần làm tiếp theo, giống như một 'quy tắc ngón tay cái'. Ví dụ, 'heuristic khan hiếm', xu hướng mọi người gán giá trị cao cho các mặt hàng hiếm, là một heuristic. Đó là một phương pháp cố gắng đoán giá của một mặt hàng. Nó không hoàn hảo (ví dụ: nhiều thứ hiếm mà không có giá trị: DNA của bạn có thể độc nhất vô nhị nhưng không chắc nhiều người muốn mua nó), nhưng nó là một công cụ ước tính đủ tốt cho nhiều đối tượng.
Heuristics xuất hiện trong mã hóa mọi lúc. Đối với trường hợp này, chúng tôi sẽ sử dụng heuristics để ước tính mức độ 'tốt' của bố cục bảng.
Gán một giá trị cho bố cục bảng biểu thị mức độ 'tốt' của nó; số cao hơn có nghĩa là bố cục 'tốt hơn' và số thấp hơn có nghĩa là bố cục 'tệ hơn'. Chúng tôi không có cách nào để tính toán chính xác bố cục bảng 'tốt' như thế nào, nhưng chúng tôi có thể sử dụng một số phỏng đoán để giúp quyết định bước đi tiếp theo của chúng tôi. Cố gắng nghĩ về một số phỏng đoán có thể xảy ra để quyết định xem bố cục bảng có 'tốt' hay không trước khi tiếp tục.
Một heuristic là một phỏng đoán có giáo dục chưa được chứng minh về những gì cần làm tiếp theo, giống như một 'quy tắc ngón tay cái'. Ví dụ, 'heuristic khan hiếm', xu hướng mọi người gán giá trị cao cho các mặt hàng hiếm, là một heuristic. Đó là một phương pháp cố gắng đoán giá của một mặt hàng. Nó không hoàn hảo (ví dụ: nhiều thứ hiếm mà không có giá trị: DNA của bạn có thể độc nhất vô nhị nhưng không chắc nhiều người muốn mua nó), nhưng nó là một công cụ ước tính đủ tốt cho nhiều đối tượng.
Heuristics xuất hiện trong mã hóa mọi lúc. Đối với trường hợp này, chúng tôi sẽ sử dụng heuristics để ước tính mức độ 'tốt' của bố cục bảng.
Gán một giá trị cho bố cục bảng biểu thị mức độ 'tốt' của nó; số cao hơn có nghĩa là bố cục 'tốt hơn' và số thấp hơn có nghĩa là bố cục 'tệ hơn'. Chúng tôi không có cách nào để tính toán chính xác bố cục bảng 'tốt' như thế nào, nhưng chúng tôi có thể sử dụng một số phỏng đoán để giúp quyết định bước đi tiếp theo của chúng tôi. Cố gắng nghĩ về một số phỏng đoán có thể xảy ra để quyết định xem bố cục bảng có 'tốt' hay không trước khi tiếp tục.
Ví dụ về Heuristics cho năm 2048 Gạch miễn phíNếu có ít ô miễn phí □ trên bảng, thì các tùy chọn của bạn trở nên rất hạn chế. Do đó, một giá trị cao hơn có thể được trao cho các bảng có nhiều điểm mở hơn.
Một phiên bản cải tiến cũng sẽ ước tính cơ hội cho các ô bị chiếm đóng hợp nhất với một ô lân cận bằng một nửa giá trị tùy thuộc vào xác suất mà hàng xóm này có thể được hợp nhất, v.v. Ước tính như vậy sẽ bắt đầu với các ô có giá trị 2 hoặc 4 nằm bên cạnh các ô miễn phí.
Một phiên bản cải tiến cũng sẽ ước tính cơ hội cho các ô bị chiếm đóng hợp nhất với một ô lân cận bằng một nửa giá trị tùy thuộc vào xác suất mà hàng xóm này có thể được hợp nhất, v.v. Ước tính như vậy sẽ bắt đầu với các ô có giá trị 2 hoặc 4 nằm bên cạnh các ô miễn phí.
Hợp nhất tiềm năngNếu có nhiều ô bằng nhau liền kề, thì một số lượng lớn các hợp nhất có thể diễn ra, dẫn đến một số lượng lớn các ô miễn phí và do đó có nhiều lựa chọn hơn. Do đó, một giá trị cao hơn có thể được trao cho các bảng có nhiều hợp nhất tiềm năng. Cũng nên xem xét rằng nếu bạn di chuyển theo một hướng, thì các hợp nhất tiềm năng theo hướng vuông góc rất có thể sẽ biến mất, vì vậy cần phải nỗ lực để tính đến khả năng đó.
Đối thủHeuristic này đối xử với thế hệ ngẫu nhiên như một người chơi thứ hai thù địch. Đó là, nó sẽ giả định việc tạo ngẫu nhiên sẽ luôn dẫn đến kết quả tồi tệ nhất có thể xảy ra, và do đó các giá trị cao hơn có thể được trao cho các bảng để giảm thiểu rủi ro kết quả xấu.
MonotonicityDãy đơn điệu là một chuỗi các số trong đó mỗi số lớn hơn hoặc bằng tất cả các số trước đó (tăng đơn điệu) hoặc mỗi số nhỏ hơn hoặc bằng tất cả các số trước đó (giảm đơn điệu). Ví dụ, 1,1,1,2,3 và 3,2,1,1,1 là đơn điệu tăng và đơn điệu giảm tương ứng nhưng 1,1,1,2,1 không đơn điệu. Chúng ta có thể gán các giá trị cao hơn cho bố cục bảng đơn điệu tăng hoặc gần với đơn điệu tăng về phía một góc, tức là một ô gần góc đó lớn hơn hoặc bằng tất cả các ô ở xa góc đó. Đây là một mô phỏng của chiến lược được thảo luận trong phần trước, trong đó trọng tâm là giữ ô lớn nhất ở một góc và tất cả các ô lớn khác tập trung xung quanh góc đó.
Làm mịnBất kỳ 2 ô lân cận nào không có giá trị bằng nhau đều gây ra chi phí vì chúng chiếm không gian cần thiết để di chuyển các ô xung quanh và hợp nhất chúng.
Chi phí này cao hơn nếu các ô rất khác nhau với ít cơ hội được hợp nhất trong tương lai. Heuristic đơn giản sau đây dễ dàng tổng hợp tất cả các 'chi phí' hoặc heuristic tiêu cực này. Trên bảng M×N (có hàng M và cột N), có quan hệ lân cận N−1 trong mỗi hàng và M−1 quan
hệ như vậy trong mỗi cột, do đó, tổng cộng (M × (N−1)) + (N × (M−1)) = 2MN − M − N dấu phân cách giữa các ô lân cận. Chúng tôi đính kèm một heuristic âm (tức là chi phí) cho mỗi một trong số chúng, đó là thước đo số lần hợp nhất cần thiết để số nhỏ hơn của cả hai số trở nên bằng với số lớn hơn. Nói cách khác, chúng ta đếm số yếu tố của 2 phân tách cả hai. Tương đương, nhưng nói một cách chính thức hơn, nếu chúng ta để A bằng giá trị của ô nhỏ hơn và B bằng giá trị của ô lớn hơn, chúng ta lấy nhật ký2 (A / B) làm chi phí, tức là đây sẽ là điểm âm.
Chi phí này cao hơn nếu các ô rất khác nhau với ít cơ hội được hợp nhất trong tương lai. Heuristic đơn giản sau đây dễ dàng tổng hợp tất cả các 'chi phí' hoặc heuristic tiêu cực này. Trên bảng M×N (có hàng M và cột N), có quan hệ lân cận N−1 trong mỗi hàng và M−1 quan
hệ như vậy trong mỗi cột, do đó, tổng cộng (M × (N−1)) + (N × (M−1)) = 2MN − M − N dấu phân cách giữa các ô lân cận. Chúng tôi đính kèm một heuristic âm (tức là chi phí) cho mỗi một trong số chúng, đó là thước đo số lần hợp nhất cần thiết để số nhỏ hơn của cả hai số trở nên bằng với số lớn hơn. Nói cách khác, chúng ta đếm số yếu tố của 2 phân tách cả hai. Tương đương, nhưng nói một cách chính thức hơn, nếu chúng ta để A bằng giá trị của ô nhỏ hơn và B bằng giá trị của ô lớn hơn, chúng ta lấy nhật ký2 (A / B) làm chi phí, tức là đây sẽ là điểm âm.
Đây không phải là những phương pháp phỏng đoán duy nhất có sẵn, nhưng vẫn là thức ăn tốt cho suy nghĩ.
Nếu heuristics đáng tin cậy hơn thì chúng có thể được sử dụng để chọn lọc hơn trong đó các động thái sẽ được nghiên cứu thêm. Đối với một số trò chơi, heuristics thay đổi từ đầu trò chơi sang trò chơi giữa và trò chơi kết thúc. Nếu heuristics rất không đáng tin cậy thì người ta có thể mô phỏng nhiều trò chơi từ vị trí đến cuối và sử dụng số liệu thống kê để đánh giá nước đi nào có vẻ tốt hơn và lần lượt điều tra chúng nhiều hơn. Nhưng những chiến lược như vậy phù hợp hơn cho các trò chơi có bảng lớn hơn, không phải cho năm 2048.
Nếu bạn quan tâm đến việc viết AI 2048 của riêng mình, bạn có thể truy cập vấn đề tương tác của chúng tôi tại cariboutests.com/judge.
Tính chất toán học &; Chứng minhPhần này dành cho những sinh viên quan tâm đến toán học mới. Chúng tôi giới thiệu các khái niệm được tìm thấy trong các khóa học toán đại học. Phần này dành cho học sinh trung học hoặc học sinh trung học cơ sở quan tâm.
Mặc dù 2048 là một trò chơi arcade thú vị, nhưng cũng có một số chi tiết về nó có thể được chứng minh là đúng thông qua các phương pháp toán học. Tuy nhiên, để làm điều đó, chúng ta sẽ cần một số công cụ, đáng chú ý nhất trong số đó được gọi là bất biến.
Mặc dù 2048 là một trò chơi arcade thú vị, nhưng cũng có một số chi tiết về nó có thể được chứng minh là đúng thông qua các phương pháp toán học. Tuy nhiên, để làm điều đó, chúng ta sẽ cần một số công cụ, đáng chú ý nhất trong số đó được gọi là bất biến.
Bất biếnBất biến là một thuộc tính của một đối tượng không thay đổi khi các hoạt động nhất định được thực hiện với đối tượng đó.
Ví dụMột số chẵn không để lại phần dư khi được chia cho 2 (chẳng hạn như .. −2,0,2,4,6,..) và một số lẻ để lại phần dư 1 khi được chia cho 2 (chẳng hạn như .. −1,1,3,5,..). Cộng hoặc trừ 2 cho một số chẵn sẽ cho một số chẵn và cộng hoặc trừ 2 cho một số lẻ sẽ cho một số lẻ. Do đó, phép toán cộng hoặc trừ 2 không làm thay đổi tính chất là số chẵn hoặc số lẻ.
Tính chất của một số chẵn hoặc lẻ còn được gọi là Chẵn lẻ của nó. Do đó, chúng ta có thể nói, chẵn lẻ của một số là một bất biến dưới phép cộng/trừ 2. Cộng hoặc trừ 2 lần nhiều lần vẫn không làm thay đổi tính chẵn lẻ. Do đó:∴
Chẵn lẻ của một số là một bất biến dưới phép cộng và trừ của bất kỳ số chẵn nào.
Tính chất của một số chẵn hoặc lẻ còn được gọi là Chẵn lẻ của nó. Do đó, chúng ta có thể nói, chẵn lẻ của một số là một bất biến dưới phép cộng/trừ 2. Cộng hoặc trừ 2 lần nhiều lần vẫn không làm thay đổi tính chẵn lẻ. Do đó:∴
Chẵn lẻ của một số là một bất biến dưới phép cộng và trừ của bất kỳ số chẵn nào.
Một bất biến (chẳng hạn như Chẵn lẻ) của một phép toán nhất định (chẳng hạn như cộng/trừ một số chẵn) rất hữu ích để chứng minh rằng một đối tượng (chẳng hạn như một số) có một giá trị bất biến (chẳng hạn như chẵn) không thể được chuyển đổi thành một đối tượng khác (chẳng hạn như một số khác) với một giá trị bất biến khác (chẳng hạn như lẻ) theo một loại phép toán như vậy (trong trường hợp này, cộng/trừ của một số chẵn).
Bất biến có thể có vô số dạng trong toán học. Một số trong những cái đáng chú ý nhất là bất biến nút thắt. Trước khi bất biến nút thắt được phát hiện vào những năm 1920, các nhà toán học không thể chứng minh rằng bất kỳ hai nút thắt nào khác nhau (tức là không thể biến dạng thành nhau), hoặc khác biệt ngay cả từ một vòng lặp đơn giản!
Nếu bạn tò mò về các nút thắt và tính chất của chúng, trò chơi Unknotting game của chúng tôi là một nơi tốt để bắt đầu.
Bất biến có thể có vô số dạng trong toán học. Một số trong những cái đáng chú ý nhất là bất biến nút thắt. Trước khi bất biến nút thắt được phát hiện vào những năm 1920, các nhà toán học không thể chứng minh rằng bất kỳ hai nút thắt nào khác nhau (tức là không thể biến dạng thành nhau), hoặc khác biệt ngay cả từ một vòng lặp đơn giản!
Nếu bạn tò mò về các nút thắt và tính chất của chúng, trò chơi Unknotting game của chúng tôi là một nơi tốt để bắt đầu.
Theo hoạt động thực hiện các nước đi trong trò chơi 2048, sau đây là những bất biến:
Lemma 1: Số của một ô sẽ luôn là lũy thừa của 2.- Nếu hai ô có lũy thừa bằng nhau của 2 hợp nhất, thì kết quả sẽ là lũy thừa tiếp theo của 2.
- Tất cả các ô được tạo bắt đầu bằng 2 hoặc 4, là lũy thừa của 2.
- Do đó, theo nguyên tắc quy nạp toán học, tất cả các số của gạch đều là lũy thừa của 2.
Lemma 2: Trong một động thái, tổng của tất cả các số ô chỉ thay đổi thông qua việc tạo ngẫu nhiên của ô mới.- Nếu không có ô nào hợp nhất, thì tổng được bảo toàn.
- Nếu bất kỳ hai ô nào hợp nhất, thì tổng vẫn được giữ nguyên vì ô kết quả có cùng tổng với hai ô ban đầu (như đánh giá việc cộng một số số).
- Do đó, vì tổng của các ô ban đầu luôn được giữ nguyên, tổng số tiền chỉ được thay đổi bằng cách tạo ra một ô mới có giá trị ngẫu nhiên.
Với những tính chất này, bây giờ chúng ta có thể chứng minh một số kết quả thú vị về năm 2048.
Thêm Lemma- Lemma: Cho N là số chẵnthứ n, tức là N = 2 n và để kích thước bảng đủ lớn để trò chơi có ít nhất n nước đi. Khi đó, xác suất tổng số trên các ô sẽ tại bất kỳ thời điểm nào trong trò chơi chính xác bằng N bằng (10 + (−1⁄10)n)/(11).
Bằng chứng- Vì tổng của tất cả các số ô không thay đổi khi phối, cách duy nhất để tổng tăng là tạo ô ngẫu nhiên. Do đó, sau bất kỳ lượt nào, tổng tăng thêm 2 với 90% cơ hội hoặc 4 với 10% cơ hội. Cho P(n) là xác suất mà
- tại một thời điểm nào đó trong trò chơi, tổng chính xác là N = 2n và Q(n) = 1 − P(n) là xác suất mà tổng sẽ không bao giờ bằng N.
- Khi bắt đầu trò chơi, tổng bằng 0 với xác suất 100%, tức là P (0) = 1 và Q (0) = 0.
- Khả năng duy nhất mà một số chẵn N không thể là tổng của tất cả các ô là N−2 xảy ra dưới dạng tổng (với xác suất 1−Q(n−1)) VÀ 4 được tạo ra (với xác suất 1⁄10). Do đó, xác suất là Q(n) = (1−Q(n−1))/(10) là quan hệ lặp lại tuyến tính 10 Q(n) + Q(n−1) = 1. Giải pháp tổng quát của quan hệ lặp lại tuyến tính không đồng nhất này (với 1 ở phía bên tay phải) bằng với nghiệm chung của phiên bản đồng nhất
- (với số 0 ở phía bên tay phải) cộng với một giải pháp cụ thể của phiên bản không đồng nhất.
- Nghiệm tổng quát của phiên bản đồng nhất 10 Q(n) + Q(n−1) = 0 là Q(n) = a(−1⁄10)n với a là một số tùy ý.
- Một nghiệm cụ thể của phiên bản không đồng nhất là Q(n) = 1/11 với mọi n vì 10(1/11) + 1/11 = 1.
- Hằng số a được xác định từ trường hợp n = 0: 0 = Q (0) = a (−1⁄10) 0 + 1/11 = a + 1/11 và do đó a = −1/11,
- thay thế a vào công thức cho Q cho Q(n) = 1/11 − 1/11(−1⁄1⁄1⁄10)n và do đó P(n) = 1 − Q(n) = ( 10
- + (−1⁄10)n )/(11). ■
- Lemma: Không thể đạt được một ô 262144 = 218.
Bằng chứng- Chúng tôi bắt đầu chứng minh bằng cách giả định ngược lại: rằng một số cấu hình bảng quản lý để có được một ô 262144 = 218. Sau đó,
- một nước đi trước đó, tổng phải là 2 18 − 4 hoặc 218 − 2. Nhưng 2 18 − 4
- mất tối thiểu 16 ô để biểu diễn (16 là số 1 trong biểu diễn nhị phân của 2 18 − 4 = 217 + 2 16+.. +23 + 22, và xuất hiện như là kết quả của số lượng gạch là lũy thừa của 2. Ví dụ, có hai ô có 16 thay vì một ô có 32 sẽ làm tăng số lượng gạch hơn nữa).
- 218 − 2 sẽ mất tối thiểu 17 ô để đại diện. Do đó, không thể vượt qua 2 18
- − 4 và do đó không thể đạt được 218 = 262144. ■
- Lemma: Để đạt được tổng gạch là 131072 = 2 17, ngoài may mắn đáng kinh ngạc để có thể hợp nhất đủ nhiều ô, có một may mắn cuối cùng là khoảng 1 trong11 cần thiết.
Bằng chứng- Như được hiển thị trước đây, tổng ô luôn tăng 2 hoặc 4 trong mỗi lần di chuyển do tạo ô ngẫu nhiên.
- Do đó, một nước đi trước khi tổng gạch đạt 2 17 nó phải là 2 17− 2 hoặc 217− 4.
- Theo lập luận trong chứng minh trước, số lượng ô tối thiểu đại diện cho 2 17− 2 là 16
- Số lượng ô tối đa trên bảng là 16, vì vậy nếu đạt được 217 − 2 thì chắc chắn sẽ không thể tiếp tục vì sẽ không có chỗ cho một ô mới xuất hiện và không thể hợp nhất do tính độc đáo của tất cả các ô trên bảng. Do đó,
- cách duy nhất để đạt được tổng ô là 217 là đạt được 2 17− 4 (lấy tối thiểu15 ô, chừa chỗ cho một ô khác xuất hiện), sau đó tạo ra 4. Xác suất đạt được
- bất kỳ tổng gạch chẵn nào đạt tới 10⁄11 và 4 được tạo ra với xác suất 1⁄10 cho tích 1⁄11 là cơ hội bỏ qua 2 17− 2 và cuối cùng đạt tổng gạch là 131072 = 2 17. ■
Theo dõi cập nhật sắp tới