Кіріспе
Минимакс ойын ағашын іздеудің вариациясы. Негамакс іздеуі – екі ойыншының ойынының нөлдік қосынды қасиеттеріне сүйене отырып, минимакс іздеуінің бір түрі. Бұл алгоритм 1 = min(a, b) = max(b, a) фактісіне сүйенеді, бұл минимакс алгоритмін іске асыруды жеңілдетеді. Нақтырақ айтқанда, мұндай ойында А ойыншысы үшін позицияның мәні В ойыншысы үшінгі мәннің теріс шамасына тең болады. Осылайша, қозғалыс жасап отырған ойыншы, қозғалыс нәтижесінде туындаған мәннің теріс шамасын барынша арттыратын қозғалысты іздейді: бұл ұрпақ позициясы міндетті түрде қарсылас бағалаған болуы керек. Жоғарыдағы аргумент А немесе В қозғалыс жасап жатса да жұмыс істейді. Бұл екі позицияны да бағалау үшін бір процедураны қолдануға болады дегенді білдіреді. Бұл минимакс-тен кодтауды жеңілдетеді, себебі минимакс А ең жоғары бағаланған ұрпақты, ал В ең төмен бағаланған ұрпақты таңдауын талап етеді. Оны негаскаутпен шатастыруға болмайды, ол 1980-ші жылдары ашылған альфа-бета кесуді тиімді пайдалану арқылы минимакс немесе негамакс мәнін жылдам есептеуге арналған алгоритм. Альфа-бета кесудің өзі, позицияның минимакс немесе негамакс мәнін қызығушылық тудырмайтын белгілі бір позицияларды іздеуден аулақ болу арқылы жылдам есептеудің бір тәсілі екенін атап өткен жөн. Көптеген қарсыластық іздеу жүйелері негамакс іздеуінің кейбір түрлерін қолданады.
Negamax search is a variant form of minimax search that relies on the zero sum property of a two player game. This algorithm relies on the fact that 1=\min(a, b) = \max( b, a) to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single procedure can be used to value both positions. This is a coding simplification over minimax, which requires that A selects the move with the maximum valued successor while B selects the move with the minimum valued successor. It should not be confused with negascout, an algorithm to compute the minimax or negamax value quickly by clever use of alpha–beta pruning discovered in the 1980s. Note that alpha–beta pruning is itself a way to compute the minimax or negamax value of a position quickly by avoiding the search of certain uninteresting positions. Most adversarial search engines are coded using some form of negamax search.
Альфа-бета кесумен Negamax
Минимакс үшін алгоритмдік оңтайландырулар Negamax үшін де толыққанды қолданылады. Альфа-бета кесу, Negamax алгоритмі іздеу ағашында бағалайтын түйіндер санын, Minimax алгоритмінде қолданылуымен салыстырылатын тәсілмен азайта алады. Альфа-бета кесуді қолдана отырып, тереңдігі шектелген Negamax іздеуінің псевдокоды төменде келтірілген: Альфа-бета кесуді оңтайландыру, бұл түйіннің мәнін беретін ең мүмкін балалық түйіндерді болжауға бағытталған. Алгоритм осы балалық түйіндерді бірінші кезекте іздейді. Сәтті болжаулардың нәтижесінде альфа/бета кесулері ертерек және жиірек орын алып, осылайша ойын ағашының қосымша тармақтары мен іздеу ағашының қалған балалық түйіндері кесіледі.