Proof-number search (original) (raw)
Proof-Number-Suche (kurz: PN-Suche) bzw. Beweiszahlsuche ist ein Spielbaum-Suchalgorithmus, der von Victor Allis, ursprünglich zur Lösung der Spiele Vier gewinnt und Qubic, erfunden wurde. Anwendungen sind hauptsächlich die Endspiellösung und Teilziele während des Spiels. Das Verfahren eignet sich besonders für Probleme, deren Lösung eine hohe Zahl an Zügen erfordern, auf die der verteidigende Spieler jeweils nur eine geringe Zahl an sinnvollen Erwiderungen hat (forcierte Züge). Während bei der klassischen Alpha-Beta-Suche der gesamte Spielbaum bis zu einer vorher festgelegten Tiefe ausgewertet wird, können bei der PN-Suche auch frühzeitig beweisende oder widerlegende Teilbäume gefunden werden, die zwar tief sind, aber wenig verzweigen. (Genauer: Für deren Beweis oder Widerlegung nur vergl
| Property | Value |
|---|---|
| dbo:abstract | Proof-Number-Suche (kurz: PN-Suche) bzw. Beweiszahlsuche ist ein Spielbaum-Suchalgorithmus, der von Victor Allis, ursprünglich zur Lösung der Spiele Vier gewinnt und Qubic, erfunden wurde. Anwendungen sind hauptsächlich die Endspiellösung und Teilziele während des Spiels. Das Verfahren eignet sich besonders für Probleme, deren Lösung eine hohe Zahl an Zügen erfordern, auf die der verteidigende Spieler jeweils nur eine geringe Zahl an sinnvollen Erwiderungen hat (forcierte Züge). Während bei der klassischen Alpha-Beta-Suche der gesamte Spielbaum bis zu einer vorher festgelegten Tiefe ausgewertet wird, können bei der PN-Suche auch frühzeitig beweisende oder widerlegende Teilbäume gefunden werden, die zwar tief sind, aber wenig verzweigen. (Genauer: Für deren Beweis oder Widerlegung nur vergleichsweise wenig Terminalpositionen ausgewertet werden müssen.) (de) Proof-number search (short: PN search) is a game tree search algorithm invented by Victor Allis, with applications mostly in , but also for sub-goals during games. Using a binary goal (e.g. first player wins the game), game trees of two-person perfect-information games can be mapped to an and–or tree. Maximizing nodes become OR-nodes, minimizing nodes are mapped to AND-nodes. For all nodes proof and disproof numbers are stored, and updated during the search. To each node of the partially expanded game tree the proof number anddisproof number are associated. A proof number represents the minimum number of leafnodes which have to be proved in order to prove the node. Analogously, a disproofnumber represents the minimum number of leaves which have to be disprovedin order to disprove the node. Because the goal of the tree is to prove a forcedwin, winning nodes are regarded as proved. Therefore, they have proof number0 and disproof number ∞. Lost or drawn nodes are regarded asdisproved. They have proof number ∞ and disproof number0. Unknown leaf nodes have a proof and disproof number of unity. The proof number of an internal AND node is equal to the sum ofits children's proof numbers, since to prove an AND node all the children haveto be proved. The disproof number of an AND node is equal to the minimum ofits children's disproof numbers. The disproof number of an internal OR node isequal to the sum of its children's disproof numbers, since to disprove an OR nodeall the children have to be disproved. Its proof number is equal to the minimumof its children's proof numbers. The procedure of selecting the most-proving nodeto expand is the following. We start at the root. Then, at each OR node the childwith the lowest proof number is selected as successor, and at each AND node thechild with the lowest disproof number is selected as successor. Finally, when aleaf node is reached, it is expanded and its children are evaluated. The proof and disproof numbers represent lower bounds on the number of nodes to be evaluated to prove (or disprove) certain nodes. By always selecting the most proving (disproving) node to expand, an efficient search is generated. Some variants of proof number search like dfPN, PN2, PDS-PN have been developed to address the quite big memoryrequirements of the algorithm. (en) |
| dbo:wikiPageExternalLink | https://webdocs.cs.ualberta.ca/~mmueller/ps/ICGA2012PNS.pdf |
| dbo:wikiPageID | 23073520 (xsd:integer) |
| dbo:wikiPageLength | 3495 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1077795516 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Victor_Allis dbc:Search_algorithms dbc:Game_artificial_intelligence dbc:Graph_algorithms dbr:Game_tree dbr:And–or_tree dbr:Search_algorithm dbr:Perfect-information_game dbr:Endgame_solver |
| dbp:wikiPageUsesTemplate | dbt:Short_description |
| dct:subject | dbc:Search_algorithms dbc:Game_artificial_intelligence dbc:Graph_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | Proof-Number-Suche (kurz: PN-Suche) bzw. Beweiszahlsuche ist ein Spielbaum-Suchalgorithmus, der von Victor Allis, ursprünglich zur Lösung der Spiele Vier gewinnt und Qubic, erfunden wurde. Anwendungen sind hauptsächlich die Endspiellösung und Teilziele während des Spiels. Das Verfahren eignet sich besonders für Probleme, deren Lösung eine hohe Zahl an Zügen erfordern, auf die der verteidigende Spieler jeweils nur eine geringe Zahl an sinnvollen Erwiderungen hat (forcierte Züge). Während bei der klassischen Alpha-Beta-Suche der gesamte Spielbaum bis zu einer vorher festgelegten Tiefe ausgewertet wird, können bei der PN-Suche auch frühzeitig beweisende oder widerlegende Teilbäume gefunden werden, die zwar tief sind, aber wenig verzweigen. (Genauer: Für deren Beweis oder Widerlegung nur vergl (de) Proof-number search (short: PN search) is a game tree search algorithm invented by Victor Allis, with applications mostly in , but also for sub-goals during games. Using a binary goal (e.g. first player wins the game), game trees of two-person perfect-information games can be mapped to an and–or tree. Maximizing nodes become OR-nodes, minimizing nodes are mapped to AND-nodes. For all nodes proof and disproof numbers are stored, and updated during the search. (en) |
| rdfs:label | Proof-Number-Suche (de) Proof-number search (en) |
| owl:sameAs | freebase:Proof-number search yago-res:Proof-number search wikidata:Proof-number search dbpedia-de:Proof-number search dbpedia-sr:Proof-number search https://global.dbpedia.org/id/215bZ |
| prov:wasDerivedFrom | wikipedia-en:Proof-number_search?oldid=1077795516&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Proof-number_search |
| is dbo:wikiPageWikiLink of | dbr:Victor_Allis dbr:3D_tic-tac-toe dbr:And–or_tree |
| is foaf:primaryTopic of | wikipedia-en:Proof-number_search |