Cờ vua: Máy tính với Con người

Bài viết được dịch từ bài "Chess: Computer v. Human" của tác giả Jeff Atwood

Cờ vua: Máy tính với Con người

Gần đây tôi có đến thăm Bảo tàng lịch sử máy tính ở gần San Jose, nơi có một triển lãm mới về lịch sử máy tính chơi cờ vua. Mặc dù tôi hoàn toàn không hứng thú với cờ vua như một trò chơi, nhưng máy tính chơi cờ vua lại có một ý nghĩa quan trọng trong lĩnh vực khoa học máy tính. Cờ vua vẫn là một tiêu chuẩn hữu hình và công khai nhất của sự gia tăng không ngừng về tốc độ máy tính trong vòng 50 năm qua.

Có hai chiến lược thông thường cho các chương trình máy tính chơi cờ vua:

  1. Tìm kiếm brute force hoặc Kiểu A. Tất cả các nước cờ có thể có đều được xem xét.
  2. Chiến lược AI hay Kiểu B. Chỉ những nước cờ tốt mới được xem xét.

Như ta thấy, máy tính có một khoảng thời gian khó khăn với khái niệm "tốt". Đó là lý do lịch sử máy tính chơi cờ vua bị thống trị bởi những chương trình Kiểu A. Chương trình máy tính chơi cờ Kiểu A nổi tiếng nhất có lẽ là Deep Blue của IBM, đã biến đổi qua nhiều phiên bản trước khi đánh bại một nhà đương kim vô địch cờ vua thế giới năm 1997.

Gần đây tôi có dựng một chiếc PC mới cho mình với một con chip Intel Core 2 Duo mới nhất. Theo như Fritz Chess Benchmark, chiếc PC ở nhà của tôi có thể tính toán khoảng 4,45 triệu nước cờ trên 1 giây. Thực tế trên hình biểu diễn bằng 4452 kilonode trên giây (kN/s), một đơn vị đo lường thường thấy dành cho các engine chơi cờ vua.

4.45 triệu nước cờ trên 1 giây nghe có vẻ ấn tượng, cho đến khi bạn so sánh nó với Deep Blue:

Năm    Nước cờ/giây
1985   50 nghìn
1987   500 nghìn
1988   720 nghìn
1989   2 triệu
1991   7 triệu
1996   100 triệu
1997   200 triệu

Những chiếc PC nhanh nhất đã tụt hậu 15 năm so với Deep Blue trong việc chơi cờ. Dĩ nhiên, Deep Blue được xây dựng bằng những dãy phần cứng được thiết kế riêng cho việc chơi cờ, vậy nên có một chút bất công khi so sánh trực tiếp nó với một CPU thương mại, đa nhiệm.

Cờ vua vốn là một vấn đề song song. Những CPU 2 nhân và 4 nhân trong kết quả Fritz Chess Benchmark gần như đúng gấp đôi kết quả của những CPU một nhân với cùng tốc độ. Bạn chắc chắn có thể nối một đống những chiếc desktop thương mại này và đạt được những con số như Deep Blue. Bài báo ExtremeTech thú vị về việc dựng những máy tính chơi cờ này cho thấy sẽ phải cần 24 máy Opteron 2.3 GHz dual, dual core để bắt kịp Deep Blue. Ít nhất là tháng 1 năm 2006 ở thời điểm của bài viết. Nhưng điều quan trọng hơn việc nâng rộng phần cứng là đây -- những chương trình chơi cờ Kiểu B đã trỗi dậy:

Dù brute force kém hơn, nhưng chiếc Deep Blitz có thể là một đối thủ của Deep Blue bởi những cải tiến trong phần mềm chơi cờ của nó. Deep Blitz có khả năng tính toán những nước đi tới một độ sâu tương tự vì nó có thể thu hẹp việc tìm kiếm đến những nước đi mạnh nhất.

Dữ liệu cho thấy Deep Blue dành rất nhiều thời gian để tính toán những nước đi xấu nhưng bù lại điểm yếu này thông qua brute force. Trong một trận đấu giữa Deep Blue và Deep Blitz chạy chương trình Deep Fritz hay Deep Shredder, việc máy nào thắng không rõ ràng lắm. Chắc chắn rằng Kasparov không tính toán đến 200 triệu nước đi trên giây khi ông ấy đánh bại Deep Blue ở trận 1 trong trận đấu năm 1997, do vậy con số 200 triệu nước đi trên giây không phải là một yêu cầu khi chơi cờ vua ở trình độ vô địch thế giới. Có vẻ như Deep Fritz, hiệu quả hơn trong việc loại bỏ các nước đi yếu, là một chương trình chơi cờ vua "thông minh" hơn nhiều so với phần mềm của Deep Blue.

Bảng xếp hạng máy tính chơi cờ vua mới nhất được xác định chỉ giữa các máy tính chơi với nhau. Bram Cohen cho rằng kết quả xếp hạng những trận đấu của máy tính với nhau đủ để cho thấy những chương trình máy tính chơi cờ vua vô địch vượt trên những kiện tướng của con người:

