| dbo:abstract
|
- Mit Null-Zug-Suche (nullmove pruning) bezeichnet man eine Forward-Pruningtechnik in Spielbaumsuchverfahren für Zwei-Personen-Nullsummenspielen mit perfekter Information. Speziell in Schachprogrammen hat sich das Nullmove Pruning bewährt. Diese Technik wird benötigt, um die Ermittlung der Spielstärke möglicher Züge bzw. Spielverläufe zu beschleunigen, indem Züge, welche durch unten beschriebenes Verfahren als zu schwach ermittelt werden, von einer weiteren Berechnung ausgeschlossen werden. Ausgehend von der Annahme, dass das Zugrecht einen Vorteil darstellt, wird beim Nullmove Pruning in der Baumsuche (Weiterverfolgung von Stellungsmöglichkeiten, die sich aus einem Zug ergeben) einer Seite ermöglicht, zwei Züge auszuführen. Ist der dadurch erzielte Vorteil nicht groß genug, so war wahrscheinlich schon der erste der beiden Züge minderwertig, und der daraus resultierende Ast des Spielbaums (sämtliche mögliche Spielverläufe, die sich aus der aktuellen Stellung ergeben können) braucht nicht weiter untersucht zu werden, er wird abgeschnitten. Hierdurch können minderwertige Varianten gut und schnell erkannt werden und die zur Verfügung stehende Zeit für die Analyse wichtigerer Varianten genutzt werden. Um insgesamt den Suchaufwand zu reduzieren, muss die Baumsuche, mit der der Null-Zug bewertet wird, mit geringerer Suchtiefe durchgeführt werden, als die Suche zur Bewertung normaler Züge. Eine Reduktion der Suchtiefe um zwei Halbzüge hat sich als vorteilhaft herausgestellt. Manche Programme arbeiten auch mit einer Reduktion um drei Halbzüge, was ein stärkeres Pruning bewirkt, aber taktisch etwas anfälliger ist, da auch vielversprechende Züge mit aussortiert werden können. Das normale Nullmove Pruning versagt in Zugzwangstellungen, da hier die Prämisse nicht erfüllt wird. Es kann ein taktisch nachteiliger Zug durch den Zugzwang erforderlich sein.Da Zugzwangstellungen beim Schach relativ selten vorkommen (am ehesten in bestimmten Endspielsituationen), ist die Fehlerhäufigkeit eher gering. Einige Schachprogrammierer schalten das Nullmove Pruning im Endspiel auch einfach ganz ab, da gerade am Ende nur noch wenige Zweige des Baumes übrig sind und diese eher Zugzwangsstellungen sein können. Bei Spielen wie Dame (engl. checkers) gehören Zugzwangstellungen zum Normalfall, weshalb bei solchen Spielen diese Technik nicht angewandt wird. Eine verbesserte Technik nennt sich Verified Nullmove Pruning und umgeht die Probleme in Zugzwangstellungen. (de)
- Pour les programmes d'échecs, l'heuristique à mouvement nul est une technique heuristique utilisée pour améliorer la vitesse de l'algorithme d'élagage alpha-bêta. Développée par Beal en 1989, puis Goetsch et Campbell en 1990, c'est - impliqué dans le projet Hydra - qui a rendu cette technique accessible aux amateurs de programmation échiquéenne en publiant ses commentaires. (fr)
- In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm. (en)
- Евристика нульового ходу — метод збільшення швидкості алгоритму відсічення альфа-бета в комп'ютерних шахах. Відсічення альфа-бета прискорює виконання алгоритму мінімакс, розпізнаючи точки відсічки. Це точки в ігровому дереві, де поточна позиція така добра для сторони, яка зараз ходить, що найкращий шлях для протилежної сторони — уникнути ходу. Так як такі позиції, можливо, не були результатом найкращої гри, їх та всі гілки ігрового дерева, які ідуть від них, можна проігнорувати. Чим скоріше програма робить відсічку, тим скоріше працює система пошуку. Евристика нульового ходу спроєктована, щоб зменшити час пошуку. Ідея евристики нульового ходу базується на факті, що найкращі ходи в шахах покращують позицію для того, хто їх зробив. Так, якщо гравець втратить право ходу (що недопустимо в шахах) і все ще має позицію, достатню для відсічки, тоді програма майже неодмінно зробить відсічку, якщо цей гравець вже походив. (uk)
- В компьютерных шахматах, эвристика нулевого хода — метод увеличения скорости алгоритма альфа-бета-отсечения. Альфа-бета-отсечение ускоряет выполнение минимаксного алгоритма, распознавая точки отсечения вариантов, представляющихся бесперспективными. Это такая точка в игровом дереве, где текущая позиция настолько выгодна для стороны, которая сейчас ходит, что противоположная сторона будет избегать такую позицию. Поскольку такие позиции не могут быть результатом наилучшей игры, их и все ветви игрового дерева, которые идут от них, можно исключить из расчёта («отсечь»). Чем скорее программа делает отсечку, тем быстрее работает система поиска наилучшего хода. Эвристика нулевого хода направлена на ускорение нахождения предполагаемых точек отсечения при сохранении разумного уровня аккуратности. Идея этой эвристики базируется на том предположении, что наиболее приемлемые ходы в шахматах улучшают позицию того, кто их сделал. Так, если игрок в данной точке может передать очередь хода противнику (сделать нулевой ход, что недопустимо в шахматах) и всё ещё имеет позицию, достаточно сильную для создания отсечения, тогда в данной точке почти наверняка возможно отсечение, поскольку данный игрок в действительности будет делать ход, и его позиция ещё более усилится. Эвристика нулевого хода приводит к неверному результату в ситуациях цугцванга, когда игрок вынужден делать явно невыгодный ход при отсутствии вариантов улучшения своей позиции, поэтому игровые компьютерные программы вынуждены распознавать подобные ситуации и находить способы компенсации такого рода ошибок. В частности «верифицированной эвристикой нулевого хода» называется компьютерная стратегия не полного отсечения таких вариантов, а продолжение поиска, однако с сокращённой глубиной . (ru)
|
| rdfs:comment
|
- Pour les programmes d'échecs, l'heuristique à mouvement nul est une technique heuristique utilisée pour améliorer la vitesse de l'algorithme d'élagage alpha-bêta. Développée par Beal en 1989, puis Goetsch et Campbell en 1990, c'est - impliqué dans le projet Hydra - qui a rendu cette technique accessible aux amateurs de programmation échiquéenne en publiant ses commentaires. (fr)
- In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm. (en)
- Mit Null-Zug-Suche (nullmove pruning) bezeichnet man eine Forward-Pruningtechnik in Spielbaumsuchverfahren für Zwei-Personen-Nullsummenspielen mit perfekter Information. Speziell in Schachprogrammen hat sich das Nullmove Pruning bewährt. Diese Technik wird benötigt, um die Ermittlung der Spielstärke möglicher Züge bzw. Spielverläufe zu beschleunigen, indem Züge, welche durch unten beschriebenes Verfahren als zu schwach ermittelt werden, von einer weiteren Berechnung ausgeschlossen werden. (de)
- В компьютерных шахматах, эвристика нулевого хода — метод увеличения скорости алгоритма альфа-бета-отсечения. Альфа-бета-отсечение ускоряет выполнение минимаксного алгоритма, распознавая точки отсечения вариантов, представляющихся бесперспективными. Это такая точка в игровом дереве, где текущая позиция настолько выгодна для стороны, которая сейчас ходит, что противоположная сторона будет избегать такую позицию. Поскольку такие позиции не могут быть результатом наилучшей игры, их и все ветви игрового дерева, которые идут от них, можно исключить из расчёта («отсечь»). Чем скорее программа делает отсечку, тем быстрее работает система поиска наилучшего хода. (ru)
- Евристика нульового ходу — метод збільшення швидкості алгоритму відсічення альфа-бета в комп'ютерних шахах. Відсічення альфа-бета прискорює виконання алгоритму мінімакс, розпізнаючи точки відсічки. Це точки в ігровому дереві, де поточна позиція така добра для сторони, яка зараз ходить, що найкращий шлях для протилежної сторони — уникнути ходу. Так як такі позиції, можливо, не були результатом найкращої гри, їх та всі гілки ігрового дерева, які ідуть від них, можна проігнорувати. Чим скоріше програма робить відсічку, тим скоріше працює система пошуку. Евристика нульового ходу спроєктована, щоб зменшити час пошуку. (uk)
|
