Trận MoGo thắng Kim Myungwan ở Portland ngày 7/8/2008 là lần đầu một chương trình cờ vây thắng kỳ thủ chuyên nghiệp tám đẳng với mức chấp chín quân, và là mở đầu của cuộc đua máy chơi cờ vây bằng phương pháp Monte Carlo. Câu chuyện chạy từ Munich 1993 đến AlphaGo 2016. Nó đáng quan tâm vì cho thấy bước ngoặt của AlphaGo được dựng trên nền một ý tưởng mà từng có thời không ai coi trọng.

Tóm tắt nhanh

Trong ba mươi năm, máy chơi cờ vây yếu vì không ai viết nổi công thức chấm điểm thế cờ. Cách thoát ra là thôi chấm điểm: cho máy chơi ngẫu nhiên đến hết ván hàng nghìn lần, rồi chọn nước có tỷ lệ thắng tốt nhất. Hai chương trình Crazy Stone (Pháp, Lille) và MoGo (Pháp, Paris) đưa cách này lên bàn lớn, hạ mức chấp từ chín quân xuống bốn quân trước kỳ thủ chuyên nghiệp. AlphaGo về sau gắn mạng nơ-ron vào đúng bộ khung tìm kiếm ấy.

Diễn biến chính

Vì sao cờ vây khó với máy (1997 trở đi)

Tháng 5/1997, Deep Blue của IBM thắng Garry Kasparov ở cờ vua, nhưng cờ vây vẫn được xem là pháo đài chưa ai hạ được. Theo bảng của Coulom, số thế cờ vua vào khoảng 10^50, còn cờ vây khoảng 10^171. Cái khó hơn là không có hàm đánh giá: một quân cờ vây không có giá cố định như quân hậu hay quân xe. Cách làm truyền thống (alpha-beta cùng hàm đánh giá) được chính Coulom nhận xét là đã thất bại với cờ vây.

Munich, 1993: ý tưởng "chơi bừa"

Nhà vật lý Bernd Brügmann ở Viện Max Planck viết chương trình Gobble, chọn nước đi bằng cách chơi ngẫu nhiên hàng nghìn ván rồi lấy kết quả trung bình. Chính ông viết rằng cách này nghe có vẻ lố bịch. Gobble chỉ ở trình khoảng 25 kyu (người mới học) trên bàn 9×9, và bài viết lúc đó không được coi trọng. Ý tưởng chỉ còn sống lay lắt ở nhóm nghiên cứu Paris.

2005–2006: Crazy Stone, UCT và MoGo

Từ tháng 7/2005, Rémi Coulom viết Crazy Stone và đặt tên cho cách làm là tìm kiếm cây Monte Carlo: giữ một cái cây trong bộ nhớ và dồn thêm ván thử vào các nhánh hứa hẹn. Ngày 29/5/2006, Crazy Stone đoạt vàng bàn 9×9 tại Olympiad máy tính ở Turin. Cùng năm, Kocsis và Szepesvári công bố công thức UCT, lấy ý từ bài toán chọn máy đánh bạc. Nhóm của Sylvain Gelly và Olivier Teytaud ghép các ý tưởng đó thành MoGo, chương trình UCT đầu tiên, đứng số một trong 142 chương trình trên máy chủ CGOS 9×9.

2007–2008: nấc chín quân bị lấy

Năm 2007, MoGo thắng bàn lớn 19×19 ở Olympiad. Tháng 3/2008, nó thắng kỳ thủ chuyên nghiệp Taranu năm đẳng trên bàn 9×9. Ngày 7/8/2008 ở Portland, MoGo chạy từ xa trên siêu máy tính Huygens ở Amsterdam (khoảng 800 lõi, tên gọi MoGo Titan), thắng Kim Myungwan 8p chấp chín quân, hơn 1,5 điểm. Chưa đầy bốn tuần sau, ngày 4/9/2008, Crazy Stone thắng nữ kỳ thủ Aoba Kaori 4p ở mức chấp tám quân.

Cuối 2008–2009: tám, bảy, sáu quân

Tháng 12/2008, Crazy Stone thắng Aoba ở mức chấp bảy quân. MoGo thì thua Kim ở mức bảy quân. Tháng 2/2009, tại Taiwan Open, MoGo thắng Zhou Junxun 9p khi chấp bảy quân, rồi thắng kỳ thủ chuyên nghiệp Chien 1p khi chấp sáu quân.

2010–2014: bức tường bốn quân

Điểm yếu của phương pháp là những thế cờ chỉ có đúng một nước cứu: trung bình thống kê khiến máy bỏ lỡ nước đó. Mức chấp vì thế nhích rất chậm. Zen thắng Takemiya Masaki 9p ở chấp năm rồi chấp bốn quân (2012). Crazy Stone thắng Ishida Yoshio năm 2013 và Yoda Norimoto ngày 21/3/2014 (hơn 2,5 điểm), đều ở mức chấp bốn quân. Cũng năm 2014, Franz-Józef Dickhut, người chơi 6 đẳng nghiệp dư, thắng Crazy Stone 3–1 khi không chấp quân nào.

