Kỹ thuật bảng phương án cho các bài toán trò chơi
Lưu Anh Tuấn
Trong lĩnh vực trò chơi, ngày nay máy tính đã có một số ưu thế so với con người. Đó là tốc
độ tính toán cực nhanh và khả năng lưu trữ các cấu hình trò chơi rất lớn. Rõ ràng máy tính
có thể phân tích và ghi nhớ các thế của trò chơi với tốc độ vượt xa con người.
Hơn nữa, lĩnh vực khoa học máy tính ngày càng phát triển những kỹ thuật tiên tiến để trợ
giúp cho khả năng “suy nghĩ” của máy tính. Một trong các kỹ thuật đó là kỹ thuật “bảng
phương án”.
Vậy kỹ thuật bảng phương án là gì? Đó là kỹ thuật dùng để tính toán và lưu trữ tất cả các
khả năng tốt nhất có thể có của mỗi cấu hình của trò chơi. Ta có thể coi đó như là một từ
điển giúp máy tính có thể có quyết định tốt nhất tại mỗi thế của trò chơi. Và ta cũng có thể
nhận ra một điều rằng, kỹ thuật này đòi hỏi một sự tính toán rất lớn và đòi hỏi phải lưu trữ
rất nhiều, nhiều khi là thừa thãi. Hạn chế này làm cho kỹ thuật bảng phương án không thể
áp dụng cho những trò chơi có không gian lớn như các trò chơi cờ tướng, cờ vua... Tuy
nhiên đối với những bài toán có không gian nhỏ thì kỹ thuật này tỏ ra rất hữu hiệu.
Ta xét một trò chơi đơn giản sau:
Trò chơi thứ 1
Cho một lưới ô vuông m x n ô. Một con hậu nằm ở một ô nào đó trên lưới. Mỗi nước đi
con hậu có thể đi một trong các hướng với số ô không hạn chế. Hai đấu thủ chơi với nhau,
đến lượt ai thì người đó cho con hậu đi. Nếu không đi được nữa thì người đó thua. Hãy lập
trình cho máy chơi với người để khả năng thắng của máy là cao nhất.
Ta cũng phải giả sử rằng nếu có một thuật toán tối ưu cho trò chơi này thì các đấu thủ đều
phải biết, do đó ở đây chỉ có yêu cầu rằng khả năng thắng của máy là cao nhất có thể được,
bởi vì nếu máy đã rơi vào thế thua thì không thể làm gì hơn.
Đối với trò chơi này, ta có thể nhận thấy rằng nếu ai đưa được con hậu về đến ô dưới trái
( ô [1,1]) thì là người đó thắng. Ta sẽ đánh dấu ô đó bằng số 1. Các ô có thể đi về được ô
này thì rõ ràng là ở thế thua, do đó phải được đánh số 0. Ta được bảng như sau:
Sau đó ta lại có thể thấy rằng nếu ta đưa được con hậu về ô [3,2] hoặc ô [2,3] thì đối thủ
của ta đến lượt họ đi chắc chắn phải đưa hậu đến một trong các ô đã được đánh dấu là 0,
đó chính là thế thằng cho ta, do đó hai ô này sẽ được đánh dấu là 1. Tương tự như trên, các
ô có thể đưa hậu về hai ô này là ở thế thua sẽ được đánh dấu là 0. Cứ tiếp tục như vậy ta

For i:=1 to 5 do
Begin
T:=0;
For k:=1 to 5 do T:=T+a[k,j+i];
T:=T-a[i,j+i];
If T=0 then a[i,j]:=1
Else a[i,j]:=0;
End;
Ta thấy chương trình này còn có một lỗ hổng, đó là nếu tính các cột từ N-4 đến cột N ta
phải xét đến các cột N+1 đến N+5 mà lại chưa có giá trị cho các cột này. Các bạn hãy thử
nghĩ xem ta sẽ khởi tạo giá trị gì cho các cột đó.
Trò chơi thứ 3
Hai người chơi trò lật xúc xắc như sau: có một con xúc xắc trên bàn, tổng S bằng giá trị
mặt trên cùng của con xúc xắc. Đến lượt ai thì người đó lật 1 trong bốn mặt bên của con
xúc xắc và cộng giá trị mặt trên vào tổng S. Sau lượt ai mà tổng S lớn hơn N cho trước thì
người đó thua. Hãy tìm cách chơi tốt nhất.
Các bạn hãy tự giải bài toán này nhé.
Chúc các bạn thành công.