Негамакс алгоритам
Негамакс претрага је варијанта минимакс претраге која се ослања на нулту-суму приликом игре у којој учествују два играча.
Овај алгоритам се заснива на чињеници да је макс(a, б) = -мин(-a, -б) како би се поједноставила имплементација минимакс алгоритма. Прецизније, вредност која одговара позицији играча А у току игре једнака је негацији вредности која одговара позицији играча Б. Према томе, играч који је на потезу жели да максимизује негацију вредности која произилази из тог потеза: позиција наследника мора, по дефиницији, да буде вреднована од стране противника. Претходна реченица је коректна независно од тога који играч је на потезу, играч А или играч Б. Из тога произилази да се једним потезом могу вредновати обе позиције. Ово је поједностављена верзија минимакс алгоритма која захтева да играч А одабере потез са максималном вредношћу наследника, док играч Б одабере потез са минималном вредношћу наследника.
Овај алгоритам не би требало мешати са негаскаут алгоритмом, који веома брзо израчунава минимакс или негамакс вредност, мудро користећи алфа-бета претрагу, откривену 1980—их година.[1] Потребно је имати на уму да је алфа-бета претрага, сама по себи, један од начина да се израчуна минимакс или негамакс вредност позиције, брзо, избегавајући претрагу конкретних неинтерсантних позиција.
Већина алгоритама претраживања су засновани на негамакс претрази.
Основни негамакс алгоритам
[уреди | уреди извор]Негамакс ради над истом врстом стабла (game tree) која се користи приликом алгоритма минимакс претраге. Сваки чвор и корен стабла представљају одређене фазе игре у којој учествују два играча. Прелазак на чворове потомака представља потезе који су на располагању играчу који се налази на датом чвору, односно играчу који је на потезу.
Циљ негамакс претраге је пронаћи чвор циљне вредности за играча који се налази на корену стабла.[2] Наредни песудокод приказује основни негамакс алгоритам, са могућношћу педашавања максималне дубине претраге.
01 function negamax(čvor, dubina, boja) 02 if dubina = 0 ili čvor je terminalni čvor 03 return boja * heuristička vrednost čvora 04 najboljaVrednost := −∞ 05 foreach potomak čvora 06 v := −negamax(potomak, dubina − 1, −boja) 07 najboljaVrednost := max( najboljaVrednost, v ) 08 return najboljaVrednost
Inicijalni poziv za koren igrača A negamaxVrednostKorena := negamax( koren, dubina, 1) minimaxVrednostKorena := negamaxVrednostKorena
Inicijalni poziv za koren igrača B negamaxVrednostKorena := negamax( koren, dubina, −1) minimaxVrednostKorena := −negamaxVrednostKorena
Корен наслеђује вредност једног од својих непосредних потомака, односно синова. На крају, онај потомак чију је вредност корен наследио представља уједно и најбољи потез који је могуће одиграти. Иако се у псеудокоду у оквиру променљиве najboljaVrednost чува само најбољи резултат, практична имплементација ће такође чувати и најбољи потез, заједно са najboljaVrednost.
Оно што може бити збуњујуће је начин израчунавања хеуристичке вредности тренутног чвора. У овој имплементацији, ова вредност се увек израчунава са тачке гледишта играча А, чија боја је 1. Другим речима, већа хеуристичка вредност увек представља ситуацију која је повољнија за играча А. Ово је понашање које одговара и минимакс алгоритму. Хеуристичка вредност се не мора нужно поклапати са повратном вредношћу чвора, najboljaVrednost, услед негације вредности која се јавља приликом примене негамакс агоритма, као и због параметра боја. Негамакс повратна вредност чвора је хеуристичка са тачке гледишта чвора играча који је тренутно на потезу.
Негамакс резултат се поклапа са минимакс резултатом који се односи на чворове где је играч А на потезу, као и онде где је играч А максимизујући играч у минимакс еквиваленту. Негамакс увек претражује максимум вредности за све своје чворове. Отуда, када су чворови играча Б у питању, минимакс резултат представља негацију њихових негамакс резултата. Играч Б је минимизујући играч у минимакс еквиваленту.
Одређене варијације негамакс алгоритма могу да изоставе параметре боја. У том случају, функција која израчунава хеуристичку вредност враћа вредност са тачке гледишта чвора тренутног играча.
Негамакс алгоритам са алфа-бета претрагом
[уреди | уреди извор]Одређене оптимизације минимакс алгоритма су једнако примењиве за негамакс алгоритам. Алфа-бета претрага може смањити број чворова који негамакс алгоритам обрађује у претрази на сличан начин као у минимакс алгоритму.
Овај псеудокод приказује негамакс алгоритам са алфа-бета претрагом ограничене дубине.
01 function negamax(čvor, dubina, α, β, boja) 02 if dubina = 0 ili čvor je terminalni čvor 03 return boja * heuristička vrednost čvora 04 potomciČvora := GenerišiPoteze(čvor) 05 potomciČvora := RedosledPoteza(potomciČvora) 06 najboljaVrednost := −∞ 07 foreach potomak u potomciČvora 08 v := −negamax(potomak, dubina − 1, −β, −α, −boja) 09 najboljaVrednost := max( najboljaVrednost, v ) 10 α := max( α, v ) 11 if α ≥ β 12 return β 13 return najboljaVrednost
Inicijalni poziv za koren igrača A negamaxVrednostČvora := negamax( koren, dubina, −∞, +∞, 1)
Алфа (α) и бета (β) представљају горње и доње границе за вредности чворова потомака за дату дубину стабла. Негамакс поставља аргументе α и β за корен стабла на најмању и највећу могућу вредност. Остали алгоритми претраге, као што су негаскаут и МТД, могу иницијализовати α и β одређеним алтернативним вредностима како би се касније унапредиле перформансе претраге стабла.
Када негамакс наиђе на вредност чвора потомка изван алфа-бета граница, тада се одсецају одређени делови стабла и елиминишу се из даље претраге. Одсецања су имплицитно заснована на повратним вредностима чворова, najboljaVrednost. Вредност чвора која одговара иницијалном интервалу од α до β представља конкретну (праву) вредност чвора. Та вредност се поклапа са вредношћу коју би вратио и основни негамакс алгоритам, без одсецања и без икаквих α и β граница. Уколико је повратна вредност чвора изван интервала, онда та вредност представља горњу (уколико је вредност ≤ α) или доњу (уколико је вредност ≥ β) границу за праву вредност датог чвора. Алфа-бета претрага на крају одбацује све вредности које произилазе из граница. Те вредности не доприносе и не утичу на крајњи резултат алгоритма.
Псеудокод приказује fail-soft варијације алфа-бета претраге. Fail-soft никада не враћа α или β директно као вредност чвора. Тако, вредност чвора може бити изван иницјалних граница α-β интервала. Са друге стране, fail-hard алфа-бета претрага увек ограничава вредност чвора алфа-бета интервалом.
Ова имплементација такође приказује опциони редослед потеза у односу на форич петљу која обрађује чворове потомака. Редослед потеза је оптимизација алфа-бета претраге која покушава да погоди чворове потомака који имају вредност најприближнију вредности датог чвора. Алгоритам најпре претражује те чворове. Резултат доброг нагађања је побољшање времена, а честа алфа-бета одсецања утичу на одсецање додатних грана и преосталих потомака чворова у стаблу.
Негамакс алгоритам са алфа-бета претрагом и транспозиционим табелама
[уреди | уреди извор]Транспозиционе табеле селективно памте вредности чворова у стаблу. Транспозиција је термин који подразумева да се до дате позиције на табли игре (game board) може доћи примењујући низ различитих потеза у игри.
Када негамакс претражује стабло, и наилази на исти чвор више пута, транспозициона табела може вратити претходно израчунату вредност чвора, прескачући потенцијално дуг процес поновног израчунавања вредности чвора. Ефикасност негамакс алгоритма се нарочито побољшава за она стабла са много путева до датог чвора.
Испод је приказан псеудокод који додаје транспозиционе табеле у алгоритам са алфа-бета претрагом:
function negamax(čvor, dubina, α, β, boa)
alfaOrig := α
// Transpoziciona Lukap Tabela, čvor je lukap ključ za ttUnos
ttUnos := TranspozicionLukapTabela( čvor )
if ttUnos je validan i ttUnos.dubina ≥ dubina
if ttUnos.Flag = EXACT
return ttUnos.Vrednost
else if ttUnos.Flag = LOWERBOUND
α := max( α, ttUnos.Vrednost)
else if ttUnos.Flag = UPPERBOUND
β := min( β, ttUnos.Vrednost)
endif
if α ≥ β
return ttUnos.Vrednost
endif
if dubina = 0 ili čvor je terminalni čvor
return boja * heuristička vrednost čvora
najboljaVrednost := -∞
potomciČvora := GenerišiPoteze(čvor)
potomciČvora := RedosledPoteza(potomciČvora)
foreach potomak u potomciČvora
vr := -negamax(potomak, dubina - 1, -β, -α, -boja)
najboljaVrednost := max( najboljaVrednost, vr )
α := max( α, vr )
if α ≥ β
break
// Transpoziciona Tabela Store; čvor je lukap ključ za ttUnos
ttUnos.Vrednost := najboljaVrednost
if najboljaVrednost ≤ alfaOrig
ttUnos.Flag := UPPERBOUND
else if najboljaVrednost ≥ β
ttUnos.Flag := LOWERBOUND
else
ttUnos.Flag := EXACT
endif
ttUnos.dubina := dubina
TranspozicionaTabelaStore( čvor, ttUnos )
return najboljaVrednost
Inicijalni poziv za koren igrača A negamaxVrednostČvora := negamax( koren, dubina, −∞, +∞, 1)
Алфа-бета одсецања, као и ограничена максимална дубина претраге у негамакс алгоритму могу довести до делимично нетачне, и у потпуности занемарене процене чворова у стаблу. Ово компликује додавање транспозиционе табеле зарад оптимизације негамакс алгоритма. Недовољно је пратити само najboljaVrednost датог чвора у табели, зато што najboljaVrednost не мора уједно бити и права вредност чвора. Код стога мора сачувати и повратити везу najboljaVrednost са одређеним алфа-бета параметрима и дубином претраге за сваку ставку транспозиционе табеле.
Транспозиционе табеле ће обично изоставити или заменити претходне вредности одређених чворова у својим табелама. Ово је неопходно пошто је број чворова који негамакс посећује често већи од величине саме табеле. Изгубљене или изостављене ставке у табели неће утицати на крајњи негамакс резултат. Међутим, изгубљене ставке могу захтевати од негамакс претраге чешће поновно израчунавање одређених вредности чворова стабла, што утиче на његову ефикасност.
Види још
[уреди | уреди извор]Референце
[уреди | уреди извор]- ^ Schaeffer, Jonathan. „The History Heuristic and Alpha-Beta Search Enhancements in Practice”. CiteSeerX 10.1.1.56.9124
., IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989
- ^ Breuker, Dennis M. Memory versus Search in Games, Maastricht University, October 16, 1998
Литература
[уреди | уреди извор]- Heineman, George T., Gary Pollice, and Stanley Selkow (2008). „Chapter 7:Path Finding in AI”. Algorithms in a Nutshell. Oreilly Media. стр. 213—217. ISBN 978-0-596-51624-6.
- Fishburn, John P. (1984). „Appendix A: Some Optimizations of α-β Search”. Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. стр. 107–111. ISBN 978-0-8357-1527-0.