Шахмат бағдарламаларындағы null move әдісі – alpha–beta pruning алгоритмін жылдамдатуға көмектесетін тиімді техника. Ойын ағашын қысқарту арқылы іздеу жылдамдығын арттырады.
In computer chess programs, the null move heuristic is a heuristic technique used to enhance the speed of the alpha–beta pruning algorithm.
Негізгі себептері
Альфа-бета кесу минимакс алгоритмін кесулерді анықтау арқылы жылдамдатады, ойын ағашындағы осы жағдайға қарсы тараптың ең жақсы ойыны болмаған нүктелер. Мұндай жағдайлар ең жақсы ойынның нәтижесі болмағандықтан, олар және олардан тарайтын ойын ағашының барлық тармақтарын қараудың қажеті жоқ. Бағдарлама қаншалықты жылдам кесулерді анықтаса, іздеу соғұрлым жылдам жүреді. Нөлдік қимыл эвристикасы кесулерді, қалыпты жағдайда қажет болатын күштен кемірек жұмсап, шамалы дәлдікпен болжауға бағытталған. Нөлдік қимыл эвристикасы шахматтағы көптеген ақылға қонымды қимылдар оларды жасаған тараптың позициясын жақсартады деген фактіге негізделген. Сондықтан, егер қозғалыс кезегіндегі ойыншы қозғалу құқығынан бас тартса (немесе шахматтағы заңсыз әрекет – нөлдік қимыл жасаса) және кесуді жасауға жеткілікті күшті позицияда болса, онда қазіргі позиция, егер ағымдағы ойыншы шын мәнінде қозғалса, әлдеқашан кесуді тудырар еді.
Alpha–beta pruning speeds the minimax algorithm by identifying cutoffs, points in the game tree where the current position is so good for the side to move that best play by the other side would have avoided it. Since such positions could not have resulted from best play, they and all branches of the game tree stemming from them can be ignored. The faster the program produces cutoffs, the faster the search runs. The null move heuristic is designed to guess cutoffs with less effort than would otherwise be required, whilst retaining a reasonable level of accuracy. 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 (or make a null 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.
Іске асыру
Нөлдік қозғалыс эвристикасын қолданғанда, компьютерлік бағдарлама ең алдымен қозғалу кезегі келген тараптың мүмкіндігінен бас тартады, содан кейін нәтижесінде алынған позицияда альфа-бета іздеуді, нөлдік қозғалыс эвристикасын қолданбағандағыдан гөрі, көбірек беткейлікке дейін жүргізеді. Егер осы беткейлік іздеуден тоқтату орын алса, онда толық тереңдіктегі іздеу де тоқтатуға әкелер дейді. Беткейлік іздеу терең іздеуден жылдам болғандықтан, тоқтату тезірек табылады, бұл компьютерлік шахмат бағдарламасын үдетіп жібереді. Егер беткейлік іздеу тоқтатуға жетпесе, бағдарлама толық тереңдіктегі іздеуді жүргізуі керек. Бұл тәсіл екі тұжырымға негізделген. Біріншіден, өз кезегінен бас тартудың кемшілігі, беткейлік іздеуді жүргізудің кемшілігінен артық деп есептейді. Егер беткейлік іздеу тым беткей болмаса (практикалық іске асыруда, нөлдік қозғалыс іздеуі әдетте толық іздеуден 2 немесе 3 қадамға дейін беткей болады), бұл көбінесе дұрыс. Екіншіден, нөлдік қозғалыс іздеуі толық іздеудің орнына нөлдік қозғалыс іздеуін жүргізуге кеткен уақытты ақтау үшін жеткілікті жиілікте тоқтатуды қамтамасыз етеді деп есептейді. Іс жүзінде, бұл да көбінесе солай болады.
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. This approach makes two assumptions. First, it assumes that the disadvantage of forfeiting one's turn is greater than the disadvantage of performing a shallower search. Provided the shallower search is not too much shallower (in practical implementation, the null move search is usually 2 or 3 plies shallower than the full search would have been), this is usually true. Second, it assumes that the null move search will produce a cutoff frequently enough to justify the time spent performing null move searches instead of full searches. In practice, this is also usually true.
Тексерілген бос кесу
Цугцванг проблемасын шешуге арналған тағы бір эвристика – Омид Дэвид пен Натан Нетаньяхудың расталған нөлдік қимыл кесу әдісі. Расталған нөлдік қимыл кесуінде, егер беткейлік нөлдік қимыл іздеуі жоғары сәтсіздік көрсетсе, ағымдағы түйінен іздеуді тоқтатудың орнына, іздеу төмендетілген тереңдікпен жалғастырылады.
Another heuristic for dealing with the zugzwang problem is Omid David and Nathan Netanyahu's verified null move pruning. In verified null move pruning, whenever the shallow null move search indicates a fail high, instead of cutting off the search from the current node, the search is continued with reduced depth.