Играње стратешких игара са минималним алгоритмом

У овој лекцији истражићемо популаран алгоритам који се зове минимак . Такође ћемо научити неке од његових пријатељских суседских додатака, попут хеуристичких резултата , итеративног продубљивања и алфа-бета обрезивања . Користећи ове технике, можемо створити флексибилнији и моћнији агент за играње игара. Моћи ће да се такмичи у многим изазовима, укључујући стратешку игру Исолатион.

У мом претходном посту Како освојити Судоку научили смо како да научимо рачунаре да решавају загонетку Судокуа. Ако га нисте прочитали, само на брзину прочитајте. Али то је заиста био само начин да намочимо ноге пре него што смо заротили у софистицираније методе агената за играње игара. Нарочито оне методе које могу повући стратешке потезе против противника!

Немојте се насукати

Изолација (или Исола) је стратешка друштвена игра заснована на потезу где два играча покушавају да ограниче свог противника на 7к7 даску налик на шаху. На крају, више не могу да направе потез (чиме их изолују).

Сваки играч има по један комад, којим се може кретати попут краљице у шаху - горе-доле, лево-десно и дијагонално. Постоје три услова под којима се делови могу померати -

  1. Не могу свој комад поставити на већ посећени трг.
  2. Не могу да пређу преко већ посећених квадрата (провлачење кроз њих дијагонално је у реду).
  3. Не могу прелазити преко комада другог.

На горњој слици, са црних поља можете видети да су оба играча ставила своје делове на разне делове плоче. Али како је игра напредовала, то показује да жути играч још увек има три могућа потеза. Горе и десно, десно један квадрат, а десно два квадрата. Али плави играч нема више опција. Дакле, жути играч је овде победник.

Сада ово може изгледати као једноставна игра - и да будем искрен, јесте. Није да играмо покер или Старцрафт. Ипак, још увек постоји огромна количина могућих потеза које било који играч може повући у било ком тренутку током игре.

У загонеткама попут Судоку-а постоји „одговор“ који желимо решити. Али нема одговора када су стратешке игре у питању.

Играмо против другог противника - попут особе, рачунара или детектива мачке. То захтева стратегију и мало размишљања о томе како игра може изгледати док се котрља.

Такве игре могу еволуирати и произвести апсурдну количину могућих исхода. Зато морамо да размислимо како можемо да изаберемо најбољи могући потез, без трошења времена потребно мачкама да населе Земљу.

Добро, нема више мачака!

Моћни Минимак и пријатељи

Сад кад знате како се игра Исолатион, погледајмо како можемо да користимо алгоритам минимак ; основна ствар у заједници АИ. Такође ћемо се осврнути на хеуристичке оцене , итеративно продубљивање и алфа-бета обрезивање . Заједно са њима можемо да изградимо конкурентног агента за интелигенцију.

Минимак

Минимак алгоритам је веома популаран за подучавање агената интелигенције како да играју стратешке игре по потезу. Разлог је тај што узима у обзир све могуће потезе које играчи могу предузети у било ком тренутку током игре. Помоћу ових информација покушава да умањи предност противничког играча, истовремено повећавајући предност агента на сваком кораку који АИ агент игра.

Е сад, како ово изгледа?

Па, слично ономе како би АИ агент играо игру попут Судокуа, ми можемо да моделирамо следеће могуће потезе које било који играч може повући путем стабла претраживања . Међутим, мораћемо да користимо дрво претраживања са променљивим ширинама - или другим речима, ширином нивоа стабла. Разлог је тај што постоји променљив број потеза које сваки играч може да повуче у било ком тренутку током игре.

Горе приказано дрво представља следеће потезе доступне током игре Изолације. Има мрежу 2к3, а доњи десни квадрат је недоступан. Као што видите, два играча су плави круг и црвени крст.

Врх стабла (коријенски чвор) илуструје потез црвеног играча. Средњи ниво илуструје следеће могуће потезе плавог играча. И трећи ниво илуструје могуће потезе црвеног играча, с обзиром на претходни потез плавог играча.

Свако стање игре или чвор на дрвету има информације о томе који играч има највише користи од било ког потенцијалног потеза.

Сад се можда питате, ког врага су ти троуглови испод сваког потеза?

Доњи троугао представља место на дрвету где ће минимакс умањити противникову предност. Док су троуглови нагоре локације на којима минимакс максимизира предност агента.

