TD-Gammon là chương trình backgammon tự học do Gerald Tesauro viết tại IBM. Tháng 10 năm 1991, Bill Robertie, người hai lần vô địch thế giới, ngồi đấu với nó và chỉ thắng sát nút. Gần hai mươi lăm năm trước khi AlphaGo hạ Lee Sedol, đây là một bước ngoặt của học tăng cường, nhưng sau đó lại bị cả ngành bỏ quên.

Tóm tắt nhanh

TD-Gammon bị quên không phải vì sai phương pháp. Nó tự chơi, tự sửa dự đoán và không cần thầy, đúng hướng mà AlphaGo dùng về sau. Nhưng nó thành công trên backgammon, một bàn cờ có xúc xắc nên rất dễ chịu với máy. Khi công thức được mang sang cờ vua và cờ vây, nó kém hẳn. Người ta kết luận đó là trường hợp đặc biệt, và ý tưởng phải đợi hơn hai thập kỷ mới được chứng minh lại.

Diễn biến chính

1949–1962: Arthur Samuel và giấc mơ máy tự học

Arthur Samuel vào IBM năm 1949 và dạy chiếc IBM 701 chơi cờ đam. Ông để máy ghi nhớ thế cờ, tự rút kinh nghiệm từ thắng thua, và gọi quá trình ấy là học máy. Năm 1962, chương trình của ông thắng một kiện tướng cờ đam.

Những trận về sau lúc được lúc mất. Các thử nghiệm máy tự chơi khác, như cỗ máy chơi cờ ca-rô bằng hộp diêm của Donald Michie, cũng sinh ra lối chơi kỳ quặc và dễ vỡ. Giới nghiên cứu dần bỏ hướng này.

1988–1989: Sutton và Neurogammon

Năm 1988, Richard Sutton, khi ấy ở phòng thí nghiệm GTE, công bố phương pháp sai khác theo thời gian. Ý chính: máy không cần đợi hết ván mới học mà sửa dự đoán trước đó bằng dự đoán sau đó. Cùng lúc, Tesauro viết Neurogammon, mạng nơ-ron học từ những nước đi do con người chấm điểm. Chương trình này vô địch Olympiad máy tính đầu tiên ở London năm 1989, nhưng chỉ ở mức khá và không thể giỏi hơn người dạy nó.

1990–1991: Tesauro cược vào cỗ máy không thầy

Tesauro học vật lý, lấy tiến sĩ tại Princeton, rồi đến Trung tâm nghiên cứu Watson của IBM. Ông dựng một mạng nơ-ron mới với trọng số ngẫu nhiên, chỉ nhìn bàn cờ ở dạng thô, rồi cho hai bản sao tự chơi. Sau hai trăm nghìn ván, bản đầu tiên chơi ngang Neurogammon.

Ở bản tiếp theo, ông ghép thêm các đặc điểm thế cờ của Neurogammon và cho máy tự chơi khoảng ba trăm nghìn ván trong một tháng. Bản này đấu Robertie 31 ván vào tháng 10 năm 1991. Cuối năm đó nó còn đấu Paul Magriel và Malcolm Davis, tổng 51 ván với ba đối thủ và chỉ lỗ ròng 13 điểm.

1992: máy dạy lại người

Với các lượt mở 2-1, 4-1 và 5-1, sách giáo khoa dạy đặt mồi. TD-Gammon chọn tách quân, một nước mà cao thủ coi là rụt rè. Phép chơi thử đến cùng, tức cho máy chơi tiếp thế cờ hàng nghìn lần với xúc xắc khác nhau, đứng về phía máy. Nước đặt mồi gần như biến mất khỏi các giải đấu. Kit Woolsey nhận rằng khả năng phán đoán thế cờ của máy vượt xa ông.

Năm 1992, tại World Cup backgammon, phiên bản có nhìn trước một lượt chơi 38 ván biểu diễn và chỉ lỗ ròng 7 điểm. Cùng năm, Tesauro đăng kết quả trên tạp chí Machine Learning.

1993: trận 40 ván với Robertie

Sau khi tự chơi khoảng một triệu rưỡi ván, một phiên bản mạnh hơn gặp lại Robertie. Ông bị dẫn gần suốt buổi và chỉ thắng một điểm ở ván cuối, tức hơn máy đúng một điểm sau 40 ván. Robertie ước tính máy chỉ kém những người giỏi nhất thế giới vài phần trăm điểm mỗi ván.

1995–2017: bị nghi ngờ rồi được minh oan

NeuroChess của Sebastian Thrun chỉ thắng khoảng 13% số ván trước một chương trình cờ vua miễn phí. Thử nghiệm ở cờ vây của nhóm có Sejnowski cũng chỉ đạt kết quả hạn chế. Trong khi đó, IBM giữ bộ trọng số làm bí mật thương mại và tháng 9 năm 1995 đưa TD-Gammon vào gói trò chơi đi kèm OS/2.

