Proof-Number-Suche

Proof-Number-Suche

Proof-Number-Suche (kurz: PN-Suche) bzw. Beweiszahlsuche ist ein Spielbaum-Suchalgorithmus, erfunden von Victor Allis, ursprünglich zur Lösung der Spiele Vier gewinnt, Qubic (1990). Anwendungen sind hauptsächlich in der Endspiel-Lösung und für Teilziele während des Spiels.

Zur Anwendung des Algorithmus wird ein binäres Ziel definiert (z. B. Spieler am Zug gewinnt) und der Spielbaum in einen Und-Oder-Baum transformiert. Dies ist einfach möglich, indem maximierende Knoten als ODER-Knoten betrachtet werden und minimierende Knoten als UND-Knoten (Vgl Minimax-Algorithmus).

Zahlen für den Beweis (Beweiszahlen) und Gegenbeweis (Widerlegzahlen) von Knoten (proof and disproof numbers) werden in den Knoten geführt und während der Suche aktualisiert. Sie sind definiert als untere Schranke der noch zu expandierenden Knoten, um einen (Gegen-)beweis zu erreichen.

Durch Auswahl der meist-beweisenden/meist-widerlegenden Knoten für die nächste Expansion wird eine effiziente Suche generiert.

Wegen der hohen Zahl der erzeugten Knoten ist die PN-Suche durch den verfügbaren Arbeitsspeicher begrenzt. Es existieren jedoch Varianten, die diese Limitierung lockern und deutlich mehr Positionen bewerten können, z. B. PN^2, PDS-PN[1].

Quellen

  1. ↑ Mark H.M. Winands, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik: PDS-PN: A New Proof-Number Search Algorithm. (PDF) In: Lecture Notes in Computer Science. 2003.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Commander (song) — Commander …   Wikipedia

  • Mersenne-Primzahl — Poststempel mit der 23. Mersenne Primzahl, gefunden 1963 an der UIUC von Donald B. Gillies. Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die ersten acht Mersenne Zahlen Mn… …   Deutsch Wikipedia

  • Relapse (album) — Relapse Studio album by Eminem Released May 15, 2009 (see …   Wikipedia

  • Hamas — حركة المقاومة الاسلامية …   Wikipedia

  • Austrian legislative election, 2008 — Infobox Election election name = Austrian legislative election, 2008 country = Austria type = parliamentary ongoing = no previous election = Austrian legislative election, 2006 previous year = 2006 previous MPs = next election = next year = seats …   Wikipedia

  • Believe (Cher song) — Believe Single by Cher from the album Believe B side …   Wikipedia

  • Das neue Leben (Roman) — Die Hagia Sophia in Istanbul Das neue Leben (türkischer Originaltitel: Yeni Hayat) ist ein 1994 erschienener Roman des türkischen Schriftstellers Orhan Pamuk. Sein Titel spielt auf Dantes gleichnamiges Werk (ital. Vita Nova) an.[1] Der 22 Jahre… …   Deutsch Wikipedia

  • Heinrich Goebel — Heinrich Göbel, Fotografie aus New York Heinrich Göbel (* 20. April 1818 in Springe; † 4. Dezember 1893 in New York; nach 1849 auch als Henry Goebel bekannt) war ein Feinmechaniker deutscher Herkunft, der 1865 US Staatsbürger wurde. Heinrich… …   Deutsch Wikipedia

  • Henry Goebel — Heinrich Göbel, Fotografie aus New York Heinrich Göbel (* 20. April 1818 in Springe; † 4. Dezember 1893 in New York; nach 1849 auch als Henry Goebel bekannt) war ein Feinmechaniker deutscher Herkunft, der 1865 US Staatsbürger wurde. Heinrich… …   Deutsch Wikipedia

Share the article and excerpts

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