Chiếc máy đánh cờ đầu tiên
Năm 1769 kỹ sư người Hungary Baron Wolfgang von Kempelen thiết kế một chiếc máy chơi cờ để làm vui cho nữ hoàng Áo Maria Theresia. Đây là một cỗ máy cơ khí hoàn toàn, có hình dáng giống như một người Thổ. Tất nhiên là sức mạnh nổi bật của nó là nhờ một kiện tướng được khéo léo giấu bên trong nó. Chiếc máy này là đồ giả mạo 
Chiếc “máy giấy” của Turing
Một điều đáng kinh ngạc là chương trình chơi cờ đầu tiên được viết trước khi chiếc máy tính đầu tiên được phát minh. Nó được viết bởi một người nhìn xa trông rộng, biết rằng máy tính có thể lập trình được sắp ra đời và một khi nó được phát minh ra, nó có thể chơi cờ được.
Người đó là Alan Turing, một trong những nhà toán học lớn của thời kỳ đó. Turing đứng đầu nhóm phá mã bí mật “Enigma” của Đức, có ảnh hưởng lớn đến kết cục của chiến tranh thế giới lần thứ 2. Ông rất thích chơi cờ nhưng mặc dù rất cực kỳ thông minh và giành rất nhiều công sức để học cờ nhưng ông vẫn chỉ là một người chơi tương đối yếu. Sau chiến tranh, ông viết những lệnh hướng dẫn để máy tính có thể chơi cờ được. Vào thời điểm đó chưa có chiếc máy tính nào có thể chạy được các lệnh nên chính ông thực hiện các lệnh đó, đóng vai bộ xử lý trung tâm và cần khoảng nửa tiếng cho một nước đi. Một ván cờ được ghi lại, trong đó chiếc “paper machine” của Turing thua một đồng nghiệp.
Đây là ván cờ lịch sử: Turing’s paper machine – Alick Glennie, Manchester 1952: 1.e4 e5 2.Nc3 Nf6 3.d4 Bb4 4.Nf3 d6 5.Bd2 Nc6 6.d5 Nd4 7.h4 Bg4 8.a4 Nxf3+ 9.gxf3 Bh5 10.Bb5+ c6 11.dxc6 0-0 12.cxb7 Rb8 13.Ba6 Qa5 14.Qe2 Nd7 15.Rg1 Nc5 16.Rg5 Bg6 17.Bb5 Nxb7 18.0-0-0 Nc5 19.Bc6 Rfc8 20.Bd5 Bxc3 21.Bxc3 Qxa4 22.Kd2? [22.h5 would have trapped the bishop] 22…Ne6 23.Rg4 Nd4? [23…Rxb2! 24.Bxb2 Rxc2+] 24.Qd3 Nb5 25.Bb3 Qa6 26.Bc4 Bh5 27.Rg3 Qa4 28.Bxb5 Qxb5 29.Qxd6 Rd8 0-1.
Chiến lược của Shanon
Cũng vào cùng thời với Turing, một nhà toán học lớn khác, Claude Shanon của Bell Laboratorié cũng nghĩ tới việc dạy máy tính chơi cờ. Ông nhận ra rằng vấn đề là ở chỗ có quá nhiều khả năng tiếp diễn sau một nước đi. Do đó ông phân biệt giữa “chiến lược A”, tìm kiếm tất cả những nước tiếp theo, và “chiến lược B”, bỏ những đường không cần thiết. Ngày nay chúng ta phân biệt các chương trình theo loại “cục súc” (brute force) hay “lựa chọn” mặc dù tất cả các chương trình mạnh đều ít nhiều thuộc về loại “cục súc”.
Cờ thay vì bom nguyên tử
Trong những năm chiến tranh, Mĩ xây dựng một phòng thí nghiệm khổng lồ ở Los Alamos trong sa mạc của bang New Mexico. Mục đích của nó là nghiên cứu chế tạo bom nguyên tử. Để tìm ra dạng cấu tạo của phần kích nổ để có thể tạo thành phản ứng dây chuyền đòi hỏi rất nhiều tính toán.
Năm 1946, nhà toán học Hungary/Mỹ John von Neumann được giao nhiệm vụ thiết kế một chiếc máy tính để thực hiện công việc này nhanh hơn. Năm 1950, một chiếc máy khổng lồ được goi là MANIAC I được chế tạo. Nó có hàng nghìn bóng chân không và công tắc và có thể thực hiện 10000 lệnh trong một giây. Nó cũng có thể được lập trình.
Thay vì ngay lập tức bắt tay vào việc chế tạo bom, các nhà khoa học bắt đầu thí nghiệm với chiếc máy. Một trong những điều đầu tiên họ làm là viết một chương trình chơi cờ. Nó chơi trên một bàn cờ thu nhỏ 6×6 và không có Tượng. Mặc dù vậy chương trình này vẫn cần 12 phút để tìm kiếm trước 4 ply (ply là nửa nước đi, ví dụ e4 hay …d5; 1.e4 e5 là một nước đi) (với Tượng trên bàn cờ nó sẽ cần khoảng 3 tiếng).
Chương trình này chơi ba ván cờ trong những năm 50. Ván đầu tiên thi đấu với chính nó (Trắng thắng), ván thứ hai với một người chơi hay, chấp nó một hậu. Ván cờ kéo dài 10 tiếng và người thắng. Cuối cùng nó chơi với một phụ nữ trẻ, mới học chơi cờ tuần trước. Chương trình thắng trong vòng 23 nước. Đó là lần đầu tiên con người thua một chiếc máy tính trong một trò chơi trí tuệ.
Đây là ván cờ lịch sử thứ hai (bàn cờ 6×6, không tượng, tốt không được phép đi hai ô trong nước đầu tiên, không được nhập thành)
MANIAC 1 – Human, Los Alamos 1956: 1.d3 b4 2.Nf3 d4 3.b3 e4 4.Ne1 a4 5.bxa4? [5.Nd2 and 6.Nd2-c4+ Nbcxc4 7.b3xc4 with a good game] 5…Nxa4 6.Kd2? Nc3 7.Nxc3 bxc3+ 8.Kd1 f4 9.a3 Rb6 10.a4 Ra6 11.a5 Kd5 12.Qa3 Qb5 13.Qa2+ Ke5 14.Rb1 Rxa5 15.Rxb5 Rxa2 16.Rb1 [to prevent 16…Ra1 mate!] 16…Ra5 17.f3 Ra4 18.fxe4 c4 19.Nf3+ Kd6 20.e5+ Kd5 21.exf6Q Nc5 22.Qf6xd4+ Kc6 23.Nf3-e5 mate.
Cờ và toán học
Vấn đề chính với các chương trình chơi cờ là số lượng lớn các nước phải tính toán. Một ví trí trung bình sẽ có 40 nươc đi hợp lệ. Nếu bạn tính tất cả các nước đi đối phương trả lời bạn sẽ có 40×40 = 1600 vị trí. Điều này có nghĩa là sau hai ply, được coi là một nước đi trong cờ Vua, 16000 vị trí có thể xảy ra. Sau hai nước nó là 2.5 triệu vị trí và sau ba nước là 4.1 tỷ. Trung bình một ván cờ kéo dài khoảng 40 nước. Số vị trí cần tính là khoảng 10 mũ 128, lớn hơn cả số nguyên tử có trong vũ trụ (chỉ khoảng 10 mũ 80)
Một điều dễ nhận thấy là không có chiếc máy tính hay loại máy nào có thể chơi cờ bằng cách tìm ra tất cả các khả năng. Nhưng con người cũng không phải là hoàn hảo. Câu hỏi là máy cần tìm kiếm tới độ sâu nào (trước bao nhiêu nước) để có thể đối chọi được với khả năng chiến lược của con người. Những chiếc máy tính thời đầu có thể tạo và đánh giá khoảng 500 vị trí trong một giây hay 90000 vị trí trong ba phút, thời gian bạn có để đi một nước trong các cuộc thi đấu. Điều này có nghĩa là nó chỉ có thể tìm kiếm trước 3 ply (một nước đi rưỡi). Điều này có nghĩa là nó chơi rất kém – chỉ ngang một người mới tập chơi. Để tìm kiếm sâu hơn nữa nó cần giải quyết được 15000 vị trí trong một giây, nhanh hơn gấp 30 lần. Nhưng tính toán trước 4 ply cũng chưa đủ sâu. Do đó máy tính dường như không bao giờ có thể chơi ở trình độ kiện tướng trong cờ Vua.
Alpha-beta
Bước nhẩy vọt đầu tiên là năm 1958 khi ba nhà khoa học của đại học Carnegie-Mellon University tại Pittsburgh (Newell, Shaw và Simon) tìm ra một phát hiện quan trọng. Bạn có thể bỏ một phần lớn của cây tìm kiếm mà không ảnh hưởng tới kết quả. Họ gọi đó là thuật toán alpha-beta. Một điểm cần nhớ là đây là một kỹ thuật toán học thuần tuý.
Đây là sơ lược thuật toán alpha-beta trong cờ Vua: giả sử máy tính đã kết thúc ước lượng một nước đi và bắt đầu tính toán nước thứ hai. Ngay khi có một đường chứng tỏ nó sẽ có giá trị thấp hơn nước đầu tiên chúng ta có thể bỏ đường tìm kiếm này. Chúng ta không cần biết chính xác là nước đi thứ hai tệ hơn bao nhiêu so với nước đi đầu tiên nhưng chắc chắn là chúng ta muốn nước đi đầu tiên hơn.
Thuật toán alpha-beta có kết quả giống như một tìm kiếm đầy đủ trong khi chỉ phải đi qua căn bậc hai số vị trí mà tìm kiếm đầy đủ cần. Đột nhiên những chiếc máy tính thời đầu có thể tìm kiếm trước 5 hoặc 6 ply. Vào thập kỷ 70, chiếc máy tính nhanh nhất (CDC Cyber series) có thể tìm trước tới 7 ply và đạt được khả năng chơi đáng nể. Nhưng kể cả với alpha-beta, bạn vẫn cần tốc độ gấp 5 lần để có thể tìm thêm một ply nữa. Số mũ của số phải tìm kiếm một lần nữa đuổi kịp các nhà lập trình.
Chiếc máy Belle
Ken Thompson là một nhà khoa học không thể chờ đợi những chiếc siêu máy tính giá hàng triệu đô trở nên 5 hay 25 lần nhanh hơn để có thể chơi cờ tốt hơn. Ông và một đồng nghiệp ở Bell Laboratories quyết định chế tạo một chiếc máy chỉ chuyên để chơi cờ, sử dụng hàng trăm con chip và giá khoảng 20 nghìn đô la.
Họ gọi chiếc máy đó là “Belle” và nó chỉ có thể chơi cờ. Nhưng nó có thể tìm kiếm tới 180 nghìn vị trí trong một giây (siêu máy tính vào thời đó chỉ có thể tìm được 5000 vị trí) Belle có thể tìm trước 8 hay 9 ply trong các cuộc thi đấu, giúp nó có thể được chơi trong hàng kiện tướng. Nó thắng giải vô địch thế giới máy tính chơi cờ đầu tiên và tất cả những giải đấu khác từ 1980 đến 1983 cho đến khi nó bị chiếc máy khổng lồ Cray X-MPs, đắt hơn nó một nghìn lần, qua mặt.
Những con chip để chơi cờ
Vào giữa những năm 80, giáo sư Hans Berliner, một nhà khoa học máy điện toán ở đại học Carnegie-Mellon tiếp tục công việc của Ken Thompson. Berliner, đã từng là phóng viên báo chỉ ở giải vô địch cờ vua thế giới, chế tạo một chiếc máy tính có phần cứng đặc biệt để chơi cờ, gọi là HiTech. Ông và sinh viên Carl Ebeling chế tạo một con chip để tính các nước đi. Với 64 chip chạy song song, HiTech suýt nữa đạt được danh hiệu vô địch máy tính đánh cờ vua thế giới vào năm 1986 (một chiếc Cray thắng giải này).
Sau đó các sinh viên của Berliner như Feng-hsiung Hsu, Murray Campbell và những người khác tự phát triển một chiếc máy tính khác, được gọi là ChipTest và sau đó Deep Thought. Giá của nó khoảng 5000 đô la và có thể tính toán được 500 000 vị trí trong một giây. Sau đó Hsu và Campbell cắt đứt với các thầy và gia nhậm IBM. Cùng vời Joe Hoane họ chế tạo ra Deep Blue.
Deep Blue
Garry Kasparov thi đấu với Deep blue tại Philadelphia và New York. Nó gồm có một máy chủ IBM SP/2 với một số lớn các con chip đặc biệt để tính toán nhanh. Mỗi con chip có thể xử lý hai đến ba triệu vị trí một giây. Với việc sử dụng hơn 200 con chip này, tốc độ tổng cộng của chương trình có thể tăng lên tới 200 triệu vị trí trong một giây.
Độ sâu tìm kiếm và khả năng chơi cờ
Xử lý 200 triệu vị trí trong một giây có nghĩa gì với một chiếc máy tính đánh cờ ? Ken Thompson, cha đẻ của Belle (cũng như Unix và ngôn ngữ lập trình C) tiến hành một số thí nghiệm thú vị trong những năm 80 cho thấy tương quan giữa độ sâu tìm kiếm và khả năng chơi cờ.
Thompson chơi Belle với chính nó với một bên được tính toán sâu hơn. Trung bình tính trước được thêm một ply ngang bằng với khoảng 200 điểm ELO. Với 4 ply Belle ở khoảng 1230 và với 9 ply nó đạt tới 2328 điểm ELO.
Bằng cách tiếp tục tăng độ sâu tìm kiếm (càng về sau ELO càng tăng chậm) ta có thể kết luận là cần tính trước được 14 ply để có thể đạt đến trình độ vô địch thế giới (2800)
Kết luận của các chuyên gia: bạn cần chế tạo một chiếc máy tính có thể xử lý một tỷ vị trí trong một giây (và tính trước 14 ply) nếu bạn muốn thách đấu với nhà vô địch cờ vua thế giới. Deep Blue đã tiến khá gần, nhưng chưa đạt tới điểm này.
Những chiếc máy nhỏ bé
Tất nhiên là chất lượng lập trình cũng có vị trí rất quan trọng. Những chương trình chơi cờ trên PC ngày này như Fritz hay Junior có thể xử lý 5 triệu hoặc hơn vị trí trong một giây. Chúng đều đạt đến sức mạnh khoảng 2700 ELO và là đối thủ cho bất kỳ ai trong nhóm 100 kỳ thủ đứng đầu thế giới. Trong cờ nhanh chỉ có khoảng 10 kỳ thủ đứng đầu có thể cạnh tranh với nó và nếu chơi blitz có lẽ chỉ hai hoặc ba người có thể sống sót.
Tấn công trên cả hai mặt trận
Một trong những điểm quan trọng trong sức mạnh của máy tính là nó có khả năng chơi theo các sách khai cuộc. Những kiến thức và kinh nghiệm qua bao đời của các kiện tướng có thể dễ dàng được lưu trữ trên đĩa cứng và máy tính có thể truy cập nó trong khi chơi khai cuộc. Ngay cả những chương trình trên PC cũng biết khoảng 10 triệu vị trí khai cuộc và có thể truy cập đầy đủ thống kê về chúng (những nước nào đã được đi, kết quả như thế nào, thứ hạng của người chơi v.v…). Thường thì máy tính sẽ chơi mười lăm hoặc hai mươi nước trước khi nó phải tính toán nước đầu tiên. Nếu không có được lợi thế từ kiến thức của con người trong khai cuộc, máy tính sẽ yếu đi nhiều
Máy tính không chỉ có lợi từ khối lượng kiến thức khổng lồ trong khai cuộc từ lịch sử cờ Vua mà nó còn có lợi thế từ những nghiên cứu về cờ tàn.
Cơ sở dữ liệu cờ tàn
Một lần nữa chúng ta lại gặp lại Ken Thompson, người tiên phong trong lĩnh vực này. Trong những năm 80, ông bắt đầu tạo và ghi lại tất cả những vị trí tàn cuộc với bốn và năm quân trên bàn cờ. Một thế cờ tàn cuộc bình thường với 5 quân, ví dụ như một Vua với hai Tượng và một Vua với một Mã, sẽ có khoảng 121 triệu vị trí. Với một con tốt, do nó đi không đều (nước đầu tiên có thể đi hai ô), số vị trí tăng lên 335 triệu. Thompson viết một chương trình tính toán tất cả các vị trí hợp lệ và tìm ra tất cả các đường bắt buộc dẫn trong mỗi tàn cuộc. Ông cũng nén dữ liệu và có thể lưu trữ khoảng 20 loại tàn cuộc trong một đĩa CD-ROM chuẩn.
Sử dụng cơ sở dữ liệu này, máy tính sẽ chơi mỗi tàn cuộc với độ chính xác tuyệt đối (“như là chúa trời”). Cho bất kỳ thế tàn cuộc nào, nó biết ngay lập tức đó là một trận thắng, hoà hay thua và trong bao nhiêu nước. Thường thì nó sẽ thông báo chiến thắng hay chiếu hết trước khoảng 50 nước. Khi ở bên thua nó sẽ chơi theo đường tốt nhất. Deep Blue sử dụng cơ sở dữ liệu tàn cuộc của Thompson và ngay cả chương trình cho PC Fritz bây giờ cũng sử dụng nó trong cây tìm kiếm của mình. Điều này sẽ ảnh hưởng đến sức mạnh của nó như thế nào sẽ cần thời gian để trả lời.
Một số tàn cuộc với 5 quân nổi tiếng là khó hoặc không thể cho con người có thể làm chủ. Một ví dụ điển hình là Hậu chống lại Hậu và Tốt, trong trường hợp này con người không có cơ hội nào có thể thắng được máy tính. Nhưng những tàn cuộc với 5 quân chỉ là tic-tac-toe (một trò chơi rất đơn giản) so với những tàn cuộc với 6 quân mà Thompson đang tạo ra. Trong một số tàn cuộc với 6 quân, bạn cần đi chính xác 200 nước đi để có thể dành chiến thắng. Thường thì ngay cả những kỳ thủ mạnh nhất trên thế giới cũng không thể biết được mình đã tiến đến đâu sau 100 nước đi mà máy tính nói với chúng ta là bắt buộc. Sự phát triển về công nghệ phần cứng cũng làm tăng lợi thế của máy tinhs. Các thế tàn cuộc với 6 quân của Thompson, với 8 đến 20 tỷ vị trí mỗi loại, có thể được nén và lưu trữ trên một chiếc DVD.
May mắn thay tàn cuộc với 7 quân, gồm khoảng 500 nghìn tỷ vị trí cho mỗi loại, vẫn là một tương lai xa. Và may mắn hơn nữa là hai đầu – nghiên cứu khai cuộc và cơ sở dữ liệu về tàn cuộc – sẽ không bao giờ gặp nhau. Có lẽ bạn sẽ không bao giờ thấy máy tính đi 1.e4 và thông báo sẽ chiếu hết ở nước thứ 40. Nhưng hầu như chỉ còn là vấn đề thời gian, vài năm hay một thập kỷ, trước khi máy tính có thể liên tục đánh bại nhà vô địch cờ Vua thế giới.
Frederic Friedel
