1
Chương 3. TRÒ CHƠI, TÌM KIẾM VÉT CẠN, ĐỘ PHỨC TẠP
TÍNH TOÁN

NỘI DUNG

3.1 Làm sao để thắng - định nghĩa trò chơi
3.2 Các trò chơi độ phức tạp hàm mũ
3.3 Kỹ thuật rút gọn, máy Turing bất định
3.4 Tính toán nhanh

TÀI LIỆU THAM KHẢO
1. Bài giảng về cơ sở tính toán tại địa chỉ http://www.cs.bu.edu/~lnd/toc/
2. Dexter C. Kozen. Theory of Computation. Springer, 2006
3. Michael Sipser , Introduction to the Theory of Computation, 2nd edition,
Couse technology 2005
4.J. V. Neumann, O. Morgenstern. Theory of Game and Economic Behavior,
Princeton Univ. Press, 1944 2
3.1. Làm sao để thắng - định nghĩa trò chơi

Trong mục này sẽ xét bài toán có lẽ hấp dẫn hơn: trò chơi với thông tin đầy đủ, hai người
chơi và tổng 0. Sẽ xét một vài trò chơi đơn giản không có thuật toán hữu hiệu mà phải tìm kiếm
vét cạn tất cả các cấu hình cho phép.

3.1.1 Định nghĩa trò chơi


- Trò chơi cờ : Cờ là trò chơi 2-người chơi với thông tin đầy đủ, nhưng không phải là trò
chơi thắng-thua vì có khả năng hai đấu thủ hòa nhau Hình 1: Một thế cờ - Trò chơi bài:Trò chơi bài là trò chơi không có thông tin đầy đủ. Bởi vì trong trò chơi bài, chỉ có
một phần thông tin f
i
(x) (các quân bài trên tay của người chơi thứ i) của thế x là được biết 4
3.1.2 Chiến lược chơi để giành chiến thắng

Mỗi người chơi có chiến lược chọn nước đi đối với mỗi thế. Chiến lược S gọi là chiến thắng
nếu nó đảm bảo thắng lợi cho người chơi biết nó trong mọi cách chơi của các đối thủ. Có thể
mở rộng t trong T thành V trong tất cả các thế có chiến lược chiến thắng cho một bên chơi mà
V(x) = max
m
{a(x)V(r(x, m))}.

Định giá hoặc giải trò chơi có nghĩa là tính V. Cho phép chọn nước đi tốt trong một trò chơi
mở rộng. Thực chất có thể mở rộng trò chơi G thành G’ bằng cách bổ sung thêm giai đoạn
chuẩn bị vào G. Tại giai đoạn chuẩn bị, người chơi A có thể đề nghị thế bắt đầu G, còn đối thủ
B lựa chọn phía để chơi. Sau đó, A có thể bắt đầu chơi G hoặc giảm số đếm các thế chưa sử

n
cặp chiến lược cho 2 người chơi. Đối với trò chơi 5-bit là 2
320
. Để
chứng minh định lý, đưa ra một chiến lược nhanh (nhưng với thời gian hàm mũ).

Chứng minh định lý:
- Xây dựng một đồ thị gồm tất cả các thế và các nước đi x-bit.
- Tạo V = 0 và tạo lại V = v trong T.
- Lặp cho đến hết: nếu V(x) = 0, tạo V(x) = a(x)max
m
{a(x)V(r(x, m))}.
Thủ tục dừng khi V
-1
(0) rỗng do hết thời gian hạn định cho trò chơi.
- Về nguyên tắc, khó tính được r. Chỉ xét tính được r trong không gian O(x). Sau đó, 2
2x

nước đi có thể có thể tính được với thời gian hàm mũ 2
3x
. Thuật toán thực hiệ mọi nước đi
trong từng bước. Vì vây, tổng thời gian chạy là 2
3x+1
; tuy cực kỳ chậm (2
313
đối với trò chơi
13 bit) nhưng nhanh hơn rất nhiều so với thuật toán vét cạn (Hàm mũ của hàm mũ thời gian).

 Bài tập: Trò chơi vơi que diêm. Cho 3 hộp, mỗi hộp có 3 que diêm:



Hình 2: Bàn cờ của Martin Gardne

Xét xem bên trắng có thể luôn luôn thắng hay không?

- Phương án của Sid Sackson: Bàn cờ được mô tả như hình 3. Hình 3: Bàn cờ của Sid Sackson

Trong phương án này, quân vua và quân tháp có thể hoán đổi vị trí cho nhau về cuối của bàn
cờ chỉ một lần duy nhất trong một ván cờ.
Xét xem bên trắng có thể luôn luôn thắng hay không? 8
- Phương án của Dam Glimne: Bàn cờ được mô tả như hình 4. Hình 4: Bàn cờ của Dam Glimne

