SSS*

SSS*

SSS* is a search algorithm, introduced by Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm.

SSS* is based on the notion of solution trees. Informally, a solution tree can be formed from any arbitrary game tree by pruning the number of branches at each MAX node to one. Such a tree represents a complete strategy for MAX, since it specifies exactly one MAX action for every possible sequence of moves might be made by the opponent. Given a game tree, SSS* searches through the space of partial solution trees, gradually analyzing larger and larger subtrees, eventually producing a single solution tree with the same root and Minimax value as . SSS* never examines a node that alpha-beta pruning would prune, and may prune some branches that alpha-beta would not. Stockman speculated that SSS* may therefore be a better general algorithm than alpha-beta. However, Steve Rozen and Judea Pearl have shown that the savings in the number of positions that SSS* evaluates relative to alpha/beta is limited and generally not enough to compensate for the increase in other resources (e.g., the storing and sorting of a list of nodes made necessary by the best-first nature of the algorithm).

External links

* [http://www.cse.msu.edu/~stockman/ George Stockman's website]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • SSS — may stand for:* Saffir Simpson Hurricane Scale, or Saffir Simpson Scale, a system for measuring intensity of tropical cyclones * Same Store Sales, a measure to gauge the development of retail revenues * Satellite Syndicated Systems, a company… …   Wikipedia

  • SSS-PC — is an operating system kernel with powerful scalability and load balancing capabilities, created in Japan by Takashi MATSUMOTO, a professor at the University of Tokyo. It has powerful functions for clustering, parallel processing and targeting… …   Wikipedia

  • SSS — steht als Abkürzung für vielerlei Dinge: Behörden/Organisationen Selective Service System, eine Behörde in den Vereinigten Staaten zur Verwaltung der Wehrpflichtigen State Security Service, Nachrichtendienst Nigerias Societas Sanctissimi… …   Deutsch Wikipedia

  • SSS — Saltar a navegación, búsqueda SSS son las siglas de Script del lado del servidor, en inglés Server side scriping, un método para crear webs dinámicas. Servicio de Seguro Social (1952 1982) de Chile Selective Service System de EE.UU. Soraya Sáenz… …   Wikipedia Español

  • sss… — [sss] Interj. ❖ ♦ Interjection imitant un sifflement et exprimant, selon la manière dont elle est modulée, l approbation, l incrédulité (var. : ts ts), etc. 0 « Ssssss » Sifflement prolongé par quoi l on montre à l interlocuteur que l importance… …   Encyclopédie Universelle

  • şşş — v. ş Trimis de siveco, 10.08.2004. Sursa: Dicţionar ortografic  şşş v. ş3 Trimis de gall, 31.12.2007. Sursa: DOOM 2 …   Dicționar Român

  • ššš — jst. Ššš! Tyliaũ! …   Bendrinės lietuvių kalbos žodyno antraštynas

  • sss — fonosimb. var. → sst …   Dizionario italiano

  • SSS — abbrev. Selective Service System …   English World dictionary

  • SSS — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Ne doit pas être confondu avec SS ni SSSS.   Sigles d’une seule lettre …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”