BÁO CÁO ĐỒ ÁN
MÔN TRÍ TUỆ NHÂN TẠO

Đề bài:
Giải thuật cắt tỉa Alpha-Beta.Phương pháp và minh họa.Hà nội tháng 4-2008
Các vấn đề sẽ trình bày
I: Tỡm hiu v gii thut ct ta Alpha-Beta.
I.1:Cây trò chơi.
I.2:Chiến lợc vét cạn.
I.3:Chiến lợc MiniMax.
I.4:Thuật toán cắt tỉa Alpha-Beta.
I.5: Đánh gía thuật toán Alpha-Beta.
I.6: Hớng cải tiến thuật toán AlphaBeta.
II: ng dụng thuật toán cắt tỉa AlphaBeta cài đặt chơng trình
chơi cờ vua.
II.1: Sơ đồ các lớp cơ bản của chơng trình.
II.2:Các chức năng chính của chơng trình:
III.3: Hng phỏt trin ca chng trỡnh
I: Tỡm hiu v gii thut ct ta Alpha-Beta:
Gii thut ct ta Alpha Beta l mt gii thut tỡm kim cú i
th. Mt vớ d minh ha cho thut toỏn ct ta Alpha Beta rừ nht
m ta cú th thy l cỏc chng trỡnh chi c. Vấn đề chơi cờ có
thể xem nh vấn đề tìm kiếm nớc đi, tại mỗi lần đến lợt mình, ngời
chơi phải tìm trong số rất nhiều nớc đi hợp lệ (tuân theo đúng luật
đi), một nớc đi tốt nhất sao cho qua một dãy nớc đi đã thực hiện,
anh ta giành phần thắng. Tuy nhiên vấn đề tìm kiếm ở đây sẽ rất
phức tạp , bởi vì ở đây có đối thủ, ngời chơi không biết đợc đối thủ
của mình sẽ đi nớc nào trong tơng lai. Sau đây chúng ta sẽ phát

nào đó. Do đó, trên cùng một mức của cây các đỉnh đều là Trắng
hoặc đều là Đen, các lá của cây ứng với các trạng thái kết thúc. Độ
sâu của cây trò chơi là số tầng của cây(chính là độ sâu d của cây).
Thuật ngữ nớc đi chỉ bao gồm một lần đi của một đối thủ hoặc
một lần đi phản ứng lại của đối thủ bên kia. Nói cách khác nớc đi ở
đây thực chất chỉ là nửa nớc theo cách hiểu của làng cờ.
Ví dụ: Xét trò chơi Dodgen (đợc tạo ra bởi Colin Vout). Có hai
quân Trắng và hai quân Đen, ban đầu đợc xếp vào bàn cờ 3*3
(Hình vẽ). Quân Đen có thể đi tới ô trống ở bên phải, ở trên hoặc ở
dới. Quân Trắng có thể đi tới trống ở bên trái, bên phải, ở trên.
Quân Đen nếu ở cột ngoài cùng bên phải có thể đi ra khỏi bàn cờ,
quân Trắng nếu ở hàng trên cùng có thể đi ra khỏi bàn cờ. Ai đa hai
quân của mình ra khỏi bàn cờ trớc sẽ thắng, hoặc tạo ra tình thế bắt
đối phơng không đi đợc cũng sẽ thắng.
Giả sử Đen đi trớc, ta có cây trò chơi đợc biểu diễn nh hình trên.
I.2:Chiến lợc vét cạn:
Dùng thuật toán vét cạn để tìm kiếm trên cây trò chơi dờng nh là
một ý tởng đơn giản. Ta chỉ cần chọn nhánh cây dẫn đến nớc thắng
để đi quân là đảm bảo thắng lợi. Nếu mà đúng nh vậy thì các loại
cờ sẻ trở thành một cho chơi vô cùng buồn tẻ. Rất tiếc rằng vấn đề
này không thể thực hiện nổi do sự bùng nổ tổ hợp. Ví dụ nếu từ
một thế cờ trung bình có khả năng đi đợc 16 nớc (gọi hệ số nhánh
con tại mỗi nút là 16). Nh vậy một tầng sẻ có 16 nút con và 16 nút
con này lại có 16 nút con nữa. Tổng số nút con ở độ sâu thứ 2 sẽ là
16*16=b
2
. Cứ nh vậy ở độ sâu d sẽ có b
d
nút.
Nếu giả sử độ sâu của cây là 100(hệ số nhánh là 16 và độ sâu là

trạng thái kết thúc) là giá trị của hàm kết cuộc. Đỉnh có giá trị càng
lớn càng tốt cho Trắng, đỉ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 lên gốc u. Giả sử v là đỉnh trong của cây và giá trị các
đỉnh con của nó đã đợc xác định. Khi đó nếu v là đỉnh Trắng thì giá
trị của nó đợc xác định là giá trị lớn nhất trong các giá trị của các
đỉnh con. Còn nếu v là đỉnh Đen thì giá trị của nó là giá trị nhỏ
nhất trong các giá trị của các đỉnh con.
Ví dụ: Xét cây trò chơi trong hình 4.3, gốc a là đỉnh Trắng. Giá trị
của các đỉnh là số ghi cạnh mỗi đỉnh. Đỉnh i là Trắng, nên giá trị
của nó là max(3,-2) = 3, đỉnh d là đỉnh Đen, nên giá trị của nó là
min(2, 3, 4) = 2.
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
Trắng, hàm MinVal xác định giá trị cho các đỉnh Đen.
function MaxVal(u);
begin
if u là đỉnh kết thúc then 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 then MinVal(u)
ơ
f(u)

