Бележки на програмиста Интелигентни системи

Това е страхотно!

Интелигентни системи. Алгоритъм за намиране на оптималния ход в играта Tic-Tac-Toe

системи

Сигурен съм, че мнозина са се насладили на великолепното търсене на Machinarium. Вероятно си спомняте робота, който трябваше да биете в бара, за да получите необходимите болтове. И така, играта, в която трябваше да бъде бит, е много подобна на тик-так, но има поле 10 на 10 и продължава, докато един от играчите подреди ред от пет фигури.

Продължавайки темата за интелигентните системи, предлагам да напиша алгоритъм за игра на тик-так, според правилата, предложени в Machinarium.

Игри с нулева сума

Дърво на играта (решението)

дървото играта

Процедура Minimax

програмиста

Тук трябва да бъдат обяснени някои от използваните функции.

  • Функция isTerminal проверява дали в игралното поле е достигнато състоянието на терминала. Състояние на терминала, това е състояние, при което един от играчите печели или всички възможни ходове са изчерпани или е изпълнено условието за спиране на разширяването на дървото на играта (достигната е максималната дълбочина/паметта е приключила).
  • Функция евристичен дава евристична оценка на състоянието на игралното поле.
  • Функция деца, всеки път, когато е осъществен достъп, той връща следващото дъщерно на текущо оценяваната позиция в дървото на играта. Тези. разширява дървото на играта до следващата дълбочина.

Представеното решение е доста грубо и съдържа много почти идентичен код. Ако разгледате внимателно кода, ще забележите, че извикването на функцията MAX е еквивалентно на извикване -MIN (обратното също е вярно).

Въз основа на това наблюдение можете да съкратите кода до една функция:

Когато избирате една от опциите (MAXIMIN или MINIMAX), бъдете внимателни, много е важно да не се забърквате с аргументите при първото извикване на тези функции. Ако горната част е разкрита за MAX плейъра (последният ход е MAX плейър), тогава функцията MINIMAX или -MAXIMIN трябва да бъде извикана.

Е, с помощта на процедурата minimax, броят на отваряемите върхове е значително намален, но за да се приложи алгоритъм, който може да се конкурира със силен играч, може да се наложи да отворите дървото на играта на достатъчно голяма дълбочина и при в същото време оценявайте все по-голям брой върхове. Това може да доведе до значителни разходи както по отношение на времето, така и на паметта. Следователно, въпреки факта, че процедурата minimax значително намалява броя на отворените върхове, тя все още не дава приемливи резултати.

Ако се върнем към примера на дървото на играта, даден по-рано, тогава можем да забележим следното, след като е намерен ход, който води кръстовете поне до равенство, този ход става по-малък от това, за което се съгласяват. Когато започне разглеждането на втория ход (на дълбочина 1) и се намери загубен връх, вече няма смисъл да се разкрива следващият (на дълбочина 2), тъй като за кръговете най-лошото нещо, за което се договарят, е -5 резултат, което от своя страна е по-малко от най-лошите очаквания за центриране. Следователно вторият ход (вторият връх на дълбочина 1) няма да бъде избран.

Трудно е да се разбере това наблюдение за първи път, но въпреки това може да помогне за намаляване на броя на разширените върхове в дървото на играта. Въз основа на тези разсъждения е изграден следният алгоритъм, наречен алфа-бета изрязване.