Настолни игри Изкуствен интелект: минимаксният алгоритъм: 8 стъпки

2024 Автор: John Day | [email protected]. Последно модифициран: 2024-01-30 07:51

Чудили ли сте се някога как се правят компютрите, срещу които играете в шах или шашки? Е, не търсете повече от тази инструкция, защото тя ще ви покаже как да направите прост, но ефективен изкуствен интелект (AI), използвайки алгоритъма Minimax! Използвайки алгоритъма за минимакс, ИИ прави добре планирани и обмислени ходове (или поне имитира мисловен процес). Сега бих могъл просто да ви дам кода за AI, който направих, но това нямаше да е забавно. Ще обясня логиката зад избора на компютъра.

В тази инструкция ще ви преведа през стъпките как да направите AI за Othello (AKA Reversi) в python. Трябва да имате междинно разбиране за това как да кодирате в python, преди да се заемете с този проект. Ето няколко добри уебсайта, които да разгледате, за да ви подготвим за тази инструкция: w3schools или learnpython. В края на тази инструкция трябва да имате AI, който да прави изчислени ходове и трябва да може да победи повечето хора.

Тъй като този Instructable ще се занимава предимно с това как да се направи AI, няма да обяснявам как да проектирам игра в python. Вместо това ще дам кода за играта, в която човек може да играе срещу друг човек и да го променя, така че да можете да играете игра, в която човек играе срещу AI.

Научих как да създам този AI чрез лятна програма в Columbia SHAPE. Прекарах добре там, затова разгледайте уебсайта им, за да видите дали ще се интересувате.

Сега, след като сме отстранили логистиката, нека започнем да кодираме!

(Поставих няколко бележки в изображенията, така че не забравяйте да ги разгледате)

Консумативи

Това е лесно:

1) Компютър със среда на python като Spyder или IDLE

2) Изтеглете файловете за играта Othello от моя GitHub

3) Вашият мозък с инсталирано търпение

Стъпка 1: Изтеглете необходимите файлове

Когато влезете в моя GitHub, трябва да видите 5 файла. Изтеглете всички 5 и ги поставете в една и съща папка. Преди да стартираме играта, отворете всички файлове в шпионската среда.

Ето какво правят файловете:

1) othello_gui.py този файл създава дъската за игра, на която играчите могат да играят (независимо дали човек или компютър)

2) othello_game.py този файл играе два компютъра един срещу друг без игралната дъска и показва само резултатите и позициите за преместване

3) ai_template.py тук ще поставите целия си код, за да направите своя AI

4) randy_ai.py това е предварително подготвен AI, който избира ходовете си на случаен принцип

5) othello_shared.py куп готови функции, които можете да използвате, за да направите своя AI, като например да проверите за налични ходове, резултата или състоянието на борда

6) Трите други файла: Puma.py, erika_5.py и nathan.py, направени съответно от мен, Ерика и Натан от програмата SHAPE, това са три различни AI с уникални кодове

Стъпка 2: Как да отворите и играете на Python Othello

След като отворите всички файлове, в долния десен ъгъл на екрана въведете „run othello_gui.py“и натиснете enter в конзолата IPython. Или в терминала на Mac въведете „python othello_gui.py“(след като сте в правилната папка, разбира се). След това на екрана трябва да изскочи дъска. Този режим е режимът човек срещу човек. Светлината отива втора и тъмна първо. Вижте моето видео, ако сте объркани. i В горната част има детайла на всяка цветна плочка. За да играете, щракнете върху валидно пространство за преместване, за да поставите плочка там и след това дайте компютъра на опонента си, който ще направи същото и ще повтори.

Ако не знаете как да играете на Отело, прочетете тези правила от уеб сайта на ултра бордовете:

Черното винаги се движи първо. Ход се прави чрез поставяне на диск с цвят на играча на дъската в позиция, която да „излиза от фланговете“един или повече от дисковете на противника. Диск или ред дискове е ограден, когато е заобиколен в краищата с дискове с противоположен цвят. Дискът може да изпревари произволен брой дискове в един или повече редове във всяка посока (хоризонтална, вертикална, диагонална)…. (довършете четенето на техния уебсайт)

Разликата между оригиналната игра и тази игра на python е, че когато не останат валидни ходове за един играч, играта приключва

Сега, когато можете да играете играта с приятел, нека направим AI, с който можете да играете.

