Hã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.

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.

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.

Trong 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 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.

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.

Phỏ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.

Đâ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.

Bấ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 đó.

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.

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.