الگوریتم sss*
الگوریتم *sss به شرح زیر است.
مقدمه
- sss یک الگوریتم جستجو است، که به وسیلهٔ جرج استکمن در سال ۱۹۷۹ معرفی شدهاست که با هدایت کردن یک حالت فضا از درخت بازی بهترین اولین که شبیه الگوریتم جستجو آ* است، میگذرد.
مبنا *sss مفهوم درخت راه حل است. یک درخت راه حل میتواند از هر درخت بازی که به وسیلهٔ هرس تعدادی راس در هر یک از راس بیشینه به یک، حالت بگیرد. چنین درختی نشان دهنده یک استراتژی کامل برای بیشینه است که آن مشخص میکند دقیقاً یک حالت بیشینه برای هر حرکت توالی ممکن، ممکن است توسط حریف ساخته شود. با توجه به یک درخت بازی، جستجو *SSS از طریق فضای جزئی درختان راه حل، به تدریج تجزیه و تحلیل زیر درختان بزرگتر و بزرگتر، سرانجام یک درخت راه حل تنها با همان ریشه و ارزش مینیماکس به عنوان درخت بازی اصلی تولید میشود. *SSS هرگز به بررسی یک گره که هرس آلفا بتا باید آن را هرس کند، و ممکن است شعبهایی که آلفا بتا نباید هرس کند را هرس میکند. استکمن بر این باور است که *SSS ممکن است یک الگوریتم کلی بهتر از آلفا بتا باشد اما، استیو روزن و جوده آ پیرل نشان دادهاند که صرفه جویی در تعداد موقعیتهای که *SSS ارزیابی میکند نسبت به آلفا / بتا محدود است و بهطور کلی به اندازه کافی نیست برای جبران افزایش در منابع دیگر (مانند ذخیره و مرتب کردن آرایهای از راسها که ساخته شدهاند به وسیلهٔ الگوریتم بهترین-اولین).
الگوریتم
در اینجا یک صف اولویت دار بنام OPEN است که حالتهای یا راسها را ذخیره میکند، جایی که J مشخصکننده راس،حالتی که راس J (راس زنده است، به این معنا که هنوز حل نشدهاست و S راس ای است که حل شده است)،ارزش حل شدن یک راس است. آیتم در OPEN نزولی مرتب شدهاند به وسیلهٔ ارزش H. اگر بیشتر از یک راس دارای ارزش H باشند، a چپترین راس در این درخت انتخاب میشود.
کد سودو
}(OPEN := { (e,L,inf
while (true) // repeat until stopped
pop an element p=(J,s,h) from the head of the OPEN queue
if J == e and s == S
STOP the algorithm and return h as a result
else
apply Gamma operator for p
operator for is defined in the following way:
if s == L if J is a terminal node (1.) add (J,S,min(h,value(J))) to OPEN else if J is a MIN node (2.) add (J.1,L,h) to OPEN else (3.) for j=1..number_of_children(J) add (J.j,L,h) to OPEN else if J is a MIN node (4.) add (parent(J),S,h) to OPEN remove from OPEN all the states that are associated with the children of parent(J) else if is_last_child(J) // if J is the last child of parent(J) (5.) add (parent(J),S,h) to OPEN else (6.) add (parent(J). (k+1),L,h) to OPEN // add state associated with the next child of parent(J) to OPEN
کد به زبان c
}(int SSS* (node n; int bound
;(push (n, LIVE, bound
}(while ( true
;(pop (node
}(switch ( node.status
:case LIVE
(if (node == LEAF
;((insert (node, SOLVED, min(eval(node),h
(if (node == MIN_NODE
;(push (node.1, LIVE, h
(if (node == MAX_NODE
(--for (j=w; j; j
;(push (node.j, LIVE, h
;break
:case SOLVED
(if (node == ROOT_NODE
;(return (h
}(if (node == MIN_NODE
;((purge (parent(node
;(push (parent(node), SOLVED, h
{
}(if (node == MAX_NODE
(if (node has an unexamined brother
;(push (brother(node), LIVE, h
else
;(push (parent(node), SOLVED, h
{
;break
{
{
{
منابع
- http://en.wikipedia.org/w/index.php?title=SSS*&oldid=453234268
- http://en.wikipedia.org/wiki/A*_search_algorithm
- http://en.wikipedia.org/wiki/Alpha-beta_pruning
پیوند به بیرون
- Chess Programming Wiki بایگانیشده در ۲۸ سپتامبر ۲۰۰۸ توسط Wayback Machine
- George Stockman's website