Стъпка 3: Минимакс алгоритъм: Генериране на сценарии

Преди да говорим как да напишем това в код, нека преминем през логиката зад него. Алгоритъмът минимакс е алгоритъм за вземане на решения и проследяване на обратния ход и обикновено се използва в игри с двама играчи, на пошагови игри. Целта на този AI е да намери следващия най -добър ход и следващите най -добри ходове, докато не спечели играта.

Сега как алгоритъмът би определил кой ход е най -добрият? Спрете и помислете как бихте избрали следващия ход. Повечето хора биха избрали хода, който би им дал най -много точки, нали? Или ако мислеха напред, биха избрали хода, който би създал ситуация, в която биха могли да спечелят още повече точки. Последният начин на мислене е начинът, по който Минимаксният алгоритъм мисли. Той гледа напред към всички бъдещи настройки на борда и прави хода, който би довел до най -много точки.

Нарекох това алгоритъм за връщане назад, защото той започва като първо създава и оценява всички бъдещи състояния на дъската с техните свързани стойности. Това означава, че алгоритъмът ще играе играта толкова, колкото е необходимо (прави ходовете за себе си и противника), докато не се изиграе всеки сценарий от играта. За да следим всички състояния на дъската (сценарии), можем да нарисуваме дърво (погледнете в снимките). Дървото на горната снимка е прост пример за игра на Connect 4. Всяка конфигурация на дъската се нарича състояние на дъската, а мястото й на дървото се нарича възел. Всички възли в долната част на дървото са крайните състояния на дъската след извършване на всички ходове. Очевидно някои държави на борда са по -добри за един играч от другия. Така че, сега трябва да накараме AI да избере до какво състояние на борда иска да стигне.

Стъпка 4: Минимакс: Оценка на конфигурациите на платката

За да дадем стойности на състоянията на борда, трябва да научим стратегиите на играта, която играем: в този случай стратегиите на Отело. Тъй като тази игра е битка за прелистване на опонента и вашите дискове, най -добрите позиции на дискове са тези, които са стабилни и не могат да се обърнат. Ъгълът например е мястото, където когато се постави диск, той не може да бъде променен в другия цвят. По този начин това място би било изключително ценно. Други добри позиции включват страните на дъската, които биха ви позволили да вземете много камъни. На този уебсайт има още стратегии.

Сега можем да присвоим стойности на позициите за всеки щат на борда. Когато позиция е заета от фигурата на AI, тогава давате определен брой точки в зависимост от позицията. Например, състояние на дъската, където фигурата на AI е в ъгъла, можете да дадете бонус от 50 точки, но ако е на неблагоприятно място, фигурата може да има стойност 0. След като се вземат предвид всички стойности на позициите, задавате стойност на състоянието на борда. Например, ако AI има фигура в ъгъла, състоянието на дъската може да има резултат 50, докато друго състояние на дъската с фигура AI в средата има резултат 10.

Има много начини да направите това и имам три различни евристики за оценка на парчетата на дъската. Насърчавам ви да направите свой собствен тип евристика. Качих три различни AI в моя github от три различни производители, с три различни евристики: Puma.py, erika5.py, nathanh.py.

Стъпка 5: Минимакс алгоритъм: Избор на най -добро движение

Сега би било хубаво, ако AI може просто да избере всички ходове, за да стигне до състоянието на дъската с най -висок резултат. Но не забравяйте, че AI също избира ходовете за противника, когато генерира всички състояния на борда и ако противникът е умен, това няма да позволи на AI да достигне най -високия резултат на борда. Вместо това интелигентният противник ще направи хода, за да накара AI да премине в най -ниското състояние на борда. В алгоритъма ние наричаме двамата играчи максимизиращ играч и минимизиращ играч. AI би бил максимизиращият играч, тъй като иска да получи най -много точки за себе си. Противникът би бил минимизиращият играч, тъй като той се опитва да направи хода, при който AI получава най -малко точки.

След като всички състояния на платката са генерирани и стойностите са присвоени на платките, алгоритъмът започва да сравнява състоянията на платката. На снимките създадох дърво, което да представя как алгоритъмът ще избира ходовете си. Всяко разделяне в клоновете е различен ход, който може да изиграе AI или противникът. Вляво от редовете на възли, аз написах дали максимизиращият или минимизиращият плейър върви. Долният ред е всички състояния на дъската с техните стойности. Вътре във всеки от тези възли има номер и това са оценките, които присвояваме на всяка от дъските: колкото по -високи са те, толкова по -добре е AI да има.