phải xem xét toàn bộ các đỉnh của cây trò chơi. Trong các trò chơi
hay, cây trò chơi là cực kỳ lớn. Chẳng hạn, đối với cờ vua, chỉ tính
đến độ sâu 40, thì cây trò chơi đã có khoảng 10
120
đỉnh! Nếu cây có
độ cao m, và tại mỗi đỉnh có b nớc đi thì độ phức tạp về thời gian
của thuật toán Minimax là O(b
m
).
Để có thể tìm ra nhanh nớc đi tốt (không phải là tối u) thay cho
việc sử dụng hàm kết cuộc và xem xét tất cả các khả năng dẫn tới
các trạng thái kết thúc, chúng ta sẽ sử dụng hàm đánh giá và chỉ
xem xét một bộ phận của cây trò chơi.
Toàn bộ ý tởng của thuật toán này là dựa trên việc chuyển đổi mỗi
thế cờ thành một con số để đánh giá. Rất tiếc là con số này thờng
không tốt và không đủ để đánh giá hết mọi điều. Mặt khác, thuật
toán này có thể rất tốn kém(chạy chậm)do việc sinh các nớc đi và l-
ợng giá rất tốn thời gian tinh toán, do vậy độ sâu của cây trò chơi
cũng bị hạn chế nhiều. Ta cần có thêm những cải tiến để cải thiện
tình hình này.
I.4:Thuật toán cắt tỉa Alpha-Beta:
Trong chiến lợc tìm kiếm Minimax, để tìm kiếm nớc đi tốt cho
Trắng tại trạng thái u, cho dù ta hạn chế không gian tìm kiếm trong
phạm vi cây trò chơi gốc u với độ cao h, thì số đỉnh của cây trò
chơi này cũng còn rất lớn với h 3. Chẳng hạn, trong cờ vua, nhân
tố nhánh trong cây trò chơi trung bình khoảng 35, thời gian đòi hỏi
phải đa ra nớc đi là 150 giây, với thời gian này trên máy tính thông
thờng chơng trình của bạn chỉ có thể xem xét các đỉnh trong độ sâu
3 hoặc 4. Một ngời chơi cờ trình độ trung bình cũng có thể tính trớc
đợc 5, 6 nớc hoặc hơn nữa, và do đó chơng trình của bạn mới đạt

