HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA SAU ĐẠI HỌC
----------

TIỂU LUẬN

TRÍ TUỆ NHÂN TẠO
Đề tài: ỨNG DỤNG CỦA THUẬT TOÁN MINIMAX VÀ CẮT TỈA
ALPHA BETA TRONG TRÒ CHƠI DODGEM

Giảng viên hướng dẫn
Học viên thực hiện

: PGS.TS. Từ Minh Phương
: Hoàng Văn Hoãn

Lớp

Nguyễn Minh Vương
: M15CQCS02

Hà nội, tháng 05 năm 2016


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

MỤC LỤC

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 2


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

Trong khoa học trí tuệ nhân tạo, mô hình phương pháp biểu diễn tri thức là một
bước ngoặc quan trọng trong việc thiết kế các hệ cơ sở tri thức và các hệ chuyên gia.
Ngày nay, có nhiều phương pháp biểu diễn tri thức đã được đề xuất và ứng dụng. Tri thức
là một hệ chuyên gia được biểu diễn theo nhiều phương pháp khác nhau. Tùy theo hệ
chuyên gia người ta sử dụng một hoặc đồng thời cả nhiều phương pháp. Mục tiêu chính
biểu diễn tri trức trong máy tính là phục vụ cho việc thu nhận tri thức vào máy tính, truy
xuất tri thức và thực hiện các phép suy luận dựa trên những tri thức đã lưu trữ.
Biểu diễn tri thức được ứng dụng nhiều trong các bài toán thực tế, nó có đến hàng
trăm giải thuật. Một trong những phương pháp biểu diễn tri thức được áp dụng rộng rãi là
biểu diễn tri thức dựa trên các luật dẫn, trong đó có tìm kiếm heuristics. Trong bài tiểu
luận này em xin trình bày sơ lược về các phương pháp biểu diễn tri thức và ứng dụng giải
thuật Minimax và phương pháp cắt cụt α, β để giải quyết bài toán dodgem.
Việc giải quyết bài toán trên có thể đưa về các bài toán tìm kiếm trong không gian
trạng thái, tức là tìm một chiến lược chọn các nước đi hợp lệ cho máy tính. Tuy nhiên,
vấn đề tìm kiếm ở đây phức tạp hơn vì người chơi không biết trước đối thủ sẽ chọn nước
đi nào tiếp theo.
Vì vậy nhóm chúng em đã tìm hiểu một số chiến lược tìm kiếm dựa trên cơ sở của
thuật toán Minimax và phương pháp cắt cụt α, β và ứng dụng của thuật toán này trong
việc giải quyết bài toán: “Dodgem”, do thời gian có hạn nên nhóm chúng em chưa tối ưu
được toàn bộ không gian trạng thái của bài toán. Trong quá trình thực hiện tiểu luận
không tránh khỏi những thiếu sót, nhóm chúng em mong sẽ nhận được chỉ bảo của thầy
cũng như sự góp ý của các học viên khác trong lớp.

Xin chân thành cảm ơn!

Hà Nội, ngày 25 tháng 5 năm 2016
Học viên thực hiện

Nhóm 5 lớp KHMT

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 3


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

I. GIỚI THIỆU TRÒ CHƠI DODGEM
1. Trò chơi tổng quát
Xét các trò chơi giữa hai đối thủ là Đỏ(máy tính) và Black(con người). Hai
“người” lần lượt thay phiên nhau thực hiện các nước đi bằng cách áp dụng một luật chơi
cho trước xác định. Các luật này là như nhau đối với cả hai người chơi. Ta có các nhận
xét sau đây:
– Các trò chơi như thế có thể biểu diễn trong một không gian trạng thái.
– Mỗi một tình huống (configuration) trong trò chơi biểu diễn một trạng thái.
– Các luật chơi tương ứng với các phép biến đổi trạng thái.
– Trạng thái bắt đầu trò chơi được cho trước. Trạng thái mà không thể có nước đi
hợp lệ nào có thể thực hiện được gọi là trạng thái kết thúc. Có thể có một tập các trạng
thái kết thúc.
Không gian tìm kiếm đối với các trò chơi này có thể được biểu diễn bởi cây trò
chơi như sau: gốc của cây ứng với trạng thái xuất phát, các đỉnh trên cây tương ứng với