Определения: родителски възел - възел, който води до или създава възли под него; произходът на дъщерните възли - възлите, които идват от един и същ родителски възел

Празните възли представляват кой ход ще направи AI, за да стигне до най -доброто състояние на борда. Започва със сравняване на децата на най -левия възел: 10, -3, 5. Тъй като максимизиращият играч ще направи хода, той ще избере хода, който ще му даде най -много точки: 10. И така, ние избираме и съхраняваме това преместете с резултата на дъската и го запишете в родителския възел. Сега, когато 10 е в родителския възел, сега е ред на минимизиращите играчи. Възелът, с който ще сравним 10, е празен, така че първо трябва да оценим този възел, преди играчът за минимизиране да може да избере. Така че се връщаме към максимизиращия ход на играча и сравняваме децата на съседния възел: 8, -2. Максимизирането ще избере 8 и ние го пишем в празния родителски възел. Сега, когато алгоритъмът приключи с попълването на празните пространства за децата на възел над него, минимизиращият играч може да сравни тези деца - 10 и 8 и да избере 8. След това алгоритъмът повтаря този процес, докато цялото дърво не бъде попълнено. В края на този пример имаме резултат 8. Това е най -високото състояние на борда, което AI може да играе, за да приемем, че противникът играе оптимално. Така че AI ще избере първия ход, който води до състояние 8 на борда, и ако противникът играе оптимално, AI трябва да изиграе всички ходове, за да стигне до състояние 8 на борда (Следвайте бележките на снимките ми)

Знам, че това беше много. Ако сте от тези типове, които трябва да накарат някой да говори с вас, за да разбере нещо, ето няколко видеоклипа, които гледах, за да ми помогнат да схвана идеята зад това: 1, 2, 3.

Стъпка 6: Минимакс алгоритъм: Псевдокод

След като разберете логиката зад алгоритъма за минимакс, погледнете този псевдокод (функциите, които са универсални за всички кодове) от wikipedia:

функция минимакс (възел, дълбочина, максимизиранеPlayer) е

ако дълбочината = 0 или възелът е терминален възел, тогава

връща евристичната стойност на възел

ако maximizingPlayer тогава

стойност: = −∞

за всяко дете на възел направете

стойност: = max (стойност, минимакс (дъщерно, дълбочина - 1, FALSE))

възвращаема стойност

else (* минимизиране на плейъра *)

стойност: = +∞

за всяко дете на възел направете

стойност: = min (стойност, минимакс (дете, дълбочина - 1, TRUE))

възвращаема стойност

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

Този псевдокод възпроизвежда процеса, който обясних в предишните две стъпки. Сега нека направим тази крачка напред и направим това в кода на python.

Стъпка 7: Направете своя AI с Ai_template.py

Преди да погледнете моя Minimax AI код, опитайте се да се опитате да направите свой собствен AI с файла ai_template.py и псевдокода, за който говорихме в последната стъпка. В ai шаблона има две функции, наречени: def minimax_min_node (дъска, цвят) и def minimax_max_node (дъска, цвят). Вместо функцията минимакс да се извиква рекурсивно, имаме две различни функции, които се извикват помежду си. За да създадете евристика за оценка на състоянията на борда, ще трябва да създадете своя собствена функция. Във файла othello_shared.py има предварително зададени функции, които можете да използвате за изграждане на вашия AI.

След като имате своя AI, опитайте да го стартирате, randy_ai.py. За да стартирате два ais един срещу друг, въведете „python othello_gui.py (вмъкнете име на ai файл).py (вмъкнете име на файл).py“в терминала на mac или въведете „run othello_gui.py (вмъкнете име на ai файл).py (вмъкнете име на файл).py и се уверете, че сте в правилната директория. Вижте и видеото ми за точните стъпки.

Стъпка 8: Време е да накарате AI да се бори

Сега вземете куп ваши компютърни приятели и ги накарайте да проектират свой собствен AI! След това можете да направите състезание и да накарате вашия AI да го изведе. Надяваме се, че дори и да не можете да създадете свой собствен AI, сте успели да разберете как работи минимаксният алгоритъм. Ако имате въпроси, не се колебайте да публикувате въпроси в коментарите по -долу.