2015–2016: AlphaGo

Hai người từng ở trong cuộc đua là David Silver (đồng tác giả cải tiến RAVE với Gelly) và Aja Huang (tác giả Erica, từng làm việc cùng Coulom) sau này ở DeepMind. Họ đưa hàm đánh giá trở lại, lần này do mạng nơ-ron học được: một mạng chính sách và một mạng giá trị dẫn đường cho tìm kiếm cây Monte Carlo. Tháng 10/2015, AlphaGo thắng Fan Hui 5–0 không chấp quân, và kết quả được công bố trên Nature ngày 28/1/2016.

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

  • Chiến thắng ở Portland là thật nhưng là ván nhanh khoảng một giờ ở mức chấp tối đa. Theo lời kể, Kim xếp MoGo ở trình hai, ba đẳng nghiệp dư, và ông thắng máy ở các ván cờ chớp chấp chín và mười một quân, chỉ thua khi chấp mười hai quân.
  • Crazy Stone ở Turin 2006 chỉ vô địch bàn nhỏ; trên bàn 19×19 nó xếp thứ năm.
  • DeepMind không phát minh ra tìm kiếm Monte Carlo. Người được coi là "cha đẻ" cũng không rõ ràng, vì trước Coulom đã có Brügmann và những nhóm khác đi gần cùng ý tưởng.
  • Câu nói đùa của Yoda (máy "nương tay" ở cuối ván) và lời đoán của Coulom rằng còn khoảng mười năm nữa chỉ đến qua lời kể lại, độ chắc thấp.
  • Chi tiết AlphaGo chấp ngược bốn quân vẫn thắng Crazy Stone và Zen chưa được đối chiếu lại với bản Nature.

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

AlphaGo là bước nhảy thật: nó mang trở lại hàm đánh giá mà cả ngành từng bỏ cuộc, và học nó thay vì viết tay. Nhưng nó đứng trên cái cây do người khác trồng. Ý nghĩ rằng có thể thôi chấm điểm thế cờ, chỉ cần chơi tới cùng rồi đếm, đã đến từ Munich, Lille, Paris và Budapest.

Lịch sử hay ghi tên người cán đích, còn đường đua do nhiều người trải. Lần tới khi một công nghệ mới nổi tiếng, nên hỏi ai đã nhặt những quân đầu tiên khỏi bàn cờ.

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

MoGo là gì và nó thắng ai năm 2008?

MoGo là chương trình cờ vây dùng tìm kiếm cây Monte Carlo với công thức UCT, do nhóm ở Paris phát triển. Ngày 7/8/2008 ở Portland, nó thắng Kim Myungwan 8p khi được chấp chín quân, hơn 1,5 điểm.

Tìm kiếm cây Monte Carlo (MCTS) hoạt động thế nào?

Máy chơi ngẫu nhiên đến hết nhiều ván từ mỗi nước đi, rồi dồn thêm ván thử vào nhánh có tỷ lệ thắng cao. Nó không cần công thức chấm điểm thế cờ.

Ai phát minh ra MCTS?

Không có câu trả lời chắc chắn. Brügmann có chương trình Gobble năm 1993, Coulom đặt tên "Monte-Carlo Tree Search" năm 2006, và nhóm của Gelly cùng Teytaud kết hợp với UCT trong MoGo.

AlphaGo liên quan gì đến MoGo và Crazy Stone?

AlphaGo là tìm kiếm cây Monte Carlo có thêm mạng chính sách và mạng giá trị. David Silver từng cùng Gelly cải tiến MoGo, và Aja Huang từng làm việc cùng Coulom trước khi cả hai tham gia dự án này.

Trước AlphaGo, máy đã mạnh đến đâu ở cờ vây?

Đến năm 2014, máy thắng kỳ thủ chuyên nghiệp cao đẳng khi được chấp bốn quân, nhưng Crazy Stone vẫn thua Dickhut, một người chơi nghiệp dư mạnh, 1–3 khi không chấp.

Nguồn tham khảo

  • AGA E-Journal và trang computer-go.info (sự kiện Portland 2008)
  • ScienceDaily (2009) về MoGo Titan và giải Taiwan Open
  • Rémi Coulom, bài báo Crazy Stone (2006) và slide JFFoS (2009)
  • Bernd Brügmann, bài viết về Gobble (1993)
  • Gelly, Wang, Munos, Teytaud (2006) về MoGo; Gelly và Silver (AI 175(11); CACM 55(3))
  • Silver et al., Nature 529 (2016) về AlphaGo
  • Wikipedia: Computer Go, Crazy Stone, Monte Carlo tree search, AlphaGo, Aja Huang

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