Trong phương án này, Vua có thể di chuyển một hoặc hai ô với điều kiện không nhảy qua
một quân cờ khác. Quân xe di chuyển như thông thường. Quân Tượng di chuyển qua một số ô
tùy ý đến một ô cùng màu và có thể nhảy qua các quân cờ ở ô khác màu. Quân Mã di chuyển
qua 2 hoặc 3 ô và có thể nhảy qua quân cờ khác. Quân Hậu di chuyển như quân Xe và như quân
Tượng. Xét xem bên trắng có thể luôn luôn thắng hay không? Sử dụng máy Turing phổ dụng u (được định nghĩa như một ô tô mát tế bào 1-con trỏ) với u
chỉ dừng khi đầu đọc-ghi của nó lăn ra khỏi tận cùng bên trái của băng vào ô trắng. Bài toán

Hình 5: Hình ảnh của băng

Qui tắc của trò chơi: Trò chơi bắt đầu với cấu hình trong hình 6. Hình 6: Cấu hình khởi tạo trò chơi 10
L đi đầu tiên và thay thế các dấu ? bởi các ký hiệu theo đòi hỏi tương ứng trạng thái của ô
p+s tại bước t của u(x) (Xem hình 7). Hình 7: Nước đi của L

S đi như sau: chọn s, chép B
s
vào thế của A, điền các dấu ? vào B, cộng s vào p và -1 vào t
(Xem hình 8). Hình 8: Nước đi của S

Chú ý rằng, L có thể phạm sai lầm (tức là điền vào dấu ? không đúng như tính toán thực tế
của u(x)), với điều kiện L luôn kiên định vơi qui tắc nêu trên. S có thể tiến hành kiểm tra hai cấu
hình băng liên tiếp. S không thể dựa vào các nước đi trước đây hoặc tính toán thực tế của u(x)
như là căn cứ đối với sai lầm của L. 11

3.3.1. Mô phỏng trò chơi máy Turing bằng trò chơi cờ tuyến tính
 Để rút gọn trò chơi dừng về trò chơi cờ tuyến tính cần đưa vào một số khái niệm:
- Máy Turing không tiền định (NTM) là máy Turing TM mà đôi khi xảy ra sự thay đổi trạng
thái (giới hạn) được lựa chọn một hàm (của cấu hình TM), thực hiện bởi một bộ điều khiển. Máy
TM (nguyên bản) M thừa nhận xâu x nếu M(x) = yes, còn NTM M thực hiện nếu cho trước bộ
điều khiển d sao cho M
d
(x) = yes. NTM mô tả những trò chơi một người chơi, chẳng hạn khối
Rubic với các qui tắc đơn giản. Ta có thể tính toán chiến lược chiến thắng với thời gian hàm mũ
(Vét cạn tất cả các thế).
- Các TM xen kẽ (ATM) là sự biến đổi của NTM được điều khiển bởi hai bộ điều khiển xen
kẽ (người chơi) l và r. Một xâu được thừa nhận nếu tồn tại l mà với mọi r có M
l,r
(x) = yes. Trò
chơi của ta có thể xem như một ATM sử dụng không gian nhỏ nhưng với thời gian hàm mũ để
đưa ra kết quả của trò chơi. Nó nhắc nhở l và r lần lượt lựa chọn nước đi (trong một vài bước nếu
nước đi được xác định bởi một số bit) và tính thế kết quả cho đến khi có người chơi chiến thắng.
 Trước hết ta mô phỏng trò chơi máy Turing bởi L-trò chơi cờ, một phương án của trò chơi cờ
tuyến tính. Nó sẽ có bàn cờ như hình 9 và giống như cờ, có 6 cấp bậc. 13

Hình 9: Bàn cờ tuyến tính
Khác với trò chơi cờ tuyến tính, trong đó chỉ quân cờ chiến thắng được phép thay thế, trong
L-trò chơi cờ, quân cờ chiến thắng cũng có thể thay thế bởi quân cờ (có cùng giới tính) cùng phe;
bit giới tính được xác định bởi bít phe trong các bước trước, và một bảng tùy ý phù hợp hơn qui
tắc giới tính đơn giản để xác định quân cờ chiến thắng.
 Quá trình mô phỏng sẽ hoàn tất bằng mô tả trò chơi dừng như là tính toán ATM mô phỏng
bởi máy Turing phổ dụng (Sử dụng lệnh “=” đối với các input của người chơi). Máy Turing

Hình 10. Mô hình tính toán hẹp
 Có thể chuyển tính toán hẹp thành tính toán nén? Điều đó tương đương với việc tồn tại thuật