các trạng thái của bàn cờ, các cung (u,v) nếu có biến đổi từ trạng thái u đến trạng thái v.
Các đỉnh trên cây được gán nhãn đỉnh Đỏ (Đen) ứng với trạng thái mà quân Đỏ (Đen) đửa
ra nước đi. Nếu một đỉnh u được gán nhãn là Đỏ (Đen) thì các đỉnh con v của nó là tất cả
các trạng thái nhận được từ u do Đỏ (Đen) thực hiện một nước đị hợp lệ nào đó. Do vậy,
các đỉnh trên cùng một mức của cây đều có nhãn là Đỏ hoặc đều có nhãn là Đen, các là
của cây ứng với trạng thái kết thúc.

2. Giới thiệu trò chơi Dodgem
Trò chơi Dogem được sáng tạo bởi Volin Vout (Berlek amp et al, 1982). Dodgem
là một chess game, giống như cờ Caro hay cờ tướng,… Là thể loại game có 2 người chơi.
Một người là Min, người còn lại là Max. Hai người chơi sẽ thay phiên nhau đưa ra các

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 4


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

nước đi của mình theo một quy luật nào đó. Dodgem được tạo ra gồm hai quân Đen và
hai quân Đỏ được xếp vào bàn cờ 3*3 với luật chơi như sau:

Hình 1. Trò chơi Dodgem
+ Quân đen: được phép đi lên trên, sang phải hoặc xuống dưới. Quân đen có thể
được đưa ra ngoài khi ở cột ngoài cùng bên phải
+ Quân đỏ: được phép đi lên trên, sang trái hoặc sang phải. Quân đỏ có thể được
đưa ra ngoài khi ở hàng trên cùng của bàn cờ.


Hình 2. Quân đỏ và quân đen được đưa ra ngoài
Trò chơi kết thúc khi 1 trong 2 người đưa được hết các quân cờ của mình ra ngoài
hoặc chặn không cho quân đối phương di chuyển.
Ngoài ra, nếu quân Đỏ cản trực tiếp một quân Đen, nó được thêm 40 điểm, nếu cản
gián tiếp nó được thêm 30 điểm (hình 3, hình 4). Tương tự, nếu quân Đen cản trực tiếp
quân Đỏ nó được thêm -40 điểm, còn cản gián tiếp nó được thêm -30 điểm.

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 5


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

Hình 3. Quân đỏ cản trực tiếp quân đen được 40 điểm

Hình 4. Quân đỏ cản gián tiếp quân đen được 30 điểm

Hình 5. Các giá trị của quân đỏ trên bàn cờ và khi ra khỏi bàn cờ

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 6


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02


Hình 6. Các giá trị của quân đen trên bàn cờ và khi ra khỏi bàn cờ

Hình 7. Cây trò chơi Dodgem với Đen đi trước

II. THUẬT TOÁN MINIMAX VÀ CẮT TỈA ALPHA BETA
1. Thuật toán Minimax
Quá trình chơi là quá trình Đỏ và Đen thay phiên nhau đưa ra các nước đi hợp lệ
đến khi dẫn đến trạng thái kết thúc cuộc chơi. Quá trình này biểu diễn bởi đường đi từ nút
gốc tới nút lá trên cây trò chơi. Giả sử tại một đỉnh u nào đó trên đường đi, nếu u là đỉnh
Đỏ (Đen) thì cần chọn một nước đi nào đó đến một trong các đỉnh con Đen (Đỏ) v của u.
Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 7


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

