07/10/2026 · VietTechies · Biên tập
Vào năm 1950, nhà nghiên cứu Claude Shannon tại Bell Labs đã trình diễn một con chuột cơ khí di chuyển trong mê cung. Tại mỗi ngã rẽ, con chuột đối mặt với hệ số phân nhánh bằng 3 để minh họa cho phương pháp tìm kiếm thử và sai. Đối với Shannon cùng các nhà khoa học máy tính thời kỳ đầu, mê cung không đơn thuần là một phát minh giải trí, mà là một "vi thế giới" được kiểm soát chặt chẽ nhằm thử nghiệm khả năng máy tính vận hành các lựa chọn có giới hạn bằng logic hình thức.
Bùng nổ tổ hợp trong các vi thế giới
Khi các nhà nghiên cứu chuyển hướng chú ý từ những mê cung đơn giản sang cờ vua, hình học cấu trúc của các lựa chọn đã mở rộng một cách đột ngột. Theo tài liệu từ Bảo tàng Lịch sử Máy tính, Shannon tính toán rằng trung bình một kỳ thủ phải đối mặt với hệ số phân nhánh là 38 nước đi hợp lệ ở mỗi lượt. Trong một ván cờ tiêu chuẩn gồm 42 nước (tương đương 84 lượt đi của cả hai bên), cây quyết định sẽ phân nhánh thành khoảng 10^34 chuỗi nước đi có thể xảy ra.
Sự bùng nổ tổ hợp khổng lồ này khiến phương pháp tìm kiếm vét cạn (brute-force) trở nên bất khả thi trên phần cứng máy tính vào thập niên 1950. Giới nghiên cứu nhận ra rằng việc đánh giá mọi nhánh tiềm năng cho đến tận cuối ván cờ sẽ làm cạn kiệt cả bộ nhớ lẫn thời gian xử lý trước khi hoàn thành một phép tính duy nhất.
Cắt tỉa cây quyết định bằng hệ thống ký hiệu
Để vượt qua cái bẫy bùng nổ tổ hợp, các nhà nghiên cứu AI tiên phong Herbert Simon và Alan Newell đã giới thiệu phương pháp tìm kiếm kinh nghiệm (heuristic) nhằm cắt tỉa cây quyết định. Thay vì kiểm tra mọi nước đi hợp lệ, các thuật toán kinh nghiệm áp dụng những quy tắc dựa trên chuyên môn của con người để bỏ qua các nước đi không triển vọng.
Quan trọng nhất trong số các phương pháp này là thuật toán cắt tỉa alpha-beta. Bằng cách sớm phát hiện ra đối thủ có thể dễ dàng phản công một nước đi cụ thể, thuật toán sẽ loại bỏ toàn bộ các nhánh con bên dưới nước đi đó mà không cần tính toán chi tiết. Kỹ thuật này đã nén hệ số phân nhánh hiệu dụng của một thế cờ từ 38 xuống còn 6, hoặc thậm chí xuống mức 3 trong những thế cờ thuận lợi.
Trận đấu xuyên Đại Tây Dương năm 1967
Trong khoảng thời gian từ năm 1959 đến 1962, nhóm sinh viên MIT gồm Alan Kotok, Elwyn Berlekamp, Michael Lieberman, Charles Niessen và Robert Wagner đã phát triển một chương trình chơi cờ vua dưới sự hướng dẫn của John McCarthy. Nhờ ứng dụng kỹ thuật cắt tỉa alpha-beta, phần mềm đã đạt đến trình độ đủ sức đánh bại các kỳ thủ nghiệp dư trước khi các sinh viên này tốt nghiệp.
Đến năm 1967, McCarthy đã tổ chức một trận đấu qua thư từ bằng cách sử dụng phiên bản nâng cấp của chương trình Kotok để đối đầu với các nhà nghiên cứu AI Liên Xô tại Viện Vật lý Lý thuyết và Thực nghiệm Moscow (ITEP). Đội ngũ Liên Xô, do George Adelson-Velsky dẫn dắt, đã trình làng chương trình cờ vua của riêng họ. Trải qua 9 tháng thi đấu, chương trình của ITEP đã đánh bại phần mềm phía Mỹ với tỷ số chung cuộc 3-1.
Tìm kiếm tăng chiều sâu dần và phần cứng chuyên dụng
Trong bài diễn thuyết nhận Giải thưởng Turing năm 1975, Newell và Simon đã chính thức hóa giả thuyết Hệ thống Ký hiệu Vật lý (Physical Symbol System hypothesis), khẳng định rằng cả trí tuệ con người lẫn máy tính đều đạt được trí thông minh thông qua việc thao tác trên các mô hình ký hiệu có cấu trúc. Cờ vua khi đó đóng vai trò là mô hình vận hành cho quan điểm nhận thức này.
Các cải tiến thuật toán nhanh chóng nối tiếp sau đó. Năm 1976, David Slate và Larry Atkins đã giới thiệu kỹ thuật tìm kiếm tăng chiều sâu dần (iterative deepening search) trong chương trình Chess 4.5. Phương pháp này gia tăng từng bước chiều sâu tìm kiếm theo các hướng đi triển vọng, giúp Chess 4.5 trở thành chương trình máy tính đầu tiên giành chiến thắng tại một giải đấu cờ vua mở rộng của con người.
Việc thiết kế phần cứng cũng nhanh chóng đồng hành cùng sự phát triển của thuật toán. Năm 1977 tại Bell Labs, Ken Thompson và Joe Condon đã chế tạo Belle, một máy tính chuyên dụng cho cờ vua sở hữu các bo mạch tùy chỉnh và cơ sở dữ liệu tàn cuộc chuyên biệt.
Những thử nghiệm ban đầu này đã thiết lập nền móng cho tìm kiếm kinh nghiệm và thao tác ký hiệu trở thành xương sống của AI cổ điển. Bằng cách biến các quyết định trong trò chơi thành những cây quyết định có thể quản lý được, các nhà nghiên cứu thời kỳ đầu đã chứng minh cách giải quyết vấn đề có cấu trúc vận hành hiệu quả ra sao trước khi việc mở rộng phần cứng vét cạn tái định nghĩa cờ vua máy tính.
Ảnh minh họa do AI tạo, không phải ảnh tư liệu.
Nguồn: AI and Play, Part 1: How Games Have Driven Two Schools of AI Research