Giải đấu cờ vua nào là tốt nhất mọi thời đại? Nếu "tốt" nghĩa là "chơi tốt" thì tôi e câu trả lời là Zappa và Fruit. Trong những giải đấu thế giới dành cho máy tính, Zappa ghi được một số điểm ấn tượng là 10.5 trên 11, một hiệu năng tốt hơn bất cứ con người nào từng có trong một giải vô định thế giới của con người, và đối đầu với những đối thủ mạnh hơn bất cứ nhà vô địch con người nào từng đối mặt. Fruit xứng đáng ở vị trí thứ hai, vậy nên đây là giải đấu duy nhất chúng ta có giữa hai đấu thủ cờ vua mạnh nhất từng được tạo ra. Dĩ nhiên, bạn sẽ sớm có thể mua được phiên bản thương mại của Zappa và cho nó tự đối đầu với chính nó, sinh ra một chuỗi những ván đấu mà hầu hết trong số chúng tốt hơn bất cứ ván đấu nào từng chơi giữa hai con người với nhau. Chào mừng đến với cờ vua của thế kỷ 21.

Một vài ghi chú hài hước: Zappa và Fruit đều được viết bởi những sinh viên trong vòng 2 năm. Những chú ngựa ô thống lĩnh là một điều thường thấy trong lĩnh vực AI. Trận hòa duy nhất của Zappa thì mỉa mai thay lại là trận đấu với chương trình đã thua toàn bộ các ván đấu khác trong giải đấu.

Giờ rõ ràng là máy tính tốt hơn con người trong cờ vua, câu hỏi nổi lên, máy tính có thể cố gắng đoán được sức của một người chơi dựa trên những nước đi trong ván đấu đó không? Và ta có thể dùng phương pháp đó để tính toán những ván đấu "cố điển" không? Chúng ta có thực sự muốn?

Tôi nghĩ đó là một tuyên bố mơ hồ, nhất là do nó không dựa trên bất cứ dữ liệu thật nào từ những ván đấu giữa máy tính và con người. Mặc dù Deep Blue đã đánh bại Kasparov năm 1997, có khá nhiều dấu hiệu cho thấy Kasparov là người chơi tốt hơn và ông đã bị tâm lý trong trận đấu đó. Tất cả những trận tái đấu giữa những nhà vô địch thế giới với các chương trình chơi cờ máy tính đã cho thấy điều đó -- bao gồm 2 trận với bản thân Kasparov năm 2003. Nhà thống kê Jeff Sonas tin rằng máy tính sẽ không bao giờ liên tục đánh bại các kỳ thủ con người tốt nhất:

Máy tính đang dần dần trở nên ưu thế hơn so với mọi người ngoại trừ top 200 kỳ thủ trên thế giới. Điều đó dẫn đến hiệu suất tổng thể của máy tính càng ngày càng cao hơn. Tuy nhiên, những kỳ thủ ở otp 200 vẫn giữ được vị trí của mình ngay cả khi đối đầu với những máy tính mới nhất và tuyệt với nhất. Có thể nhóm đó sẽ sớm giảm xuống còn 100, hay top 50, nhưng không chắc chắn. Như các bạn thấy trong những bức ảnh trước của tôi, không hề có dấu hiệu nào cho thấy top 200 đang mất vị trí của họ khi đối đầu với những máy tính xếp hạng đầu.

Top 20 người (trong số hơn 2700 người) đang có một chuỗi hòa dài với máy tính, và phần còn lại của top 200 trung bình ghi được 35% đến 40% số điểm họ ghi được trong ít năm trước. Vậy nên, tôi không thấy bất cứ dấu hiệu nào cho thấy những máy tính hàng đầu đột ngột thống trị thế giới cờ vua cả. Dĩ nhiên những máy tính hàng đầu đang cải tiến, hầu hết thông qua nâng cấp phần cứng và phần mềm, nhưng bằng cách nào đó những người hàng đầu cũng cải tiến nhanh như vậy, theo những cách khác.

Chúng ta đang ở một điểm độc nhất trong lịch sử cờ vua, một trạng thái cân bằng động chưa từng có. Những máy tính hàng đầu bắt kịp với những kiện tướng hàng đầu, và ngay lúc này tôi không tin tưởng rằng máy tính sẽ vượt qua kiện tướng. Mọi thứ tùy thuộc vào liệu máy tính hay kiện tướng có thể cái thiện nhanh hơn, ngay từ hôm nay. Có thể những người hàng đầu sẽ tìm ra cách cải thiện cách chơi chống lại máy, đến lúc họ dẫn đầu trở lại. Có lẽ Garry Kasparov có thể dẫn đầu một lần nữa.

Tôi có xu hướng đồng ý. Có thể chúng ta đã đạt đến một điểm uốn. Không gian vấn đề của cờ vua lớn đến đáng kinh ngạc đến nỗi sự gia tăng tốc độ phần cứng và giải thuật có vẻ không mang lại nhiều kết quả ý nghĩa từ nay trở đi.

Máy tính chơi cờ vua trước đây đã làm sửng sốt toàn bộ chúng ta dựa trên giới hạn không thể chối cãi của định luật Moore, nhưng 200 người chơi cờ vua giỏi nhất trên thế giới vẫn đang nắm giữ vị trí của họ.