và không cần phải xem xét nữa. Khoảng [alpha,beta] còn đợc gọi là
cửa sổ alpha, beta. Trong ngữ cảnh của các trò chơi nguyên tắc
alpha-beta nói rằng, mỗi khi xem xét một nút bất kì, nên kiểm tra
các thông tin đã biết về các nút cha, ông của nó. Rất có thể do có
đủ thông tin từ cha, ông nên không cần phải làm bất cứ việc gì nữa
cho nút này. Cũng vậy,nguyên tắc này cũng giúp chỉnh sửa hoặc
xác định chính xác giá trị tại nút cha, ông của nó. Nh trên nói, một
cách để tiện theo dõi quá trình tính toán là dùng các tham số alpha
và beta để ghi lại các thông tin theo dõi cần thiết. Thủ tục
AlphaBeta đợc bắt đầu tại nút gốc với giá trị của alpha là âm vô
cùng và beta là dơng vô cùng. Thủ tục sẽ tự gọi đệ qui chính nó
với khoảng cách giữa các giá trị alpha và beta ngày càng hẹp hơn.
function MaxVal(u,

,

);
begin
if u là lá của cây hạn chế hoặc u là đỉnh kết thúc
then MaxVal
ơ
eval(u)
else
{
for mỗi đỉnh v là con của u do
{ơ
max[

then MinVal
ơ
eval(u)
else
{ for mỗi đỉnh v là con của u do
{ơ
min[

, MaxVal(v,

,

)];
// Cắt bỏ các cây con từ các đỉnh v còn lại
if





then exit
};
MinVal
ơ


;}


ơ
MinVal(w,

,

);
v
ơ
w;}
end;
T phỏt biu trờn ta s xõy dng hm AlphaBeta bng ngụn ng
ta Pascal. Hm ny s cú dng khai bỏo nh di, trong ú depth
l sõu tỡm kim, INFINITY l giỏ tr vụ cựng, thut toỏn tớnh
toỏn da trờn th c hin ti pos l cỏc bin ton cc:
function AlphaBeta(alpha, beta, depth): integer;
begin
if (depth = 0) then
AlphaBeta := Eval { Tớnh giỏ tr th c pos }
Else
begin
best := -INFINITY;
Gen; { Sinh ra mi nc i t v trớ pos }
while (cũn ly c mt nc i m) and (best < beta) do
begin
if best > alpha then alpha := best;
thc hin nc i m;
value := -AlphaBeta(-beta, -alpha, depth-1);
b thc hin nc i m;
if value > best then best := value;

cắt bỏ đợc chỉ ra trong hình trên.
I.5: Đánh gía thuật toán Alpha-Beta:
Trong điều kiện lý tởng thuật toán AlphaBeta chỉ phải xét số nút
theo công thức:
-2*b
d/2
-1 với d chẵn
- b
(d+1)/2
+b
d/2
-1 với d lẻ.
Với b=40 và d =4 ta có số nút phải xét là 2x40
2
- 1 = 3199. Nh vậy
trong điều kiện lý tởng thì số nút phải xét nhờ AlphaBeta(chỉ
khoảng 3 nghìn nút) ít hơn thuật toán Minimax (hơn 2,5 triệu nút)
là 2560000/3199 khoảng 800 lần. Còn với b=40 và d=5 ta có số nút
phải là 40
3
+40
5/2
-1=74118. Số nút phải xét nhờ AlphaBeta ít hơn
thuật toán Minimax(hơn 102 triệu nút) là 102400000/74118 =1382
lần.
Dới đây là bảng so sánh số nút phải xét giữa hai thuật toán
Minimax và AlphaBeta.
Ta có nhận xét sau:
Số lần tăng số nút khi tăng độ sâu của Minimax luôn là hệ số phân
nhánh b, trong trờng hợp này là 40. Số lần tăng của AlphaBeta ít

-Các thuộc tính mà ta cần quan tâm đên nó là:
Màu sắc của ô cờ đó
Ô cờ đó nằm ở cột thứ bao nhiêu
Ô cờ đó nằm ở hàng thứ bao nhiêu
Quân cờ nằm trên ô cờ đó
Game
Game
Player
Player
Squares
PlayerWhite
PlayerWhite
Square
Moves
Move
Pieces
Board
Board
PlayerBlack
PlayerBlack
Piece
Piece
Pieces
PieceBishop
PieceBishop
PieceKnight
PieceKnight
PieceQueen
PieceQueen
PieceKing

Ô cờ kết thúc
Quân cờ bị băt trong nớc đi đó
Danh sách các nớc đi tiếp theo
Điểm số của nớc đi
Thời gian của nớc đi
Tạo ra một nớc đi
Quay lui lại một nớc đi
So sánh điểm số của 2 nớc đi
Lớp Moves: lớp này là danh sách các nớc đi của 2 bên
Bao gồm các thao tác:
Thêm một nớc đi mới
Xóa bỏ một nớc đi
Xắp sếp lại danh sách các nớc đi theo điểm số
Trả về một nứớc đi theo vị trí
Trả về nớc đi cuối
Trả về nớc đi áp cuối
Lớp IPieceTop: đây là một lớp giao diện định nghĩa toàn bộ các thông số
trạng thái của quân cờ nh:
Tên của quân cờ đó
Giá trị cơ bản của quân cờ đó
Giá trị của quân cờ đó
Giá trị vị trí của quân cờ đó
Quân cờ đó có thể ăn đợc không
Định nghĩa cách thức đi của quân cờ đó
Các lớp: PiecePawn , PieceBishop, PieceRook, PieceKnight,PieceQueen,
PieceKing là các lớp kế thừa từ lớp IpieceTop. Nó sẽ định nghĩa lại một
cách chi tiết cụ thể cho từng quân cờ một.

Lớp Piece: Lớp này cho ta biết tên, mã , trạng thái,điểm số, số lần di
chuyển của các quân cờ.

Rook: Cộng với các offset có giá trị là:1,-1.(Sẻ xét riêng trờng hợp
nhập thành)
Knight: Cộng với các offset có giá trị là:33,31,18,14, -33,-31,-18,-
14.
Queen: Cộng với các offset có giá trị là :1,15,16,17,-1,-15,-16,-17.
King: Cộng với các offset có giá trị là :1,15,16,17,-1,-15,-16,-17.
Với t tởng là ta sẻ cộng chỉ số của quân cờ đó(Index) với các offset
tơng ứng.Nếu tồn tại ô cờ với chỉ số mới và ô cờ đó có thể không
có quâncờ hoặc là có quân cờ của đối phơng thì ta có thể đi đến ô
cờ mới đó. Sau đó lại cộng tiếp offset cho đến khi không tồn tại ô
cờ đó hoặc ô cờ đó chứa quân cờ của mình mới thôi.
Xây dựng hàm đánh giá một thế cờ:
Mỗi một quân cờ ta đều gán cho nó một giá trị, và ứng với mỗi một
ô trên bàn cờ ứng với quân cờ đó lại có các giá trị khác nhau. Thêm
vào đó ta sẽ xây dựng các hàm đánh giá độ tơng quan giữa các
quân cờ. Gồm:
Đánh gía xem quânc ờ đó có khả năng bị quân tôt tấn công
không.
Xây dựng một hàm phòng thủ cho các quâncờ. Xem quân cờ đó
đợc phòng thủ bởi những quân nào. Tức là quân nào ở bên mình mà
có thể đi đợc đến ô của nó. Sau đó ta xây dựng điểm phòng thủ ứng
với từng quân cờ.
Pawn: 60
Bishop và Knight: 45
Rook: 30
Queen và King: 20
Nh vậy điểm số của một quân cờ sẽ là bằng: Giá trị của quân cờ
cộng với điểm vị trí của nó. Và điểm của một thế cờ bằng tổng
điểm của tất cả các quân cờ đang tồn tại trên bàn.
Giá trị của các quân cờ:

-Tuy hàm đánh giá các thế cờ được xây dựng khá chi tiết xong
trong một số thế cờ cụ thể nó vẫn không tỏ ra thực sự tối ưu. Chính
vì vậy việc dạy cho chương trình học là một việc làm hết sức cần
thiết. Sau khi đã hoàn thiện các hàm đánh giá em sẽ xây dựng lại
các bảng trạng thái để lưu lại tình trạng các ván cờ mà người chơi
đã thắng máy . Từ đó tìm ra các nước cờ tối ưu hơn.
-Việc thiết lập độ sâu của chương trình chưa có do đó không thể
phân loại được cấp độ của người chơi. Tiến tới em sẽ xây dựng
game theo các Level mà tiêu chuẩn của các Level này chính là độ
sâu tìm kiếm.
-Chương trình vẫn chỉ hạn chế đánh được trên máy tính để bàn.
Tiến tới em có thể xây dựng chương trình có thể đánh trên mạng
lan. Bằng cách tạo ra các tiến trình va luồng để cập nhật lại các
nước đi.