-F÷ÿ SiSiSi +8 Stand 3.1.1989 (*- $m -ÿÿÿÿÿÿÿ= m ist.ÿÿ2.3.3. Die Suche?In S seien die Z}ge zi m|glich. Diese werden nacheinander?ausgef}hrt, und die rekursiven Aufrufe von bestzug6 liefern die?Bewertungen /ai,bi/ und die Tiefen ti zur}ck. Die Genauigkeit?mmin der Untersuchung richtet sich nach dem ungenauesten Teil,also ist die Bewertung: 3 maxa = Max ai, maxb = Max bi, mmin = Min ti/ i i i?Damit hat man eine Bewertung nach 1, und zwar die sch{rfste,,die m|glich ist bei der gew{hlten Suchtiefe.?zbest ist der Zug zi, der zu dem maximalen ai gef}hrt hat. Bei?mehreren Z}gen mit dem gleichen ai wird der genommen, der das?gr|~te bi hat. F}r die Tiefe ist jedoch, wie oben definiert,(nicht ti, sondern das Minimum zu nehmen.ÿÿ2.3.4. Der beta-Abbruch ?Die Suche kann abgebrochen werden, wenn f}r ein ai >= beta?erreicht wird. Das Bewertungsintervall ist dann auf /ai,maxbew/?auszudehnen, denn es wurden ja nicht alle Z}ge untersucht, und?die nicht untersuchten h{tten ja noch das Intervall nach rechts?vergr|~ern k|nnen (die Verkleinerung links {ndert nichts an der?Einschlie~ungseigenschaft des ermittelten Intervalls). Au~erdem?mu~ die Tiefe auf Null zur}ckgesetzt werden, denn die?Untersuchung mit der aktuellen Tiefe ist nicht abgeschlossen?und daher mu~ die Aussage in 1. }ber die Tiefe nicht erf}lltsein.ÿÿÿÿÿ+2.3.5. Die Kombination von Regeln und Suche?Die Regeln haben ein Intervall /a,b/ ergeben. Dann wird?gesucht, das liefert /maxa,maxb/. Das richtige und sch{rfste?Ergebnis ist der Schnitt, die Tiefe ist die von der Sucheermittelte.?Es ist notwendig, maxa vor der Suche mit a zu initialisieren?(und zbest mit nullzug), damit bei zbest kein Zug mit einem?aiÿ<ÿa eingetragen wird, der also die Bewertung a unter?Umst{nden nicht erreicht. Nach der Suche wird dann die obere?Intervallgrenze gegebenenfalls auf b zur}ckgesetzt. Auch beim1Beta-Abbruch darf b statt maxbew genommen werden.?Wenn man Regeln benutzt hat, die auch ein zbest liefern, dann1darf man nat}rlich mit diesem Zug initialisieren.ÿÿÿÿÿÿ02.3.6. Einbeziehen einer gespeicherten Bewertung ?Von einer gespeicherten Bewertung, die die Bedingungen von 2?nicht erf}llt, d}rfen jedoch das Intervall und zbest zur?Initialisierung vor der Suche benutzt werden. Die Tiefe hatkeine Bedeutung. ?Gibt es Ergebnisse von den Regeln und aus der Hash-Tabelle, so0ist letztere wie eine Zugbewertung zu behandeln.ÿÿÿ2.3.7. Ein Punktintervall?Erh{lt man f}r eine Stellung ein Intervall mit a = b, dann kann?man diesem die Tiefe maxm zuordnen. Man kann auch die Suche abbrechen.?Dieser Sonderfall tritt dann auf, wenn ein Zug ein ai liefert,?das nicht kleiner als das b aus den Regeln ist, oder wenn man?ein ai = maxbew findet. Das hei~t z.B.: In einer Stellung S?kann Amzug nicht gewinnen (b=0); f}r einen zi wird?festgestellt, da~ der Gegner nicht gewinnen kann (b=0 f}r den?Gegner, aber ai=0 f}r zi von Amzug; damit ist die StellungRemis und zi ist ein Remiszug.?Der Sonderfall kann aber auch auf treten, wenn f}r S aus den?Regeln ermittelt wurde, da~ Amzug nicht mehr verliert (a=0).?Alle m|glichen Z}ge zeigen, da~ der Gegner nicht verliert (a>=0?f}r den Gegner, bi<=0 f}r Amzug f}r alle i, d.h. maxb=0. Auch?in diesem Beispiel ergibt sich als Schnitt das Punktintervall/0,0/.?Wenn in den beiden Beispielen die Bewertungen des Gegners aus?den Regeln ermittelt wurden, dann hat man durch Kombination von?Regeln aus zwei Ebenen eine eindeutige Stellungsbewertung?ermittelt: zweistufige Intervallbewertung. Die Kombination der?Intervalle wird aber durch den beschriebenen Algorithmus auch(}ber mehrere Stufen hinweg durchgef}hrt.ÿÿÿÿÿÿÿ92.3.8. Das Alpha-Beta-Intervall f}r den rekursiven Aufruf?Interessant f}r den rekursiven Aufruf sind nur Bewertungen?besser als alpha, besser als a aus den Regeln und besser als?das beste der bisher ermittelten ai. Bezeichnet man das Maximum?dieser Werte mit maxab, dann ist das Alpha-Beta-Intervall f}r&den rekursiven Aufruf /-beta, -maxab/.ÿÿ3. Die Validierung(?Das Formulieren und Programmieren der Regeln sind extrem?fehleranf{llige T{tigkeiten. Wer denkt schon daran, da~ es?in unserem einfachen Beispiel bei "sK nicht im Quadrat" noch?Ausnahmen gibt? Jeder kennt die Fehler in Abhandlungen }ber?Endspiele. Beim Codieren werden oft noch weitere Fehler einge-?schleppt. Auch beim Eintragen einzelner Stellungen k|nnen Irr-t}mer vorkommen.(?Aus den genannten Gr}nden sollte ein Programm f}r perfektes?Endspiel validiert werden, d.h. es sollte nachgewiesen werden,>?da~ es immer das richtige Ergebnis liefert! Das kann man infolgender Art durchf}hren:ÿÿÿ3.1. Die Konsistenzpr}fung ?Es werden alle legalen Stellungen nacheinander "gepr}ft". Jede?Stellung S, die mit ihrem "besten" Zug gespeichert ist oder?nach den vorliegenden Regeln entschieden wird, wird bei dieser?]berpr}fung durch "Suche" getestet. Es wird zuerst der "beste"?Zug ausgef}hrt, dann wird im Suchbaum vorausgeschaut. Dabei er-?reicht man andere Stellungen z.B. solche, die nicht durch Spei-?chern oder Regeln entschieden werden. Aber beendet werden alle?Zweige durch entschiedene Stellungen. Diese bezeichnen wir als?die Stellungen, auf die sich S "abst}tzt". Man erreicht eventu-?ell auch ]berg{nge in andere Endspiele, n{mlich nach Schlagz}-?gen oder Umwandlungen. Es wird hier vorausgesetzt, da~ alle er-?reichten anderen Endspiele schon validiert sind, also perfektsind.?Als Ergebnis dieser Suche ergibt sich f}r jede zu untersuchende?Stellung das Ergebnis Gewinn/Remis/Verlust. Dieses mu~ mit der4aus den Regeln ermittelten Bewertung }bereinstimmen!?Falls das gespeicherte Ergebnis bei S nicht Gewonnen ist, kann?es noch sein, da~ zwar die Bewertung f}r den angegebenen "be-?sten" Zug richtig ist, da~ aber ein m|glicher besserer Zug beim?Entwerfen }bersehen wurde. Man mu~ also zus{tzlich von S aus>suchen und pr}fen, ob nicht ein besseres Ergebnis m|glich ist.?Das Validieren der Stellungen, die zwar entschieden wurden, bei?denen aber auf das Ermitteln des besten Zuges verzichtet wurde,?geschieht auf dieselbe Art, es wird aber sofort in S mit derSuche begonnen.?Bei allen Stellungen, die nicht durch A oder C entschieden wer-?den, mu~ man beim Pr}fen nur kontrollieren, ob die Suche mit?"ertr{glichem Aufwand" zum Ziel f}hrt. Wir nehmen bei allem an,?da~ wir ein korrektes Programm f}r die Suche haben, das alle5Besonderheiten, wie Stellungswiederholung usw. kennt.(3Wir f}hren also folgenden Validierungsproze~ durch:( F}r alle Felder f}r den wK($ F}r alle Felder f}r den sK(( F}r alle Felder f}r den wB(1 F}r Wei~ und f}r Schwarz am Zug() Wenn Stellung legal(% dann validiere!?Danach st}tzen sich alle Stellungen nur noch auf validierte?Stellungen ab, und durch Suche wurde das durch Speichern oder?Regeln festgelegte Ergebnis best{tigt. Das gesamte Endspiel istkommen, was richtig beurteilt ist und das ist der Widerspruch!?Da alle durch Regeln entschiedenen Gewinn- und Verluststellun-?gen (nach erfolgreicher Validierung) richtig beurteilt sind,?mu~ man keine auf Remis entschiedenen Stellungen auf Kreisfrei-?heit untersuchen; diese k|nnen ja allenfalls falsch beurteilte?Gewinn- oder Verluststellungen sein, was gerade ausgeschlossenwurde.ÿÿ3.4. Remiskreise?Abst}tzungskreise k|nnen also nur bei falsch beurteilten Remis-?stellungen auftreten. Nach diesen mu~ dann aber auch gesuchtwerden.?Das bedeutet aber, da~ bei der Validierung alle mit Gewinn oder?Verlust beurteilten Stellungen in der in 3.2. beschriebenen Art?auf Kreisfreiheit untersucht werden m}ssen, es k|nnten ja?falsch beurteilte Gewinnstellungen sein. Entdeckt man einen?Kreis, der vom vermeintlichen Verlierer erzwungen werden kann,so liegt ein Fehler vor.?Es m}ssen schon stark einschr{nkende Voraussetzungen erf}llt?sein, damit ein falsch beurteilter Remiskreis auf die Bewertung?anderer Stellungen keinen Einflu~ haben kann, also bei der Validierung nicht entdeckt wird:ýÿ?1) Alle anderen wei~en Z}ge d}rfen nicht zum Gewinn f}hren,(sonst w{re die Beurteilung nicht falsch.ýÿ82) Alle anderen schwarzen Z}ge m}ssen auch (wirklich) zu9Verlust f}hren, sonst w{re die Beurteilung nicht falsch. ýÿ?3) Keine Remisstellung mit W am Zug darf in den Kreis f}hren,'sonst w{re auch diese falsch beurteilt.ýÿ?4) Jede Remisstellung mit S am Zug hat auch eine