Năm 1998, Jordan Pollack và Alan Blair cho một mạng nhỏ bắt đầu từ trọng số bằng không và học bằng cách leo đồi. Nó thắng khoảng 40% số ván trước một chương trình chuẩn công khai, bản tốt nhất khoảng 45%. Họ cho rằng thành công nằm ở động lực của trò chơi chứ không ở thuật toán TD. Tháng 12 năm 2013, bài báo của DeepMind về Atari nhắc lại niềm tin rằng TD-Gammon là trường hợp đặc biệt nhờ xúc xắc, rồi làm điều ngược lại: máy vượt các phương pháp cũ ở sáu trong bảy trò và vượt người chơi giỏi ở ba trò. Năm 2016, AlphaGo hạ Lee Sedol, và năm sau AlphaGo Zero học từ con số không, nhắc TD-Gammon như một bậc tiền bối.

Điều còn tranh cãi hoặc cần thận trọng

  • Siêu phàm hay áp sát? Các trận được ghi lại chỉ cho thấy máy áp sát những người giỏi nhất. Tesauro chỉ nói nó gần ngang họ.
  • Không có tri thức con người? Điều này chỉ đúng với bản đầu tiên. Từ bản đấu Robertie trở đi, mạng được ghép thêm đặc điểm thế cờ do người thiết kế. Các con số về số ván tự chơi cũng thuộc những phiên bản khác nhau nên hay bị trích lẫn.
  • Phép màu nằm ở xúc xắc? Đây là giả thuyết của Pollack và Blair, và Tesauro phản bác ngay trong cùng số tạp chí. Ông cho rằng leo đồi chỉ học được phần thô của chiến lược.
  • Nước đi không bất tử. Khoảng năm 2006, các máy đời sau lại khuyên đặt mồi với lượt 2-1.
  • Nguồn thứ cấp. Trận 100 ván với Malcolm Davis năm 1998, trong đó máy thua 8 điểm vì một lần gấp đôi sai, chỉ được kể lại theo nguồn thứ cấp.

Vì sao câu chuyện này đáng nhớ?

TD-Gammon cho thấy một ý tưởng đúng có thể bị bỏ rơi vì nó xuất hiện quá sớm và trên một bàn cờ quá dễ chịu. Xúc xắc đã gánh phần việc khó: buộc máy khám phá, làm phép tính thắng thua trơn tru và không cho hai bản sao cùng chơi an toàn. Khi công thức thắng, người ta công cho trò chơi. Khi nó thua ở nơi khác, người ta lại đổ lỗi cho công thức.

Câu chuyện cũng nhắc rằng một kết luận phổ biến, như TD-Gammon chỉ là trường hợp đặc biệt, vẫn cần được kiểm chứng lại khi có thêm máy tính và dữ liệu. Về sau Tesauro ở lại IBM và lo chiến lược đặt cược cho Watson khi nó chơi Jeopardy!.

Câu hỏi thường gặp

TD-Gammon là gì?

Là chương trình chơi backgammon do Gerald Tesauro viết tại IBM. Nó tự học bằng cách đấu với chính mình và sửa dự đoán sau từng nước đi, dựa trên phương pháp sai khác theo thời gian của Richard Sutton.

TD-Gammon có đánh bại nhà vô địch thế giới không?

Không hẳn. Các trận được ghi lại cho thấy nó áp sát: năm 1991 Robertie thắng, năm 1992 máy lỗ ròng 7 điểm sau 38 ván, năm 1993 Robertie hơn đúng một điểm sau 40 ván. Cách nói máy hạ nhà vô địch là phóng đại.

TD-Gammon khác Neurogammon ở điểm nào?

Neurogammon học từ những nước đi do con người chấm điểm nên chỉ giỏi bằng người dạy. TD-Gammon bản đầu chỉ biết luật và kết quả thắng thua, rồi tự học qua các ván tự chơi.

Vì sao TD-Gammon bị lãng quên?

Công thức tương tự không cho kết quả tốt ở cờ vua, cờ vây, nên giới nghiên cứu cho rằng nó chỉ thành công nhờ xúc xắc. IBM còn giữ bộ trọng số làm bí mật thương mại và đưa phần mềm vào gói trò chơi của OS/2.

TD-Gammon liên quan gì đến AlphaGo?

Cùng tinh thần tự chơi và tự sửa dự đoán. Bài báo DeepMind năm 2013 nhắc lại niềm tin rằng TD-Gammon là trường hợp đặc biệt rồi phản bác nó. AlphaGo Zero về sau học từ con số không, và TD-Gammon được nhắc như một bậc tiền bối.

Nguồn tham khảo

  • G. Tesauro, Temporal Difference Learning and TD-Gammon, Communications of the ACM, 1995
  • J. B. Pollack và A. D. Blair, Co-Evolution in the Successful Learning of Backgammon Strategy, Machine Learning, 1998
  • Mnih và cộng sự, Playing Atari with Deep Reinforcement Learning, arXiv:1312.5602 (DeepMind, 2013)
  • IBM History: các trang về Arthur Samuel và TD-Gammon
  • Trang sách của Bill Robertie, Learning from the Machine, trên bkgm.com
  • Wikipedia: TD-Gammon, Neurogammon, Gerald Tesauro (nguồn thứ cấp)
  • chessprogramming.org: NeuroChess

Bài viết tóm tắt từ video của kênh; nội dung mang tính giới thiệu.