الگوریتم 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 
George Stockman's website

الگوریتم‌های جستجو