الگوریتم sss*

الگوریتم *sss به شرح زیر است.

مقدمه

• sss یک الگوریتم جستجو است, که بوسیله جرج استکمن در سال 1979 معرفی شده است که با هدایت کردن یک حالت فضا از درخت بازی بهترین اولین که شبیه الگوریتم جستجو آ* است, میگذرد.

مبنا *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

$\Gamma$ operator for $p=(J,s,h)$ 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
• George Stockman's website