Tại đỉnh Đen (Đỏ) v sẽ chọn đi tiếp đến một đỉnh con Đỏ (Đen) w của v. Quá trình này
tiếp tục cho đến khi đạt đến một đỉnh lá của cây.
Chiến lược tìm nước đi của Đỏ hay Đen là luôn tìm những nước đi dẫn tới trạng
thái tốt nhất cho mình và tồi nhất cho đối thủ. Giả sử Đỏ cần tìm nước đi tại đỉnh u, nước
đi đó tối ưu cho Đỏ là nước dẫn tới đỉnh con v sao cho v là tốt nhất trong số các đỉnh con
của u. Đến lượt Đen chọn nước đi từ v, Đen cũng chọn nước đi tốt nhất cho mình. Để
chọn nước đi tối ưu cho Đỏ tại đỉnh u, cần xác định giá trị các đỉnh của cây trò chơi gốc u.
Giá trị của các đỉnh lá ứng với giá trị của hàm kết cuộc. Đỉnh có giá trị càng lớn càng tốt
cho Đỏ, đỉnh có giá trị càng nhỏ càng tốt cho Đen. Để xác định giá trị các đỉnh của cây trò
chơi gốc u, ta đi từ mức thấp nhất (các đỉnh lá) lên gốc u. Giả sử cần xác định giá trị của

đỉnh v mà các đỉnh con của nó đã xác định. Khi đó, nếu v là đỉnh Đỏ thì giá trị của nó là
giá trị lớn nhất trong các đỉnh con, nếu v là đỉnh Đen thì giá trị của nó là giá trị nhỏ nhất
trong các đỉnh con.
Việc gán giá trị cho các đỉnh được thực hiện bởi các hàm đệ qui MaxVal và
MinVal. Hàm MaxVal xác định giá trị cho các đỉnh Đỏ, hàm MinVal xác định giá trị cho
các đỉnh Đen

Hình 8. Cây trò chơi áp dụng thuật toán Minimax

2. Thuật toán Minimax với cắt tỉa alpha-beta

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 8


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

Trong chiến lược Minimax với độ sâu hạn chế thì số đỉnh của cây trò chơi phải xét
vẫn còn rất lớn với h>=3. Khi đánh giá đỉnh u tới độ sâu h, thuật toán Minimax đòi hỏi
phải đánh giá tất cả các đỉnh của cây gốc u với độ sau h. Tuy nhiên, phương pháp cắt cụt
alpha-beta cho phép cắt bỏ những nhánh không cần thiết cho việc đánh giá đỉnh u.
Phương pháp này làm giảm bớt số đỉnh phải xét mà không ảnh hưởng đến kết quả đánh
giá đỉnh u.
+ Nút MAX có 1 giá trị α (luôn tăng)
+ Nút MIN có 1 giá trị β (luôn giảm)
+ Tìm kiếm có thể kết thúc dưới bất kỳ:
- Nút MIN nào có β ≤ α của bất kỳ nút cha MAX nào.


- Nút MAX nào có α ≥ β của bất kỳ nút cha MIN nào.

Hình 8, 9. Trạng thái kết thúc tìm kiếm

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 9


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

Ý tưởng: Giả sử tại một thời điểm hiện tại đang ở đỉnh Đỏ a, đỉnh a có anh em là v
đã được đánh giá. Giả sử cha của đỉnh a là b, b có anh em là u đã được đánh giá, và cha
của b là c như hình sau:

Hình 10. Cắt bỏ cây con gốc a nếu eval(u) > eval(v)

Hình 11. Cắt tỉa Alpha

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 10


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02


Hình 12. Cây trò chơi áp dụng cắt tỉa Alpha-beta

III. CÀI ĐẶT THUẬT TOÁN
1. Thuật toán Minimax
procedure Minimax(u, v);
Begin
val ¬ -∞;
for mỗi w là đỉnh con của u do
If val <= MinVal(w)
{val ¬ MinVal(w); v ¬ w}
End;
Function MaxVal(u);
Begin

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 11


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

