Ръководство стъпка по стъпка за изграждане на прост AI шах

Нека разгледаме някои основни концепции, които ще ни помогнат да създадем прост AI шах:

  • движение-поколение
  • оценка на борда
  • минимакс
  • и алфа бета резитба.

На всяка стъпка ще подобряваме нашия алгоритъм с една от тези изпитани във времето техники за програмиране на шах. Ще демонстрирам как всеки от тях влияе на стила на игра на алгоритъма.

Можете да видите окончателния алгоритъм на AI тук на GitHub.

Стъпка 1: Преместете генерирането и визуализацията на дъската

Ще използваме библиотеката chess.js за генериране на ходове и chessboard.js за визуализиране на дъската. Библиотеката за генериране на ходове основно прилага всички правила на шаха. Въз основа на това можем да изчислим всички легални ходове за дадена държава на борда.

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

Ще започнем, като създадем функция, която просто връща произволен ход от всички възможни ходове:

Въпреки че този алгоритъм не е много солиден шахматист, той е добра отправна точка, тъй като всъщност можем да играем срещу него:

Стъпка 2: Оценка на позицията

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

С функцията за оценка можем да създадем алгоритъм, който избира хода, който дава най-висока оценка:

Единственото осезаемо подобрение е, че нашият алгоритъм вече ще улови парче, ако може.

Стъпка 3: Търсене на дърво с помощта на Minimax

След това ще създадем дърво за търсене, от което алгоритъмът може да избере най-добрия ход. Това се прави с помощта на алгоритъма Minimax.

В този алгоритъм рекурсивното дърво на всички възможни движения се изследва до зададена дълбочина и позицията се оценява в крайните „листа“ на дървото.

След това връщаме или най-малката, или най-голямата стойност на детето към родителския възел, в зависимост от това дали е бяло или черно за преместване. (Тоест, ние се опитваме или да минимизираме или максимизираме резултата на всяко ниво.)

С поставения минимакс нашият алгоритъм започва да разбира някои основни тактики на шаха:

Ефективността на минимаксния алгоритъм се основава силно на дълбочината на търсене, която можем да постигнем. Това е нещо, което ще подобрим в следващата стъпка.

Стъпка 4: Алфа-бета резитба

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

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

Подрязването на алфа-бета не влияе върху резултата от минимаксния алгоритъм - само го прави по-бързо.

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

С алфа-бета получаваме значителен тласък на алгоритъма на минимакс, както е показано в следващия пример:

Следвайте тази връзка, за да изпробвате алфа-бета подобрената версия на шахматния AI.

Стъпка 5: Подобрена функция за оценка

Функцията за първоначално оценяване е доста наивна, тъй като броим само материала, който се намира на дъската. За да подобрим това, ние добавяме към оценката фактор, който отчита позицията на парчетата. Например, рицар в центъра на дъската е по-добър (защото има повече опции и по този начин е по-активен) от рицар на ръба на дъската.

Ще използваме леко коригирана версия на таблици с квадратни квадратчета, които първоначално са описани в wiki за програмиране на шах.

Със следващото подобрение започваме да получаваме алгоритъм, който играе някакъв „достоен“ шах, поне от гледна точка на случаен играч:

Заключения

Силата на дори един прост алгоритъм за игра на шах е, че той не прави глупави грешки. Въпреки това все още липсва стратегическо разбиране.

С методите, които въведох тук, успяхме да програмираме алгоритъм за игра на шах, който може да играе основен шах. „Частта от AI“ (без генериране на ходове) на крайния алгоритъм е само 200 реда код, което означава, че основните концепции са доста лесни за изпълнение. Можете да проверите окончателната версия на GitHub.

Някои допълнителни подобрения, които бихме могли да направим в алгоритъма, биха били например:

  • нареждане на преместване
  • по-бързо генериране на ходове
  • и специфична оценка в края на играта.

Ако искате да научите повече, вижте wiki за програмиране на шах. Това е полезен ресурс за изследване отвъд тези основни концепции, които въведох тук.

Благодаря за четенето!