About: SSS*     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatAlgorithms, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/c/3m6oTu7e89

SSS* is a search algorithm, introduced by George 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 . 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 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 the original game tree. SSS* never examines a node that alpha-beta pruning would

AttributesValues
rdf:type
rdfs:label
  • Algoritmo SSS (es)
  • SSS* (pl)
  • SSS* (en)
rdfs:comment
  • El algoritmo SSS* (SSS estrella) se clasifica dentro de los algoritmos de búsqueda basada en grafos, de manera similar a como lo hacen los algoritmo A* o minimax. Se diferencia del algoritmo alfa-beta en que utiliza una lista como estructura. Se genera un árbol en los que los nodos son de tipo MIN o MAX. Cada nodo del árbol es una tupla (N, s, h): * N: Nombre * s: Estado (vivo o solucionado) * h: Valor de la solución ( inicialmente menos infinito si se quiere maximizar la función) (es)
  • SSS* is a search algorithm, introduced by George 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 . 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 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 the original game tree. SSS* never examines a node that alpha-beta pruning would (en)
  • SSS* jest zoptymalizowanym algorytmem do gier dwuosobowych (algorytmem typu min-max)autorstwa G. Stockmanna. Algorytm ten jest co najmniej tak dobry jak algorytm alfa-beta, tzn. nigdy nie przegląda wierzchołka ominiętego przez mogąc dodatkowo poczynić dalsze oszczędności. OPEN := { (e,L,inf) } powtarzaj zdejmij element p=(J,s,h) z wierzchołka OPEN jeśli J=e i s=S, zakończ działanie algorytmu, zwracając h w przeciwnym przypadku zastosuj operator Gamma dla p Operator dla zdefiniowany jest następująco: (pl)
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • El algoritmo SSS* (SSS estrella) se clasifica dentro de los algoritmos de búsqueda basada en grafos, de manera similar a como lo hacen los algoritmo A* o minimax. Se diferencia del algoritmo alfa-beta en que utiliza una lista como estructura. Se genera un árbol en los que los nodos son de tipo MIN o MAX. Cada nodo del árbol es una tupla (N, s, h): * N: Nombre * s: Estado (vivo o solucionado) * h: Valor de la solución ( inicialmente menos infinito si se quiere maximizar la función) (es)
  • SSS* is a search algorithm, introduced by George 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 . 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 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 the original game tree. 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, 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). However, , Jonathan Schaeffer, Wim Pijls and Arie de Bruin have shown that a sequence of null-window alpha-beta calls is equivalent to SSS* (i.e., it expands the same nodes in the same order) when alpha-beta is used with a transposition table, as is the case in all game-playing programs for chess, checkers, etc. Now the storing and sorting of the OPEN list were no longer necessary. This allowed the implementation of (an algorithm equivalent to) SSS* in tournament quality game-playing programs. Experiments showed that it did indeed perform better than Alpha-Beta in practice, but that it did not beat NegaScout. The reformulation of a best-first algorithm as a sequence of depth-first calls prompted the formulation of a class of null-window alpha-beta algorithms, of which MTD(f) is the best known example. (en)
  • SSS* jest zoptymalizowanym algorytmem do gier dwuosobowych (algorytmem typu min-max)autorstwa G. Stockmanna. Algorytm ten jest co najmniej tak dobry jak algorytm alfa-beta, tzn. nigdy nie przegląda wierzchołka ominiętego przez mogąc dodatkowo poczynić dalsze oszczędności. Dana jest kolejka priorytetowa OPEN przechowująca stany gdzie – wierzchołek (używana jest notacja Deweya, oznacza korzeń), – stan rozwiązania dla ( oznaczawierzchołek zamknięty (rozwiązany), a otwarty (nierozwiązany)) oraz – wartość rozwiązania dla OPEN jest posortowana zgodnie z malejącą wartością W przypadku wielu węzłów o tej samej mierze preferowane są wierzchołki położone po lewej stronie drzewa. OPEN := { (e,L,inf) } powtarzaj zdejmij element p=(J,s,h) z wierzchołka OPEN jeśli J=e i s=S, zakończ działanie algorytmu, zwracając h w przeciwnym przypadku zastosuj operator Gamma dla p Operator dla zdefiniowany jest następująco: jeżeli s=L jeżeli J jest wierzchołkiem terminalnym (1.) dodaj (J,S,min(h,wartość(J))) do OPEN w p.p. jeżeli J jest wierzchołkiem typu MIN (2.) dodaj (J.1,L,h) do OPEN w p.p. (3.) dla j=1..liczba_potomków(J) dodaj (J.j,L,h) do OPEN w p.p. jeżeli J jest wierzchołkiem typu MIN (4.) dodaj (rodzic(J),S,h) do OPEN usuń z OPEN wszystkie stany zawierające następników wierzchołka rodzic(J) w p.p. jeżeli J=rodzic(J).k i k=liczba_potomków(rodzic(J)) (5.) dodaj (rodzic(J),S,h) do OPEN w p.p. (6.) dodaj (rodzic(J).(k+1),L,h) do OPEN (pl)
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage disambiguates of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git147 as of Sep 06 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 50 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software