If u là đỉnh kết thúc MaxVal(u) ¬ f(u)
Else MaxVal(u) ¬ max{MinVal(v) | v là đỉnh con của u}
End;
Function MinVal(u);
Begin
If u là đỉnh kết thúc MinVal(u) ¬ f(u)

Else MinVal(u) ¬ min{MaxVal(v) | v là đỉnh con của u}
End;

2. Thuật toán cắt tỉa Alpha-beta
Procedure Alpha_beta(u,v)
Begin
α ¬ -∞; β ¬ -∞;
For mỗi w là đình con của u do
If α <= MinVal(w, α, β)
{α ¬ MinVal(w, α, β); v ¬ w}
End;
Function MinVal(w, α, β); {hàm xác định giá trị cho các đỉnh Đen}
Begin
If u là đỉnh kết thúc or u là lá của cây hạn chế then
MinVal(w, α, β) ¬ eval(u)
Else for mỗi đỉnh v là con của u do
{β ¬ min{β, MaxVal(w, α, β)};
If α >= β then exit};
/* cắt bỏ các cây con từ các đỉnh v còn lại*/
MinVal(w, α, β) ¬ β
End;
Function MaxVal(w, α, β); /*Hàm xác định giá trị cho các đỉnh Đỏ*/
Begin

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 12


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem


Lớp: M15CQCS02

If u là đỉnh kết thúc or là lá của cây hạn chết then
MaxVal(w, α, β) ¬ eval(u)
Else for mỗi đỉnh v là con của u do
α ¬ max{α, MinVal(w, α, β)};
If If α >= β then exit};
/*cắt bỏ các cây con từ các đỉnh v còn lại */
MaxVal(w, α, β) ¬ α

IV. DEMO CHƯƠNG TRÌNH
1. Giới thiệu chương trình
+ Chương trình thiết kế trên Visual studio Express 2013 trong môi trường Visual
Basic, được áp dụng giải thuật Minimax và cắt tỉa Alpha-beta.

Hình 13. Giao diện của chương trình

2. Một số chức năng của chương trình

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 13


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

+ New: Là chức năng chơi lượt mới.


Hình 14. Chức năng New

+ Reset: Là chức năng chơi lại.

Hình 15. Chức năng Reset

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 14


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02

+ About: Là chức năng giới thiệu luật chơi.

Hình 16. Chức năng About

+ Quit: Là chức năng thoát khỏi trò chơi.

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 15


Tiểu luận Minimax – Alpha Beta với trò chơi Dodgem

Lớp: M15CQCS02


KẾT LUẬN

Việc nắm bắt các giải thuật là rất quan trọng, nhưng áp dụng các giải thuật đó như
thế nào trong các bài toán thực tế là điều quan trọng hơn. Các bài toán thực tế không bao
giờ trọn vẹn như trong mô hình lý thuyết, bù lại, nó lại có tính “thực tế”; sử dụng các yếu
tố thực tế đó vào ứng dụng chúng ta sẽ đem lại một sức sống mới cho các ứng dụng đó,
chương trình của chúng ta sẽ “cư xử thông minh hơn”, có tính định hướng tốt hơn và qua
đó sẽ thân thiện hơn với người sử dụng. Nhưng trước khi xây dựng các ứng dụng như
vậy, chúng ta cùng thử sức với Dodgem. Có thể có nhiều phương pháp để giải quyết các
bài toán kể trên, ở đây chúng ta sử dụng thuật toán Minimax và phương pháp cắt tỉa
Alpha-beta.
Ta có thể mở rộng bài toán và giải được những bảng số có dạng nxn, cách làm
cũng tương tự tuy nhiên ta cần tính toán lại cách thức để kiểm tra xem trạng thái của bảng
số có hợp lệ không. Chương trình này có thể tạm chấp nhận với mức Dodgem 3x3, tuy
nhiên nếu muốn giải được bài toán với n tương đối lớn thì ta cần tìm một giải pháp khác.
Xin chân thành cảm ơn!

Nhóm 5: Hoàng Văn Hoãn; Nguyễn Minh Vương

trang 16