Али минимак може знати предност било ког играча само ако познаје стазе на дрвету које воде до победе било ког играча. То значи да минимакс мора прећи до самог дна стабла за сваки могући низ потеза. Даље, мора доделити неки резултат (нпр. +1 за победу и -1 за пораз) и те бројеве ширити кроз стабло. На тај начин, свако стање игре или чвор у дрвету имају информације о томе који играч има највише користи од било ког потенцијалног потеза.

На овој слици можемо извести неколико запажања. Први минимак додељује број коначним исходима игре на чворовима листа . Затим их шири према горе кроз дрво, успут изводећи минимализације и максимизације. Једном када минимак заврши попуњавање стабла, кад год је на реду АИ агент, знаће који потези ће вероватно довести до победе или пораза.

Други ниво након коренског чвора приказује следеће могуће потезе за плавог играча (нашег АИ агента). Наш агент жели да максимизира доступне резултате током свог потеза. Тако би изабрао потез представљен у крајњем десном чвору који следи коријенски чвор. Супер кул!

Али да ли има смисла једноставно доделити +1 или -1 исходима игре? Не би ли овај резултат требао узети у обзир како се игра добија или губи?

Упозорење спојлера: одговор је да!

Хеуристички резултати

У свету стратешких игара, хеуристички резултат је у основи субјективна вредност коју приписујемо неком стању игре. Ова вредност се заснива на нашем разумевању како се игра добија и губи. Одабиром добро осмишљене хеуристичке оцене, могли смо да научимо нашег агента интелигенције како да најбоље одабере своје следеће потезе док игра игру Изолација.

Сада вероватно постоји неограничен број хеуристичких резултата које бисмо могли смислити. Али овде ћемо погледати само неколико њих, осим наивног резултата (НС) од +1 и -1.

Једна идеја би могла бити да се изброје сви наредни могући потези које сваки играч има у било ком тренутку, јер више могућих потеза значи мање шансе да будете изоловани. Ово ћемо назвати резултат отвореног потеза (ОМС) .

Друга идеја би могла бити употреба вредности добијене из ОМС-а и одузимање броја следећих могућих потеза противника. Разлог је тај што сваки играч жели да повећа своју количину потеза, а да истовремено смањи противников потез. Ово ћемо назвати побољшани резултат (ИС) .

Горња слика приказује стопе победа у многим симулираним изолационим играма које су играли агенти АИ користећи различите хеуристичке оцене. Сада можете да видите колико су се различити наши резултати током стварне игре. Али било је неких хеуристичких резултата који су надмашили оне до којих смо дошли

Занимљиво је да су прва два скоро потпуно иста као и побољшани резултат. Назваћемо их агресивним побољшаним резултатом (АИС) и супер агресивним побољшаним резултатом (САИС) . Али постоји мала разлика између ових оцена и оригинала. Горња два резултата примењују фактор два и три на вредност коју одузмете (број потеза доступан противнику) приликом израчунавања побољшане оцене.

Можете открити оптимални „агресивни фактор“ који ћете применити приликом израчунавања овог резултата!

Још једно упозорење спојлера - постоје боље вредности.

Али шта ако дођемо до хеуристичког резултата за који је потребно много времена за израчунавање? Шта ако је дрво огромно? Да ли ће наш АИ агент имати довољно времена да пронађе своје следеће најбоље потезе, а да и даље буде довољно реагован током игре?

Итеративно продубљивање

Сада знамо да наш АИ агент може моделирати све могуће потезе користећи дрво претраживања и одговарајући хеуристички резултат његових чворова. Али на жалост, када се играмо Исолатион, наше дрво ће бити масивно. Требало би више времена да претражимо дрво и израчунамо ове вредности него што има година од Великог праска!

Унесите итеративно продубљивање - стратегију управљања временом за агенте за играње игара. Коришћењем ове методе можемо смањити време израчунавања и претраживања на максимално време које смо изабрали. На овај начин наш агент за интелигенцију може да реагује бар онолико брзо колико би човек могао.

Али како функционише итеративно продубљивање?

Омогућава минимаксу да се креће ниво по ниво и израчунава хеуристичке резултате до одређеног временског ограничења. Једном када се достигне ово временско ограничење, агент АИ је приморан да искористи најбољи потез који је открио док се кретао све дубље низ дрво.

Сада ово пружа одређени увид у то колико тешко може бити. Стварање АИ агента који је довољно паметан и одговоран за стратешке игре може бити прилично незгодно, чак и за чаробњаке за АИ. Поготово ако такве игре садрже свет могућности.

