نمایش مبدأ برای الگوریتم 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

<math>\Gamma</math> operator for <math>p=(J,s,h)</math> 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 ==
<syntaxhighlight lang="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
      {
   {
{
</syntaxhighlight>

== منابع ==
* 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
{{پانویس}}

== پیوند به بیرون ==
*[http://chessprogramming.wikispaces.com/SSS*+and+Dual* Chess Programming Wiki] {{Webarchive|url=https://web.archive.org/web/20080928225048/http://chessprogramming.wikispaces.com/SSS%2A+and+Dual%2A |date=28 سپتامبر 2008 }}
*[http://www.cse.msu.edu/~stockman/ George Stockman's website]

[[رده:الگوریتم‌های جستجو]]