Null-Move Pruning

Moderator: Einführung in die Künstliche Intelligenz

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Null-Move Pruning

Beitrag von Dreamdancer »

Was soll mir S.93 der Folie Game Playing - Adversarial Search sagen?
Was ist unter dem Punkt "Idea" die Idee?
Was ist unter Approach der Ansatz? Einen Null-Move hinzufügen? Wieso, wenn ich ihn bei vielen Spielen sowieso nicht machen darf?
Was ist unter "Danger" die Gefahr? Ich dachte, ich füge ja eben einen Null-Move hinzu?

Grüße und Danke jetzt schonmal

Benutzeravatar
klospatz
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 230
Registriert: 16. Dez 2003 14:01
Wohnort: Darmstadt
Kontaktdaten:

Re: Null-Move Pruning

Beitrag von klospatz »

Dreamdancer hat geschrieben:Was soll mir S.93 der Folie Game Playing - Adversarial Search sagen?
Was ist unter dem Punkt "Idea" die Idee?
"The null-move heuristic is based on the fact that most reasonable chess moves improve the position for the side that played them. So, if the player whose turn it is to move can forfeit the right to move (an illegal action in chess) and still have a position strong enough to produce a cutoff, then the current position would almost certainly produce a cutoff if the current player actually moved.

In employing the null-move heuristic, the computer program first forfeits the turn of the side whose turn it is to move, and then performs an alpha-beta search on the resulting position to a shallower depth than it would have searched the current position had it not used the null move heuristic. If this shallow search produces a cutoff, it assumes the full-depth search in the absence of a forfeited turn would also have produced a cutoff. Because a shallow search is faster than deeper search, the cutoff is found faster, accelerating the computer chess program. If the shallow search fails to produce a cutoff, then the program must make the full-depth search."
(aus wikipedia)
Dreamdancer hat geschrieben:Was ist unter Approach der Ansatz? Einen Null-Move hinzufügen? Wieso, wenn ich ihn bei vielen Spielen sowieso nicht machen darf?
IMHO nur eine implemierungstechnische frage. man darf einen nullzug zwar regulaererweise nicht machen, aber du kannst in deiner suche den spieler den nullzug trotzdem durchfueheren lassen und anschliessend deine suche auf der resultierenden stellung starten.
Dreamdancer hat geschrieben:Was ist unter "Danger" die Gefahr? Ich dachte, ich füge ja eben einen Null-Move hinzu?
den satz in den folien finde ich zum verstaendnis auch eher suboptimal. wahrscheinlich soll damit nur angedeutet werden, dass bei stellungen in denen tatsaechlich kein zug der beste zug ist (fuer beispiele dazu siehe schachbretter hier) deine suche trotzdem einen zug machen soll.

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Beitrag von Dreamdancer »

Ah! Jetzt ist mir zumindest der Sinn der Existenz eines solchen Schrittes klar.
Vielen Dank.

Benutzeravatar
Rodent Bait
Mausschubser
Mausschubser
Beiträge: 91
Registriert: 26. Apr 2005 14:50
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Rodent Bait »

Was ist unter "Danger" die Gefahr? Ich dachte, ich füge ja eben einen Null-Move hinzu?
Das Problem bei Stellungen, in denen kein Zug der beste Zug ist (Zugzwang-Stellungen), ist offenbar, dass sie besser bewertet werden, als sie tatsächlich sind (denn den guten Null-Move kann man ja nicht machen). Diese fehlerhafte Bewertung kann dann dazu führen, dass sich der Agent, der nach dieser Heuristik sucht, sich selbst in eine Zugzwang-Falle bringt, weil er diese Stellung zu gut bewertet hat. So habe ich das zumindest verstanden.

Antworten

Zurück zu „Einführung in die Künstliche Intelligenz“