Нажалост, број потеза које АИ агент може да „замисли“ како иде даље је ограничен. Дакле, могуће је да би могао донијети одлуку која доводи до његове пропасти. Ово је добро познати феномен који се назива ефекат хоризонта . Али још увек морамо да погледамо вероватно најефикаснији алгоритам резања времена који се користи приликом претраживања дрвећа.

Алпха-Бета резидба

Добро, то су грожђице, а не суве шљиве, али ипак - како је то икад било? Мислим, озбиљно, група грожђица-блуза?

Можда сте већ претпоставили да алфа-бета резидба нема никакве везе са сувим шљивама, а више о смањењу величине (резидбе) нашег стабла претраживања. Када имамо врло велико стабло претраживања, испоставило се да није увек потребно прелазити сваки чвор када се користи минимак.

Морамо минимаксу дати могућност да заустави претраживање одређеног дела стабла када пронађе гарантовани минимум или максимум тог одређеног нивоа.

Ако то можемо, то може у великој мери да смањи време одзива нашег агента за интелигенцију и побољша перформансе.

Како делује алфа-бета резидба?

Минимакс алгоритам се креће кроз стабло користећи претрагу у дубину. То значи да пролази кроз дрво идући с лева на десно и увек идући најдубље што може. Затим открива вредности које се морају доделити чворовима директно изнад њега, а да никада не гледа друге гране стабла.

Алпха-бета резидба омогућава минимаку да доноси једнако добре одлуке као што би минимак могао сам, али са вишим нивоом перформанси.

Размотрите следећу слику на којој имамо дрво са различитим резултатима додељеним сваком чвору. Неки чворови су осенчени црвеном бојом, што указује на то да их није потребно прегледавати.

У доњем левом углу стабла, минимак гледа вредности 5 и 6 на доњем максималном нивоу. Утврђује да 5 мора бити додељено минималном нивоу одмах изнад њега. Има смисла.

Али, након што погледа 7 и 4 десне гране максималног нивоа, схвата да горњем чвору мин нивоа мора бити додељена максимална вредност 4. Пошто ће други максимум нивоа тачно изнад првог нивоа мин узети максимум између 5 и највише 4, јасно је да ће изабрати 5. Након овога, наставило би да обилази дрво да би извршио исти тачан скуп операција унутар осталих грана стабла.

Испод је алгоритамски приказ минимакса са алфа-бета резидбом.

Коришћење ове методе омогућава једноставан начин смањења простора за претрагу нашег агента за интелигенцију. На овај начин, алфа-бета резидба омогућава минимаку да доноси добре одлуке које би минимак могао донијети сам, али са вишим нивоом перформанси.

Исола-тер

Истражили смо како да направимо сопственог агента за интелигенцију који може да игра игру Изолација на прилично конкурентном нивоу. Коришћењем минмак алгоритма видели смо како АИ агент може моделирати игру и може доносити одлуке на основу хеуристичког резултата. Такође смо научили како да одредимо добро дефинисану хеуристику за наш задати задатак (Изолација).

Али такође смо открили да би било превише рачунски интензивно пустити минимак да подивља. Тако смо морали да користимо технике попут итеративног продубљивања и алфа-бета обрезивања. То би натерало нашег агента АИ да смисли следећи потез у разумном року. Али шта ако желимо да наш АИ агент има већу стопу победе, а да истовремено буде једнако реагован као човек?

Па, постоје и друге технике које бисмо могли истражити како бисмо повећали стопу победе нашег агента као и време одзива. Дотакли смо се идеје о подешавању параметара наше хеуристичке оцене (сећате се „агресивног фактора“?). Могли бисмо чак доћи до хеуристичког резултата који је боље прилагођен игрању Изолације.

Постоје и рефлектујућа својства повезана са могућим потезима на изолационој плочи. То постаје очигледно када анализирамо потпуно насељено стабло претраживања, што би нам омогућило да потенцијално исечемо пуно грана са стабла претраживања. Такође, ако бисмо надоградили свој хардвер, наш АИ агент би био бржи - и самим тим би могао да истражи више могућности.

Ако желите да уђете у ситне детаље о томе како то сами применити, погледајте код који сам написао да бих решио овај проблем за мој Удацити Артифициал Интеллигенце Нанодегрее. Можете га пронаћи на мом ГитХуб репо-у.

Здраво, ја сам Грант! Ја сам слободни програмер и квант. Погледајте моју веб страницу на //фрееланцекуант.цом. Живели!