toán P-thời gian giải quyết mọi trò chơi nhanh, tức là trò chơi có qui tắc chuyển vị P-thời
gian và bộ đếm xác định mỗi nước đi, được giới hạn số lượng các nước đi bởi đa thức. Thuật
toán trong mục 3.1 có thể cài đặt song song với P-thời gian đối với mỗi trò chơi. Ngược lại,
mỗi tân từ tính được hẹp có thể biểu diễn như là việc xác định người chiến thắng trong trò
chơi nhanh (tương tự trò chơi dừng). Vì vậy, các trò chơi nhanh (tức là tính toán kế tiếp hẹp)
phù hợp với tính toán tiền định lớn.

 Câu hỏi liên quan: Có phải toàn bộ các thuật toán độ phức tạp hàm mũ (chẳng hạn, giải
quyết trò chơi cờ tuyến tính) là tương đương tính toán hẹp? Có hai giả thuyết loại trừ lẫn
nhau: có thể giải bài toán dừng giới nội thời gian hàm mũ trong một bộ nhớ đa thức. 16
3.4. Tính toán nhanh
3.4.1. Kỹ thuật song song hoá
Gỉa sử một giáo sư có trong văn phòng một chương trình (đối với một máy nhỏ có không
gian tuyến tính và thời gian hàm mũ) giải các bài toán trong kỳ thi sắp tới. Bạn đột nhập vào văn
phòng của giá sư trước khi kiểm tra và lấy được băng chương trình. Thời gian của bạn rất ngắn,
không đủ để chạy chương trình. Nhưng cũng trong văn phòng, bạn tìm được mật khẩu giúp bạn
truy nhập được vào máy lớn đã sẵn sàng, mà máy này có tài nguyên không gian không hạn chế
(có số lượng hàm mũ các bộ xử lý song song, bộ nhớ, …). Bạn sẽ làm thế nào, hỡi chàng sinh
viên ranh mãnh, lợi dụng tài nguyên vô hạn để giải bài thi trong một thời gian ngắn?
Hãy sinh đồng thời tất cả các cấu hình của máy nhỏ với không gian nhớ tuyến tính mà mỗi
một như là quá trình song song. Sẽ có M = n
O(n)
cấu hình/quá trình, tức là có n
O(n)
đồ thị n đỉnh và

trạng thái của b và các láng giềng của b khi xác định b
t+1
(Xem hình 11). Hình 11: Lược đồ không-thời gian 18
Tính kết quả của M (tại ôtômát trung tâm O) với giả thiết thời gian tính toán n (tức là độ sâu
của đồ thị) là nhỏ. Mỗi node có thể mô tả bởi bộ ba (i, t, s), trong đó i là thế của ôtômát, s là trạng
thái của nó, t là thời gian. Độ dài của bộ ba là nhỏ: s = O(1), t = O(n logn). một ôtômát chỉ
có thể liên quan nếu nó có thời gian truyền thông tin đến O, tức là có  n đường kết nối từ nó. Chỉ
có 3
n
đường kết nối như vậy (O chỉ có 3 láng giềng). Do đó i = O( log(3
n
)) = O(n).
Bởi vậy, có thể lưu trữ mỗi sự kiên trong một không gian nhỏ. Nhưng điều này không có ích
gì nếu cần lưu trữ một số lượng lớn các sự kiện. Để biết có bao nhiêu sự kiện, xét trò chơi xếp sỏi
với qui tắc chơi như sau. Mục đích là xếp sỏi vào node O của đồ thị có hướng và chỉ có thể đặt
sỏi vào một node nếu tất cả các node cha của nó đã được đặt sỏi. Có k viên sỏi và chúng có thể
được lấy và dùng lại.
Chú ý là node input không có cha nên luôn có thể đặt sỏi. Có thể thắng nếu k = O(dn), trong
đó d là bậc của đồ thị và n là độ sâu của nó). Chứng minh điều đó bằng qui nạp. Giả sử đã đặt sỏi
vào node mức t  0 với 1 + (d-1)t viên sỏi. Tiếp theo cần đặt vào node mức t+1 với (d-1)t + d = 1
+ (d-1)(t+1) viên sỏi. Cần đặt sỏi vào mỗi một node cha của các node node đó và sau đó có thể
lấy và dùng lại sỏi khi rời khỏi node đó. Cuối cùng, đặt viên sỏi vào chính node đó. Tuy vậy, thời
gian đặt sỏi vào đồ thị này có thể lớn (có thể phải duyệt tất cả các đường dẫn đi xuống).
Quá trình đặt sỏi phù hợp với quá trình tính sự kiện trong lược đồ đang xét. Mỗi sự kiện có