Giáo trình trí tuệ nhân tạo- chương 4-TÌM KIẾM CÓ ĐỐI THỦ
Trong chương này chúng ta chỉ quan tâm nghiên cứu các trò chơi có hai người tham gia, chẳng hạn các loại cờ (cờ vua, cờ tướng, cờ ca rô...). Một người chơi được gọi là Trắng, đối thủ của anh ta được gọi là Đen. Mục tiêu của chúng ta là nghiên cứu chiến lược chọn nước đi cho Trắng (Máy tính cầm quân Trắng).
Ch¬ng IV
T×m kiÕm cã ®èi thñ
----------------------------
Nghiªn cøu m¸y tÝnh ch¬i cê ®· xuÊt hiÖn rÊt sím. Kh«ng l©u
sau khi m¸y tÝnh lËp tr×nh ®îc ra ®êi vµo n¨m 1950, Claude
Shannon ®· viÕt ch¬ng tr×nh ch¬i cê ®Çu tiªn. c¸c nhµ nghiªn cøu
TrÝ TuÖ Nh©n T¹o ®· nghiªn cøu viÖc ch¬i cê, v× r»ng m¸y tÝnh
ch¬i cê lµ mét b»ng chøng râ rµng vÒ kh¶ n¨ng m¸y tÝnh cã thÓ
lµm ®îc c¸c c«ng viÖc ®ßi hái trÝ th«ng minh cña con ngêi. Trong
ch¬ng nµy chóng ta sÏ xÐt c¸c vÊn ®Ò sau ®©y:
• Ch¬i cê cã thÓ xem nh vÊn ®Ò t×m kiÕm trong kh«ng gian
tr¹ng th¸i.
• ChiÕn lîc t×m kiÕm níc ®i Minimax.
• Ph¬ng ph¸p c¾t côt α-β, mét kü thuËt ®Ó t¨ng hiÖu qu¶ cña
t×m kiÕm Minimax.
4.1 C©y trß ch¬i vµ t×m kiÕm trªn c©y trß ch¬i.
Trong ch¬ng nµy chóng ta chØ quan t©m nghiªn cøu c¸c trß
ch¬i cã hai ngêi tham gia, ch¼ng h¹n c¸c lo¹i cê (cê vua, cê t íng, cê
ca r«...). Mét ngêi ch¬i ®îc gäi lµ Tr¾ng, ®èi thñ cña anh ta ®îc gäi
lµ §en. Môc tiªu cña chóng ta lµ nghiªn cøu chiÕn l îc chän níc ®i
cho Tr¾ng (M¸y tÝnh cÇm qu©n Tr¾ng).
Chóng ta sÏ xÐt c¸c trß ch¬i hai ngêi víi c¸c ®Æc ®iÓm sau.
Hai ngêi ch¬i thay phiªn nhau ®a ra c¸c níc ®i tu©n theo c¸c luËt
®i nµo ®ã, c¸c luËt nµy lµ nh nhau cho c¶ hai ngêi. §iÓn h×nh lµ
cê vua, trong cê vua hai ngêi ch¬i cã thÓ ¸p dông c¸c luËt ®i con
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 1
tèt, con xe, ... ®Ó ®a ra níc ®i. LuËt ®i con tèt Tr¾ng xe Tr¾ng, ...
còng nh luËt ®i con tèt §en, xe §en, ... Mét ®Æc ®iÓm n÷a lµ hai
ngêi ch¬i ®Òu ®îc biÕt th«ng tin ®Çy ®ñ vÒ c¸c t×nh thÕ trong
trß ch¬i (kh«ng nh trong ch¬i bµi, ngêi ch¬i kh«ng thÓ biÕt c¸c ng-
êi ch¬i kh¸c cßn nh÷ng con bµi g×). 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Ï
phøc t¹p h¬n vÊn ®Ò t×m kiÕm mµ chóng ta ®· xÐt trong c¸c ch-
¬ng tr íc, 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
biÓu chÝnh x¸c h¬n vÊn ®Ò t×m kiÕm nµy.
VÊn ®Ò ch¬i cê cã thÓ xem nh vÊn ®Ò t×m kiÕm trong
kh«ng gian tr¹ng th¸i. Mçi tr¹ng th¸i lµ mét t×nh thÕ (sù bè trÝ c¸c
qu©n cña hai bªn trªn bµn cê).
• Tr¹ng th¸i ban ®Çu lµ sù s¾p xÕp c¸c qu©n cê cña hai bªn lóc
b¾t ®Çu cuéc ch¬i.
• C¸c to¸n tö lµ c¸c níc ®i hîp lÖ.
• C¸c tr¹ng th¸i kÕt thóc lµ c¸c t×nh thÕ mµ cuéc ch¬i dõng, th -
êng ®îc x¸c ®Þnh bëi mét sè ®iÒu kiÖn dõng nµo ®ã.
• Mét hµm kÕt cuéc (payoff function) øng mçi tr¹ng th¸i kÕt
thóc víi mét gi¸ trÞ nµo ®ã. Ch¼ng h¹n nh cê vua, mçi tr¹ng th¸i
kÕt thóc chØ cã thÓ lµ th¾ng, hoÆc thua (®èi víi Tr¾ng) hoÆc
hßa. Do ®ã, ta cã thÔ x¸c ®Þnh hµm kÕt cuéc lµ hµm nhËn gi¸ trÞ
1 t¹i c¸c tr¹ng th¸i kÕt thóc lµ th¾ng (®èi víi Tr¾ng), -1 t¹i c¸c tr¹ng
th¸i kÕt thóc lµ thua (®èi víi Tr¾ng) vµ 0 t¹i c¸c tr¹ng th¸i kÕt thóc
hßa. Trong mét sè trß ch¬i kh¸c, ch¼ng h¹n trß ch¬i tÝnh ®iÓm,
hµm kÕt cuéc cã thÓ nhËn gi¸ trÞ nguyªn trong kho¶ng [-k, k] víi
k lµ mét sè nguyªn d¬ng nµo ®ã.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 2
Nh vËy vÊn ®Ò cña Tr¾ng lµ, t×m mét d·y níc ®i sao cho xen
kÏ víi c¸c níc ®i cña §en t¹o thµnh mét ®êng ®i tõ tr¹ng th¸i ban
®Çu tíi tr¹ng th¸i kÕt thóc lµ th¾ng cho Tr¾ng.
§Ó thuËn lîi cho viÖc nghiªn cøu c¸c chiÕn lîc chän níc ®i, ta
biÓu diÔn kh«ng gian tr¹ng th¸i trªn díi d¹ng c©y trß ch¬i.
C©y trß ch¬i
C©y trß ch¬i ®îc x©y dùng nh sau. Gèc cña c©y øng víi tr¹ng
th¸i ban ®Çu. Ta sÏ gäi ®Ønh øng víi tr¹ng th¸i mµ Tr¾ng (§en) ®a
ra níc ®i lµ ®Ønh Tr¾ng (§en). NÕu mét ®Ønh lµ Tr¾ng (§en)
øng víi tr¹ng th¸i u, th× c¸c ®Ønh con cña nã lµ tÊt c¶ c¸c ®Ønh
biÓu diÔn tr¹ng th¸i v, v nhËn ®îc tõ u do Tr¾ng (§en) thùc hiÖn
níc ®i hîp lÖ nµo ®ã. Do ®ã, trªn cïng mét møc cña c©y c¸c ®Ønh
®Òu lµ Tr¾ng hÆc ®Òu lµ §en, c¸c l¸ cña c©y øng víi c¸c trn¹g th¸i
kÕt thó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¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 3
Gi¶ sö §en ®i tr íc, ta cã c©y trß ch¬i ®îc biÓu diÔn nh trong
h×nh 4.2.
4.2 ChiÕn lîc Minimax
Qu¸ tr×nh ch¬i cê lµ qu¸ tr×nh Tr¾ng vµ §en thay phiªn nhau
®a ra quyÕt ®Þnh, thùc hiÖn mét trong sè c¸c níc ®i hîp lÖ. Trªn
c©y trß ch¬i, qu¸ tr×nh ®ã sÏ t¹o ra ®êng ®i tõ gèc tíi l¸. Gi¶ sö tíi
mét thêi ®iÓm nµo ®ã, ®êng ®i ®· dÉn tíi ®Ønh u. NÕu u lµ
®Ønh Tr¾ng (§en) th× Tr¾ng (§en) cÇn chän ®i tíi mét trong c¸c
®Ønh §en (Tr¾ng) v lµ con cña u. T¹i ®Ønh §en (Tr¾ng) v mµ
Tr¾ng (§en) võa chän, §en (Tr¾ng) sÏ ph¶i chän ®i tíi mét trong
c¸c ®Ønh Tr¾ng (§en) w lµ con cña v. Qu¸ tr×nh trªn sÏ dõng l¹i khi
®¹t tíi mét ®Ønh lµ l¸ cña c©y.
Gi¶ sö Tr¾ng cÇn t× m níc ®i t¹i ®Ønh u. Níc ®i tèi u cho
Tr¾ng lµ níc ®i dÇn tíi ®Ønh con cña v lµ ®Ønh tèt nhÊt (cho
Tr¾ng) trong sè c¸c ®Ønh con cña u. Ta cÇn gi¶ thiÕt r»ng, ®Õn l-
ît ®èi thñ chän níc ®i tõ v, §en còng sÏ chän níc ®i tèt nhÊt cho
anh ta. Nh vËy, ®Ó chän níc ®i tèi u cho Tr¾ng t¹i ®Ønh u, ta cÇn
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 4
ph¶i 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 c¸c 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}
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 5
end;
function MinVal(u) ;
begin
if u lµ ®Ønh kÕt thóc then MinVal(u) ← f(u)
else MinVal(u) ← min {MaxVal(v) | v lµ ®Ønh con cña u}
end;
Trong c¸c hµm ®Ö quy trªn, f(u) lµ gi¸ trÞ cña hµm kÕt cuéc
t¹i ®Ønh kÕt thóc u. Sau ®©y lµ thñ tôc chän níc ®i cho tr¾ng t¹i
®Ønh u. Trong thñ tôc Minimax(u,v), v lµ biÕn lu l¹i tr¹ng th¸i mµ
Tr¾ng ®· chän ®i tíi tõ u.
procedure Minimax(u, v);
begin
val ← -∞ ;
for mçi w lµ ®Ønh con cña u do
if val VÒ mÆt lÝ thuyÕt, chiÕn lîc Minimax cho phÐp ta t×m ®îc
níc ®i tèi u cho Tr¾ng. Song nã kh«ng thùc tÕ, chóng ta sÏ kh«ng
cã ®ñ thêi gian ®Ó tÝnh ®îc níc ®i tèi u. Bëi v× thuËt to¸n
Minimax ®ßi hái ta 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 10120 ®Ø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(bm ).
§Ó 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.
Hµm ®¸nh gi¸
Hµm ®¸nh gi¸ eval øng víi mçi tr¹ng th¸i u cña trß ch¬i víi mét
gi¸ trÞ sè eval(u), gi¸ trÞ nµy lµ sù ®¸nh gi¸ “®é lîi thÕ” cña tr¹ng
th¸i u. Tr¹ng th¸i u cµng thuËn lîi cho Tr¾ng th× eval(u) lµ sè d-
¬ng cµng lín; u cµng thuËn lîi cho §en th× eval(u) lµ sè ©m cµng
nhá; eval(u) ≈ 0 ®èi víi tr¹ng th¸i kh«ng lîi thÕ cho ai c¶.
ChÊt lîng cña ch¬ng tr×nh ch¬i cê phô thuéc rÊt nhiÒu vµo
hµm ®¸nh gi¸. NÕu hµm ®¸nh gi¸ cho ta sù ®¸nh gi¸ kh«ng chÝnh
x¸c vÒ c¸c tr¹ng th¸i, nã cã thÓ híng dÉn ta ®i tíi tr¹ng th¸i ®îc xem
lµ tèt, nhng thùc tÕ l¹i rÊt bÊt lîi cho ta. ThiÕt kÕ mét hµm ®¸nh
gi¸ tèt lµ mét viÖc khã, ®ßi hái ta ph¶i quan t©m ®Õn nhiÒu
nh©n tè: c¸c qu©n cßn l¹i cña hai bªn, sù bè trÝ cña c¸c qu©n ®ã, ...
ë ®©y cã sù m©u thuÉn gi÷a ®é chÝnh x¸c cña hµm ®¸nh gi¸ vµ
thêi gian tÝnh cña nã. Hµm ®¸nh gi¸ chÝnh x¸c sÏ ®ßi hái rÊt
nhiÒu thêi gian tÝnh to¸n, mµ ngêi ch¬i l¹i bÞ giíi h¹n bëi thêi gian
ph¶i ®a ra níc ®i.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 7
VÝ dô 1: Sau ®©y ta ®a ra mét c¸ch x©y dùng hµm ®¸nh gi¸
®¬n gi¶n cho cê vua. Mçi lo¹i qu©n ®îc g¸n mét gi¸ trÞ sè phï hîp
víi “søc m¹nh” cña nã. Ch¼ng h¹n, mçi tèt Tr¾ng (§en) ®îc cho 1 (-
1), m· hoÆc t îng Tr¾ng (§en) ®îc cho 3 (-3), xe Tr¾ng (§en) ®îc cho
5 (-5) vµ hoµng hËu Tr¾ng (§en) ®îc cho 9 (-9). LÊy tæng gi¸ trÞ
cña tÊt c¶ c¸c qu©n trong mét tr¹ng th¸i, ta sÏ ®îc gi¸ trÞ ®¸nh gi¸
cña tr¹ng th¸i ®ã. Hµm ®¸nh gi¸ nh thÕ ®îc gäi lµ hµm tuyÕn
tÝnh cã träng sè, v× nã cã thÓ biÓu diÔn díi d¹ng:
s1w 1 +s2w 2+. . . +sn w n .
Trong ®ã, w i lµ gi¸ trÞ mçi lo¹i qu©n, cßn si lµ sè qu©n lo¹i ®ã.
Trong c¸ch ®¸nh gi¸ nµy, ta ®· kh«ng tÝnh ®Õn sù bè trÝ cña c¸c
qu©n, c¸c mèi t ¬ng quan gi÷a chóng.
VÝ dô 2: B©y giê ta ®a ra mét c¸ch ®¸nh gi¸ c¸c tr¹ng th¸i
trong trß ch¬i Dodgem. Mçi qu©n Tr¾ng ë mét vÞ trÝ trªn bµn cê
®îc cho mét gi¸ trÞ t¬ng øng trong b¶ng bªn tr¸i h×nh 4.4. Cßn mçi
qu©n §en ë mét vÞ trÝ sÏ ®îc cho mét gi¸ trÞ t ¬ng øng trong b¶ng
bªn ph¶i h×nh 4.4:
Ngoµi ra, nÕu qu©n Tr¾ng 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 (Xem
h×nh 4.5). T¬ng tù, nÕu qu©n §en c¶n trùc tiÕp qu©n Tr¾ng nã
®îc thªm -40 ®iÓm, cßn c¶n gi¸n tiÕp nã ®îc thªm -30 ®iÓm.
¸p dông c¸c qui t¾c trªn, ta tÝnh ®îc gi¸ trÞ cña tr¹ng th¸i ë bªn
tr¸i h×nh 4.6 lµ 75, gi¸ trÞ cña tr¹ng th¸i bªn ph¶i h×nh vÏ lµ -5.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 8
Trong c¸nh ®¸nh gi¸ trªn, ta ®· xÐt ®Õn vÞ trÝ cña c¸c qu©n
vµ mèi t ¬ng quan gi÷a c¸c qu©n.
Mét c¸ch ®¬n gi¶n ®Ó h¹n chÕ kh«ng gian t×m kiÕm lµ, khi
cÇn x¸c ®Þnh níc ®i cho Tr¾ng t¹i u, ta chØ xem xÐt c©y trß ch¬i
gèc u tíi ®é cao h nµo ®ã. ¸p dông thñ tôc Minimax cho c©y trß
ch¬i gèc u, ®é cao h vµ sö dông gi¸ trÞ cña hµm ®¸nh gi¸ cho c¸c l¸
cña c©y ®ã, chóng ta sÏ t×m ®îc níc ®i tèt cho Tr¾ng t¹i u.
4.3 Ph ¬ng ph¸p c¾t côt 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 tr×nh ®é ngêi míi tËp ch¬i!
Khi ®¸nh gi¸ ®Ønh u tíi ®é s©u h, mét thuËt to¸n Minimax
®ßi hái ta ph¶i ®¸nh gi¸ tÊt c¶ c¸c ®Ønh cña c©y gèc u tíi ®é s©u
h. Song ta cã thÓ gi¶m bít sè ®Ønh cÇn ph¶i d¸nh gi¸ mµ vÉn
kh«ng ¶nh hëng g× ®Õn sù ®¸nh gi¸ ®Ønh u. Ph¬ng ph¸p c¾t côt
alpha-beta cho phÐp ta c¾t bá c¸c nh¸nh kh«ng cÇn thiÕt cho sù
®¸nh gi¸ ®Ønh u.
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 9
T t ëng cña kü thuËt c¾t côt alpha-beta lµ nh sau: Nhí l¹i r»ng,
chiÕn lîc t×m kiÕm Minimax lµ chiÕn lîc t×m kiÕm theo ®é s©u.
Gi¶ sö trong qu¸ trÝnh t×m kiÕm ta ®i xuèng ®Ønh a lµ ®Ønh
Tr¾ng, ®Ønh a cã ngêi anh em v ®· ®îc ®¸nh gi¸. Gi¶ sö cha cña
®Ønh a lµ b vµ b cã ngêi anh em u d· ®îc ®¸nh gi¸, vµ gi¶ sö cha
cña b lµ c (Xem h×nh 4.7). Khi ®ã ta cã gi¸ trÞ ®Ønh c (®Ønh
Tr¾ng) Ýt nhÊt lµ gi¸ trÞ cña u, gi¸ trÞ cña ®Ønh b (®Ønh §en)
nhiÒu nhÊt lµ gi¸ trÞ v. Do ®ã, nÕu eval(u) > eval(v), ta kh«ng
cÇn ®i xuèng ®Ó ®¸nh gi¸ ®Ønh a n÷a mµ vÉn kh«ng ¶nh hëng g×
dÕn ®¸nh gi¸ ®Ønh c. Hay nãi c¸ch kh¸c ta cã thÓ c¾t bá c©y con
gèc a. LËp luËn t ¬ng tù cho tr êng hîp a lµ ®Ønh §en, trong tr êng
hîp nµy nÕu eval(u) < eval(v) ta còng cã thÓ c¾t bá c©y con gèc a.
§Ó cµi ®Æt kü thuËt c¾t côt alpha-beta, ®èi víi c¸c ®Ønh n»m
trªn ®êng ®i tõ gèc tíi ®Ønh hiÖn thêi, ta sö dông tham sè α ®Ó
ghi l¹i gi¸ trÞ lín nhÊt trong c¸c gi¸ trÞ cña c¸c ®Ønh con ®· ®¸nh
gi¸ cña mét ®Ønh Tr¾ng, cßn tham sè β ghi l¹i gi¸ trÞ nhá nhÊt
trong c¸c ®Ønh con ®· ®¸nh gi¸ cña mét ®Ønh §en. Gi¸ trÞ cña α
vµ β sÏ ®îc cËp nhËt trong qu¸ tr×nh t×m kiÕm. α vµ β ®îc sö
dông nh c¸c biÕn ®Þa ph¬ng trong c¸c hµm MaxVal(u, α, β) (hµm
x¸c ®Þnh gi¸ trÞ cña ®Ønh Tr¾ng u) vµ Minval(u, α, β) (hµm x¸c
®Þnh gi¸ trÞ cña ®Ønh §en u).
function MaxVal(u, α, β );
begin
if u lµ l¸ cña c©y h¹n chÕ hoÆc u lµ ®Ønh kÕt thóc
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 10
then MaxVal ← eval(u)
else for mçi ®Ønh v lµ con cña u do
{α ← max[ α, MinVal(v, α, β )];
// C¾t bá c¸c c©y con tõ c¸c ®Ønh v cßn l¹i
if α ≥ β then exit};
MaxVal ← α;
end;
function MinVal(u, α, β );
begin
if u lµ l¸ cña c©y h¹n chÕ hoÆc u lµ ®Ønh kÕt thóc
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 ← β ;
end;
ThuËt to¸n t×m níc ®i cho Tr¾ng sö dông kü thuËt c¾t côt
alpha-beta, ®îc cµi ®Æt bëi thñ tôc Alpha_beta(u,v), trong ®ã v lµ
tham biÕn ghi l¹i ®Ønh mµ Tr¾ng cÇn ®i tíi tõ u.
procedure Alpha_beta(u,v);
begin
α ← -∞ ;
β ← ∞;
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 11
for mçi ®Ønh w lµ con cña u do
if α ≤ MinVal(w, α, β ) then
{α ← MinVal(w, α, β );
v ← w;}
end;
VÝ dô. XÐt c©y trß ch¬i gèc u (®Ønh Tr¾ng) giíi h¹n bëi ®é
cao h = 3 (h×nh 4.8). Sè ghi c¹nh c¸c l¸ lµ gi¸ trÞ cña hµm ®¸nh gi¸.
¸p dông chiÕn lîc Minimax vµ kü thuËt c¾t côt, ta x¸c ®Þnh ®îc n-
íc ®i tèt nhÊt cho Tr¾ng t¹i u, ®ã lµ níc ®i dÉn tíi ®Ønh v cã gi¸
trÞ 10. C¹nh mçi ®Ønh ta còng cho gi¸ trÞ cña cÆp tham sè (α, β).
Khi gäi c¸c hµm MaxVal vµ MinVal ®Ó x¸c ®Þnh gi¸ trÞ cña ®Ønh
®ã. C¸c nh¸nh bÞ c¾t bá ®îc chØ ra trong h×nh:
Gi¸o tr×nh TrÝ TuÖ Nh©n T¹o - §inh M¹nh Têng. Ch¬ng 4- Trang 12
