Разработка и программная реализация

Рисунок 2.10 Кодирование фигур

Далее логическая структура и способ представления фигур и поля можно преобразовать в приближенный к программированию вид и перейти к одному из этапов проектирования системы создание диаграммы классов (см. приложение Б). Диаграмма содержит класс Judge (судья) c операциями по запуску игры StartGame() по проверке признаков завершения игры IsGameOver(). Данный класс связан с классом GameSession (игровая сессия). В свое время тот содержит в себе объект класса Field(поле). У данного класса есть атрибуты размер и ячейки. На поле будут располагаться фигуры - объекты класса Figure. Так же создан абстрактный класс Player(игрок) с атрибутом имя и операцией сделать ход MakeMove(). Его наследуют три класса RandomPlayer игрок, совершающий ходы случайно, Computer виртуальный игрок, который работает на основе генетического алгоритма, и Human игрок, который будет представлять реального игрока. Так же присутствуют классы, относящиеся к генетическому алгоритму: класс Genome описывающий геном и GA класс генетического алгоритма.

Созданная на основе данной диаграммы программа, содержит ка эти классы так и ряд дополнительных, вспомогательных. Программа была написана на языке программирования C# в среде разработки Visual Studio. Разработанная программа позволяет смоделировать игру Quarto, как для двух рандомных игроков, так и игру между рандомным игроком и компьютерным, работающим на основе генетического алгоритма. Запуск игры двух рандомных игроков во многом помог в исследовании самой игры, так как не приходилось самим играть в игру и вручную записывать результаты игр. Так же данная программа позволила эмулировать упрощенную игру 2х2 для подтверждения выявленных закономерностей, полученных аналитическим путем.

2.3 Описание разработанного генетического алгоритма

Работа компьютерного игрока будет основана на работе генетического алгоритма, он поможет определить куда следует поставить переданную соперником фигуру, а также принять решение на счет того какую фигуру в свою очередь передать сопернику.

Следует отметить, что в процессе работы генетического алгоритма будут участвовать лишь не занятые ячейки и не поставленные на поле фигуры, как только какая-либо фигура поставлена на поле данная ячейка считается неприкосновенной и фигура становится недоступной. Это решение позволяет существенно сократить пространство поиска решений в ходе работы алгоритма.

В качестве генома первоначально предполагалось использовать все поле и все возможные расстановки фигур на нем. Конечно, такой подход позволял сразу же брать во внимание все, что происходит на поле и как лучше поставить свою фигуру и какую дать сопернику, но не позволял разработать эффективную фитнес-функцию. В случае игры компьютера и рандомного игрока победой компьютера завершалось 85% игр, что не позволяет утверждать, что данный игрок будет эффективен в игре с реальным человеком.

В связи с этим было принято решение несколько поменять концепцию: теперь в качестве генома выступает четыре фигуры и четыре позиции, то есть массив из восьми ячеек. Выбор такого размера обусловлен тем, что он позволит составить выигрышный ряд из фигур и достроить его на поле. При этом первой фигурой в геноме является фигура, переданная игроку его соперником, ее нам необходимо будет поставить на поле, значит первая задача найти подходящее место для данной фигуры. При инициализации каждого из геномов на первую позицию присваивается код фигуры, которую игроку передал его соперник, затем коды оставшихся трех фигур генерируются случайным образом из доступных для постановки фигур, аналогично этому случайно генерируются и позиции для постановки тоже из свободных на данный момент.

После структуры генома можно перейти непосредственно к алгоритму, рассмотрим его поподробнее. Экземпляр алгоритма создается компьютерным игроком. На моменте инициализации устанавливается значения для размера популяции равным ста особям, количество поколений двадцать, уровень мутации 0,05 и уровень скрещивания 0,8. Данные параметры можно изменять и в зависимости от этого регулировать эффективность работы алгоритма.

Запуск алгоритма производится с помощью метода Go(). В нем создается популяция согласно заданному размеру, затем производится ранжирование особей согласно фитнес-функции (ее описание будет приведено ниже). Затем в цикле создаются следующие поколения, также производится их ранжирование. В результате получаем самую «приспособленную» особь в последнем поколении, которая и даст ответ на вопрос куда ставить фигуру, переданную соперником и что давать ему в ответ.

Как же происходит создание поколения? Первоначально особи генерируются случайным образом. Затем же для создания нового поколения текущая популяция должна пройти через процесс отбора, скрещивания, и мутации.

Процесс отбора осуществляется с помощью стандартного метода, используемого для генетических алгоритмов, основанного на принципах работы рулетки (ее описание было приведено в главе 1) в комбинации с применением элитарной стратегии. Согласно данной стратегии в число особей нового поколения без изменений переходит наиболее приспособленная особь текущего поколения, она занимает позицию наименее приспособленной особи в новом поколении. Метод рулетки применяется для отбора особей участвующий в операции скрещивание.

После выбора двух особей производится генерация случайного числа если оно меньше уровня скрещивания, то данный процесс производится, если же оно больше, то данные особи без изменений переходят в новое поколение. Если процесс производится, то он осуществляется следующим образом. Для скрещивания необходимы две особи, они выбираются с помощью метода, описанного выше. Генерируем два числа они будут определять сколько раз мы будем менять фигуры и обмениваться индексами позиций. Запускаем цикл, в котором количество итераций равно четырем. Первое, что можно сделать - это поменять второй особи фигуру, при этом первую фигуру мы не трогаем, так как она должна обязательно присутствовать в итоговом геноме. Берем первого родителя и по индексу (номер итерации плюс один, так как мы не трогаем первую фигуру) и присваиваем ее значение на то же место второй особи. Важно отметить, что если в геноме уже присутствует такая фигура, то вместо присваивания производится обмен позициями внутри генома. Совершать данный процесс будем согласно первому сгенерированному числу количество раз. Второе действие, которое осуществляется это обмен позициями. Оно осуществляется аналогично изменению фигур в геноме второй особи, однако здесь мы производим изменение первой особи и меняем позиции фигур и берем их по индексу цикла плюс четыре, так как нам необходимы позиции. Выполняем второе действие согласно второму сгенерированному числу. Первый потомок - это измененная первая особь, а второй - вторая. Для эффективной работы алгоритма и обеспечения быстрой сходимости для каждого потомка оценивается его фитнес. Если он хуже, чем был у его первоначально у его родителя (первого потомка мы сравниваем с первым родителем, а второго со вторым соответственно), то в следующее поколение переходит родительская особь, если лучше, то потомок добавляется в следующее поколение.

После скрещивания предусмотрена такая операция как мутация. Для этого производится генерация случайного числа если оно меньше уровня мутации, то она производится, иначе не производится. В ходе мутации производятся случайный обмен фигурами внутри генома, например, геном был 6 4 10 3 4 5 3 0, а стал 6 10 4 3 4 5 3 0. Затем по тому же принципу случайно меняются позиции в геноме. Так же, как и в случае с скрещиванием оценивается фитнес мутированной особи, если ее выживаемость ниже первоначальной, то изменения не принимаются и особь остается такой как была.

Процесс селекции, скрещивания и мутации продолжается до тех пор, пока не будет создано новое поколение согласно заданному размеру.

Наконец перейдем к описанию ключевой функции для генетического алгоритма фитнес-функции. Запускаем цикл в четыре итерации (чтобы обойти весь геном особи) для каждой фигуры проверяем наличие выигрышной позиции, при постановке на которую с этой фигурой можно выиграть и завершить игру. Если такая позиция найдена, то берется ее индекс и сравнивается с индексом этой фигуры в геноме. Если они совпадают и сейчас ход не соперника, то к значению фитнеса данного генома прибавляется 10 умноженное на позицию индекса в геноме, если индекс не совпадает или сейчас ход соперника, то к геному прибавляется -10 умноженное на позицию индекса в геноме. Если выигрышная позиция не найдена, то из значения фитнеса данного генома вычитается единица. Игрок, работа которого основана на данной версии алгоритма и данной фитнес-функции будем называть компьютер.

В ходе тестирования данной версии алгоритма (о нем будет написано далее) было выяснено, что при игре с реальным человеком в некоторых случаях данный алгоритм не позволяет выиграть компьютерному сопернику. В связи с этим было принято решение усложнить фитнес-функцию. Можно сказать, что новый вариант - это «пессимистичная» фитнес-функция. Данная функция аналогична описанной ранее за одним исключением: при рассмотрении каждой фигуры в геноме мы проверяем, а была ли у соперника до этого более лучшая альтернатива, то есть наихудший для нас ход. Если такой ход был, и он не присутствует в данном геноме, то мы «штрафуем» данный геном, так как если соперник умен, то он выберет наихудший с нашей точки зрения ход. Игрока, который будет работать на основе данного алгоритма с «пессимистичной» фитнес-функцией будем называть суперкомпьютер.

Более того было проведен ряд экспериментов для того чтобы выявить оптимальное количество поколений для алгоритма (данный параметр устанавливается при инициализации). Для суперкомпьютера самым оптимальным числом поколений является 10, так как при этом количестве достигается наибольший процент побед (рисунок 2.11).

Рисунок 2.11 График зависимости количества побед от количества поколений

2.4 Тестирование разработанного алгоритма

На основе разработанного алгоритма производится работа компьютерного игрока. При этом существуют два варианта алгоритма соответственно и два виртуальных соперника: компьютер и суперкомпьютер. В качестве тестирования эффективности работы алгоритма были запущены как одиночные игры с игроком, играющим случайно, пример лога запуска можно найти в приложении В. А также серия из пяти ста игр компьютера и рандомного игрока, лог запуска большого теста можно найти в приложении Г.

После запуска игр получились следующие результаты: 489 игр завершились победой компьютера и 2 игры завершились ничьей (рисунок 2.12).

Рисунок 2.12 Диаграмма исход 500 игр компьютера против рандомного игрока

При этом при изменении порядка игроков результат остался тем же, в первом тесте на 500 игр первым ходил рандомный игрок, а во втором аналогичном тесте первым совершал ход компьютер.

Так же была собрана статистика по количеству совершенных ходов в играх при выигрыше компьютера (см. рисунок 2.13). Данные результаты подтверждают сделанные ранее выводы о том, что второму игроку выгоднее заканчивать игру на ранних этапах, а не в конце игры.

Рисунок 2.13 Диаграмма процента игр, завершенных за определенное количество ходов



Так же был протестирован и суперкомпьютер, он так же играл против игрока играющего случайно. Результаты получились следующие: в 100% игр выиграл суперкомпьютер (рисунок 2.14), так же, как и в случае с компьютером при изменении порядка игроков результаты тестов не изменились.

Рисунок 2.14 Диаграмма 500 игр суперкомпьютера против рандомного игрока

После этого были запущены 50 игр между двумя игроками, работающими на основе двух вариантов алгоритма, между компьютером и суперкомпьютером. Данный тест показал, что суперкомпьютер намного превосходит своей эффективностью компьютер, он выиграл у него 70% игр. Ничьей были завершены 24% игр, а победой компьютера лишь 6% игр (см. рисунок 2.15).

Рисунок 2.15 Диаграмма 50 игр суперкомпьютера против компьютера

Полученные результаты означают, что алгоритм с «пессимистичной» фитнес-функцией гораздо эффективнее первоначальной версии алгоритма. Однако для создания полноценной игры оба варианта алгоритма полезны, так как они позволят реализовать два уровня сложности: для более легкого будет использоваться первый вариант алгоритма, а для сложного - второй с «пессимистичной» фитнес-функцией.

Для того чтобы провести тестирование работы алгоритма при игре с реальным человеком был создан интерфейс в виде Windows forms - приложения. Оно состоит из формы авторизации и формы, на которой присутствует игровое поле и доступные для постановки фигуры, а также кнопки запуска новой игры и ее завершения. Для простоты все фигуры на форме отображаются текстовыми аббревиатурами, например, белая низкая есть выемка квадратная фигура будет обозначена БНЕвКв. Переданная фигура отображается в виде надписи, так же для удобства игрока требуемое от него действие отображается в виде текстовой подсказки (см. приложение Г).

Для того чтобы оценить эффективность разработанного алгоритма с помощью описанной выше формы было сыграно 50 игр против компьютера. Семь игр выиграл человек, столько же были сыграны в ничью, а оставшиеся выиграл компьютерный соперник, работающий на основе разработанного алгоритма первой модификации (см. рисунок 2.16).

Рисунок 2.16 Диаграмма результаты 50 игр человека против компьютера

Полученные результаты позволяют утверждать, что разработанный алгоритм достаточно эффективен даже при игре с реальным человеком. Для того чтобы обычный человек был заинтересован в игре шанс выиграть в 18% игр представляется более приемлемым, в отличие от стопроцентного проигрыша, так как желание играть в игру может быстро уйти если не давать реальному игроку возможности выиграть.

При тестировании суперкомпьютера против человека, человеку не удалось ни разу его выиграть, так как суперкомпьютер просчитывает ходы наперед, а обычному человеку достаточно сложно просчитать ходы и удержать все комбинации в голове. Тестирование проводилось с участием обычных игроков, и возможно при игре с профессионалом суперкомпьютер возможно победить (это подтверждает тест с игрой компьютера против суперкомпьютера, где компьютеру удавалось выиграть суперкомпьютер).

Результаты тестирования показали, что оба варианта алгоритма достаточно эффективны как при игре против игрока, играющего случайно, так и при игре с человеком. При этом первый вариант алгоритма, на основе которого работает виртуальный соперник «компьютер» проигрывает в силе второму варианту алгоритма, на основе которого работает виртуальный соперник «суперкомпьютер».



Заключение

В ходе данной работы был проведен сравнительный анализ существующих методов моделирования искусственного интеллекта в играх. В результате были выявлены преимущества и недостатки каждого из методов, а лучшим был признан генетический алгоритм. В качестве игры, для моделирования которой предполагалось применение генетического алгоритма, была выбрана игра Quarto, так как она не слишком сложна как шахматы, и, но тоже время, сложнее, чем крестики-нолики.

Был проведен анализ самой игры Quarto и стратегий игроков. В результате моделирования игры выяснилось, например, что у игроков примерно равные шансы на победу. В ходе анализа количества совершенных ходов обнаружилось, что первому игроку выгоднее «затягивать» игру, а второму завершать ее на ранних этапах.

Были разработаны два варианта генетического алгоритма: с «обычной» фитнес-функцией и с «пессимистичной». Данные алгоритмы легли в основу программы, моделирующей игру для двух виртуальных соперников. В одном случае соперником был «компьютер», во втором - «суперкомпьютер».

Разработанный генетический алгоритм позволил виртуальному сопернику всегда обыгрывать рандомного игрока, т.е. игрока, совершающего ходы случайным образом. В игре компьютера с реальным человеком первый вариант алгоритма позволяет компьютеру выигрывать в 65% случаев. Если же использовался алгоритм с «пессимистичной» фитнес-функцией, компьютер всегда побеждал человека.

Полученные результаты позволяют утверждать, что в ходе данной работы был создан генетический алгоритм, который позволил построить выигрышную стратегию, обеспечивающую виртуальному сопернику победу над человеком в игре Quarto.

В дальнейшем предполагается создание полноценной электронной версии игры, поддерживающей различные режимы игры и дающие пользователю возможность настраивать уровень «интеллектуальности» виртуального соперника. Предполагается также создание мобильной версии игры.



Библиографический список

1. Иссаев С. Популярно о генетических алгоритмах // Algolist.Manual 2007. Июнь. URL: http://algolist.manual.ru (дата обращения: 02.10.2015).

2. Корнилов Е. Н. Программирование шахмат и других логических игр СПб.: БХВ-Петербург, 2005. 272 с.

3. Курейчик В. М., Родзин С. И. Эволюционные алгоритмы: генетическое программирование // Известия РАН. Теория и системы управления. 2002. N 1. С. 127-137.

4. Лукьянова Н. В., Куприянов Д. Ю., Роганова Н. А. Основы искусственного интеллекта: учебно-методическое пособие М.: МГИУ, 2012. 92 с.

5. Панченко Т. В. Генетические алгоритмы: учебно-методическое пособие Астрахань: Издательский дом «Астраханский университет», 2007. 87 с.

6. Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр: учебник СПб.: БХВ-Петербург, 2012. 432 с.

7. Печерский С. Л., Беляева А. А. Теория игр для экономистов. Вводный курс: учебное пособие Спб. Европа, 2001. 342 с.

8. Писарук Н. Н. Введение в теорию игр Минск: БГУ, 2015. 256 с.

9. Шагин В. Л. Теория игр: учебник и практикум для академического бакалавриата М.: Издательство Юрайт, 2015. 223 с.

10. Amos M., Coldridge J. A genetic algorithm for the Zen Puzzle Garden game // Natural computing. 2012. Vol. 11(3). Р. 353-359.

11. Axelrod R. The Evolution of Strategies in the Iterated Prisoner's Dilemma // Genetic Algorithms and Simulated Annealing London: Pitman, 1987. Р. 32-41.

12. Bullen T., Katchabaw M. J. Using Genetic Algorithms to Evolve Character Behaviours in Modern Video Games // Proceedings of the 2008 GameOn North America Conference. Montreal, Canada, August 2008. P. 12-20.

13. Cole N., Louis S. J., Miles C. Using a genetic algorithm to tune first-person shooter bots // In Proceedings of the IEEE congress on evolutionary computation, San Diego, CA, June 19-23 2004. CEC `04: 1. P.139-145.

14. Eshelman L. J. The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination // Foundations of Genetic Algorithms San Francisco: Morgan Kaufmann, 1991. P. 265 -283.

15. Holland J. H. Adaptation in Natural and Artificial Systems University of Michigan Press, 1975. 211 p.

16. Liaw, C. Evolving A Team In A First-Person Shooter Game By Using A Genetic Algorithm / C. Liaw, W. Wang, C. Tsai, C. Ko, G. Hao // Applied Artificial Intelligence. - 2013. Vol. 27(3). P. 199-212.

17. Quarto: Rules. Wimereux: Gigamic, 2014.

18. Sipper, M. Designing an evolutionary strategizing machine for game playing and beyond / M. Sipper, Y. Azaria, A. Hauptman, Y. Shichel // IEEE Transactions on Systems, Man, and Cybernetics. 2007. Part C: Applications and Reviews 37 (4). P. 583-593.

19. Whitley D. A Genetic Algorithm Tutorial // Statistics and Computing. 1994. Vol.4(2). P. 65-85.



Приложение А

Дерево игры 2х2

Приложение Б

Диаграмма классов, используемых в программном коде

Рисунок Б.1 Диаграмма классов



Приложение В

Результат одиночной игры рандомного игрока и компьютера

Ход игрока: Random

Переданная фигура: 0

Поле после хода:

-1 -1 -1 -1

-1 -1 -1 -1

-1 -1 -1 -1

-1 -1 -1 -1

Ход игрока: Computer

Переданная фигура: 6

Поле после хода:

-1 -1 -1 -1

-1 -1 -1 -1

-1 -1 -1 -1

0 -1 -1 -1

Ход игрока: Random

Переданная фигура: 13

Поле после хода:

-1 -1 -1 -1

-1 -1 -1 -1

-1 -1 6 -1

0 -1 -1 -1

Ход игрока: Computer

Переданная фигура: 12

Поле после хода:

-1 -1 -1 -1

-1 -1 13 -1

-1 -1 6 -1

0 -1 -1 -1

Ход игрока: Random

Переданная фигура: 15

Поле после хода:

-1 -1 -1 -1

-1 -1 13 -1

-1 12 6 -1

0 -1 -1 -1

Ход игрока: Computer

Переданная фигура: 3

Поле после хода:

-1 -1 -1 -1

-1 -1 13 -1

-1 12 6 -1

0 15 -1 -1

Ход игрока: Random

Переданная фигура: 7

Поле после хода:

-1 -1 -1 -1

-1 -1 13 3

-1 12 6 -1

0 15 -1 -1

Ход игрока: Computer

Переданная фигура: 10

Поле после хода:

-1 -1 -1 -1

-1 -1 13 3

-1 12 6 7

0 15 -1 -1

Ход игрока: Random

Переданная фигура: 11

Поле после хода:

-1 10 -1 -1

-1 -1 13 3

-1 12 6 7

0 15 -1 -1

Ход игрока: Computer

Переданная фигура: 4

Поле после хода:

-1 10 -1 -1

-1 11 13 3

-1 12 6 7

0 15 -1 -1

Победитель:Computer

Time - 00:04.34



Приложение Г

Результаты запуска 500 игр рандомного игрока против компьютера

B won seed - 0 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 1 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 2 Количество ходов Игрока А = 3 Количество ходов Игрока B = 3

B won seed - 3 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 4 Количество ходов Игрока А = 6 Количество ходов Игрока B = 6

B won seed - 5 Количество ходов Игрока А = 6 Количество ходов Игрока B = 6

B won seed - 6 Количество ходов Игрока А = 6 Количество ходов Игрока B = 6

B won seed - 7 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

B won seed - 8 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

- - - - - - - - - - - - - - - - -

B won seed - 333 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

B won seed - 334 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 335 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

Ничья Количество ходов Игрока А = 9 Количество ходов Игрока B = 8

B won seed - 337 Количество ходов Игрока А = 3 Количество ходов Игрока B = 3

B won seed - 338 Количество ходов Игрока А = 3 Количество ходов Игрока B = 3

B won seed - 394 Количество ходов Игрока А = 6 Количество ходов Игрока B = 6

Ничья Количество ходов Игрока А = 9 Количество ходов Игрока B = 8

B won seed - 396 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

B won seed - 397 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 398 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

B won seed - 399 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

B won seed - 400 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

- - - - - - - - - - - - - - - - -

B won seed - 480 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 481 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 482 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 483 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 484 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 485 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 486 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 487 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 488 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 489 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 490 Количество ходов Игрока А = 8 Количество ходов Игрока B = 8

B won seed - 491 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 492 Количество ходов Игрока А = 3 Количество ходов Игрока B = 3

B won seed - 493 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 494 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

B won seed - 495 Количество ходов Игрока А = 7 Количество ходов Игрока B = 7

B won seed - 496 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 497 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 498 Количество ходов Игрока А = 5 Количество ходов Игрока B = 5

B won seed - 499 Количество ходов Игрока А = 4 Количество ходов Игрока B = 4

A - 0

B - 498

Ничья - 2



Приложение Д

Руководство пользователя

Приложение Windows-forms состоит из 2 форм: форма авторизации и основная форма. При запуске приложения открывается форма авторизации (рисунок Д.1). На данной форме необходимо ввести имя или псевдоним, под которым пользователь желает играть. Так же на данной форме нужно решить против какого соперника он желает играть: компьютер или суперкомпьютер. Данное решение определяет, с каким уровнем сложности игрок будет проходить игру с компьютером - более легкий, или же с суперкомпьютером - сложный уровень. После ввода имени и выбора соперника необходимо нажать кнопку играть для того чтобы запустилась основная форма игры.

Рисунок Д.1 Форма авторизации

После того как пользователь авторизовался и выбрал себе соперника открывается основная форма игры (см. рисунок Д.2) Для того чтобы начать игру необходимо нажать одноименную кнопку. Первый ход совершает пользователь, ему необходимо выбрать для соперника какую-либо из фигур. Все доступные фигуры обозначены прямоугольниками и зашифрованы текстом в виде аббревиатур, например, белая низкая с выемкой квадратная фигура будет обозначена БНЕвКв. Они находятся внизу формы, по мере «расходования» фигур их количество в данной области сокращается.

Рисунок Д.2 Главная форма после нажатия кнопки «Начать игру»

После выбора какой-либо из фигур ход переходит к сопернику, и он ставит переданную ему фигуру, а также выбирает фигуру для пользователя.

Переданная фигура отображается справа от игрового поля под кнопками «Начать игру» и «Завершить игру». Там же отображаются подсказки с текущим действием, которое необходимо выполнить пользователю.

После того как соперник передал фигуру ее необходимо разместить на поле все доступные позиции для постановки фигуры подсвечены голубым цветом.

До тех пор, пока пользователь не поставит переданную фигуру, он не сможет выбрать фигуру для передачи сопернику (см. рисунок Д.3).

Рисунок Д.3 Основная форма после хода соперника

После каждого хода программа самостоятельно проверяет поля на наличие выигрышной комбинации, при обнаружении которой игра завершается и выводится сообщение об исходе игры: победа одного из игроков или же ничья (рисунок Д.4).

Рисунок Д.4 Пример сообщения об окончании игры

Приложение Е

Листинг программного кода

Класс судья

public class Judge

{

private GameSession game_session;

public GameSession GameSession // игровая сессия

{

get { return game_session; }

set { game_session = value; }

}

public void StartGame()// запуск игры

{

while ( !GameSession.IsFinished ) //пока нет признака конца игры ходим в цикле

{

if ( IsDraw( GameSession.Field ) ) //проверка есть ли ничья

{

GameSession.Winner = null;

break;

}

GameSession.CurrentPlayer.MakeMove( ref game_session ); //игрок делает ход

Log.Write(

Environment.NewLine

+ "Ход игрока: " + GameSession.CurrentPlayer.Name.ToString()

+ Environment.NewLine

+ "Переданная фигура: " + GameSession.PassedFigure.Code.ToString()

+ Environment.NewLine

+ "Поле после хода: " + Environment.NewLine + GameSession.Field.ToString()

);

GameSession.IsFinished = IsGameOver( GameSession.Field ); //проверка поля после хода, закончилась ли игра?

if ( GameSession.IsFinished == true ) //игра закончена победитель текущий игрок

{

GameSession.Winner = GameSession.CurrentPlayer;

Log.Write( Environment.NewLine + "Победитель:" + GameSession.CurrentPlayer.Name.ToString() );

}

GameSession.SwitchPlayer();//ход переходит другому игроку

}

}

private bool IsGameOver( Field field ) //проверка поля на начилие выигрышных комбинаций

{

return Utils.FieldContainsCombination( field );

}

private bool IsDraw( Field field ) //проверка ненаступила ли ничья?

{

return field.AvailablePositions.Count == 0;

}

}

Класс игровая сессия

public class GameSession

{

private Field field;

private Figure passedFigure;

private Player playerA;

private Player playerB;

private Player currentPlayer;

private int lastMovePos;

public int LastMovePos// последняя занятая позиция (куда поставлена переданная фигура)

{

get { return lastMovePos; }

set { lastMovePos = value; }

}

private Player winner;

public Player CurrentPlayer //Текущий игрок

{

get { return currentPlayer; }

private set { currentPlayer = value; }

}

private bool is_finished;

public bool IsFinished

{

get { return is_finished; }

set { is_finished = value; }

}

public Field Field //игровое поле

{

get { return field; }

set { field = value; }

}

public Figure PassedFigure //переданная фигура

{

get { return passedFigure; }

set { passedFigure = value; }

}

public Player PlayerA //первый игрок

{

get { return playerA; }

set { playerA = value; }

}

public Player PlayerB //второй игрок

{

get { return playerB; }

set { playerB = value; }

}

public Player Winner //победитель

{

get { return winner; }

set { winner = value; }

}

public GameSession( Player A, Player B )

{

this.Field = new Field( 4 );

this.IsFinished = false;

this.PlayerA = A;

this.PlayerB = B;

this.CurrentPlayer = PlayerA;

this.PassedFigure = new Figure();

}

public void SwitchPlayer()//Переход хода между игроками

{

if ( this.CurrentPlayer.Equals( PlayerA ) )

this.CurrentPlayer = PlayerB;

else

this.CurrentPlayer = PlayerA;

}

}

Класс игровое поле

public class Field : ICloneable

{

private int[ , ] cells;

private int size;

public int Count { get { return cells.Length; } }

public List<Int32> AvailableFigures { get; set; } //доступные фигуры (еще не стоят на поле)

public List<Int32> AvailablePositions { get; set; }//доступные позиции (еще не занятые фигурами на поле)

public int Size { get { return size; } private set { size = value; } }

public int[ , ] Cells { get { return cells; } }

public Field( int size )

{

AvailableFigures = Enumerable.Range( 0, 16 ).ToList();

AvailablePositions = Enumerable.Range( 0, 16 ).ToList();

Size = size;

cells = new int[ size, size ];

for ( int i = 0; i < size; i++ )

for ( int j = 0; j < size; j++ )

cells[ i, j ] = -1;

}

public int this[ int index ] //для обращения к полю по одному индексу

{

get { return cells[ index / size, index % size ]; }

set

{

int currentValue = cells[ index / size, index % size ];

cells[ index / size, index % size ] = value;

if ( currentValue == value && value != -1 )

throw new ArgumentException("Something wrong...");

if ( value != -1 )

{

AvailableFigures.Remove( value );

AvailablePositions.Remove( index );

}

// Возвращаем фигуру и позицию обратно

if ( currentValue != -1 && value == -1 )

{

AvailableFigures.Add( currentValue );

AvailablePositions.Add( index );

}

}

}

public int this[ int row, int column ] //для обращения по двум индесам

{

get { return cells[ row, column ]; }

set

{

cells[ row, column ] = value;

if ( value != -1 )

{

AvailableFigures.Remove( value );

AvailablePositions.Remove( row * size + column );

}

}

}

public int GetIndex( int value ) //получение индекса на поле для фигуры

{

for ( int i = 0; i < size; i++ )

for ( int j = 0; j < size; j++ )

if ( cells[ i, j ] == value )

return i * Size + j;

return -1;

}

public int[] GetRow( int row ) //получить строку

{

int[] tempRow = new int[ Size ];

for ( int i = 0; i < Size; i++ )

{

tempRow[ i ] = cells[ row, i ];

}

return tempRow;

}

public int[] GetColumn( int column ) //получить столбец

{

int[] tempColumn = new int[ Size ];

for ( int i = 0; i < Size; i++ )

{

tempColumn[ i ] = cells[ i, column ];

}

return tempColumn;

}

public int[] GetDiagonal( string type ) //получить диагональ

{

switch ( type )

{

case "Left":

int[] tempLeftDiagonal = new int[ Size ];

for ( int i = 0; i < Size; i++ )

{

tempLeftDiagonal[ i ] = cells[ i, i ];

}

return tempLeftDiagonal;

case "Right":

int[] tempRightDiagonal = new int[ Size ];

for ( int i = Size - 1, j = 0; i >= 0; i--, j++ )

{

tempRightDiagonal[ j ] = cells[ j, i ];

}

return tempRightDiagonal;

default: throw new ArgumentException( "Тип диагонали может быть только Left или Right!" );

}

}

public int[] GetRowIndexes( int row )

{

int[] tempRowIndexes = new int[ Size ];

for ( int i = 0; i < Size; i++ )

{

tempRowIndexes[ i ] = row * Size + i;

}

return tempRowIndexes;

}

public int[] GetColumnIndexes( int column )

{

int[] tempColumnIndexes = new int[ Size ];

for ( int i = 0; i < Size; i++ )

{

tempColumnIndexes[ i ] = i * Size + column;

}

return tempColumnIndexes;

}

public int[] GetDiagonalIndexes( string type )

{

switch ( type )

{

case "Left":

int[] tempLeftDiagonal = new int[ Size ];

for ( int i = 0; i < Size; i++ )

{

tempLeftDiagonal[ i ] = i + i * Size;

}

return tempLeftDiagonal;

case "Right":

int[] tempRightDiagonal = new int[ Size ];

for ( int i = Size - 1, j = 0; j < Size; j++ )

{

tempRightDiagonal[ j ] = i * ( j + 1 );

}

return tempRightDiagonal;

default: throw new ArgumentException( "Тип диагонали может быть только Left или Right!" );

}

}

public List<int[]> GetArraysByIndex( int index )

{

List<int[]> result = new List<int[]>();

int rowOffset = index / 4;

int columnOffset = index % 4;

result.Add( this.GetRow( rowOffset ) );

result.Add( this.GetColumn( columnOffset ) );

if ( this.GetDiagonalIndexes( "Left" ).Contains( index ) )

result.Add( this.GetDiagonal( "Left" ) );

if ( this.GetDiagonalIndexes( "Right" ).Contains( index ) )

result.Add( this.GetDiagonal( "Right" ) );

return result;

}

public int TakeRandomFigure()//берем случайную фигуру

{

// важный момент. когда мы берем фигуру мы сдвигаем последовательность рандома на 1 ячейку

// => вся случайность становится другой

int randomIndex = Utils.Rand.Next( AvailableFigures.Count );

return AvailableFigures[ randomIndex ];

}

public void FillRow( int row, int [] figures, int [] positions ) //заполняем строку

{

for ( int i = 0; i < Size; i++ )

{

figures[ i ] = cells[ row, i ];

positions[ i ] = row * Size + i;

}

}

public void FillColumn( int column, int[] figures, int[] positions ) //заполняем столбец

{

for ( int i = 0; i < Size; i++ )

{

figures[ i ] = cells[ i, column ];

positions[ i ] = i * Size + column;

}

}

public void FillDiagonal( string type, int[] figures, int[] positions ) //заполняем диагональ

{

switch ( type )

{

case "Left":

for ( int i = 0; i < Size; i++ )

{

figures[ i ] = cells[ i, i ];

positions[ i ] = i + i * Size;

}

break;

case "Right":

for ( int i = Size - 1, j = 0; j < Size; j++ )

{

figures[ j ] = cells[ j, i - j ];

positions[ j ] = i * ( j + 1 );

}

break;

default: throw new ArgumentException( "Тип диагонали может быть только Left или Right!" );

}

}

public object Clone()//клонирование поля (просто копировать нельзя)

{

var clone = new Field( Size );

for ( int i = 0; i < size; i++ )

for ( int j = 0; j < size; j++ )

clone[ i, j ] = this[ i, j ];

return clone;

}

public override string ToString()//для печати в лог

{

string field = String.Empty;

for ( int i = 0; i < size; i++ )

{

for ( int j = 0; j < size; j++ )

{

field += Cells[ i, j ].ToString() + ", ";

}

field += Environment.NewLine;

}

return field;

}

}

Абстрактный класс игрок

public abstract class Player

{

private string name;

public string Name

{

get { return name; }

set { name=value; }

}

public Player() { }

public Player( string name )

{

this.Name = name;

}

public abstract void MakeMove( ref GameSession game ); //сделать ход

}

Класс рандомный игрок

public class RandomPlayer: Player

{

public RandomPlayer( string name ): base( name )

{}

public override void MakeMove(ref GameSession game) //сделать ход

{

if ( game.PassedFigure.Code == -1 ) // если первый ход то передаем фигуру

{

Figure f = new Figure( game.Field.TakeRandomFigure() );

game.PassedFigure = f;

}

else // совершаем ход: ставим фигуру, выбираем фигуру для передачи сопернику

{

int randomIndex = Utils.Rand.Next( game.Field.AvailablePositions.Count );

int newPosition = game.Field.AvailablePositions[ randomIndex ];

game.Field[ newPosition ] = game.PassedFigure.Code;

if ( game.Field.AvailablePositions.Count != 0 )

{

Figure f = new Figure( game.Field.TakeRandomFigure() );

game.PassedFigure = f;

}

}

}

}

Класс виртуальный игрок компьютер

public class Computer : Player

{

private int[] Combination { get; set; }

public Computer( string name ) : base( name ) { }

public static double FitnessFunction( Field field, int [] combination ) //фитнес-функция

{

Field clone = field.Clone() as Field;

double win = 10;

double loose = -10;

double result = 0;

double noCombo = -1;

int size = combination.Length / 2;

bool myMove = true;

for ( int i = 0; i < size; i++ )

{

int figure = combination[ i ];

int position = combination[ i + size ];

int bestPosition = Utils.CanWinWithFigure( clone, figure );

bool gameOver = bestPosition != -1 ? true : false;

clone[ position ] = figure;

if ( gameOver )

{

if ( myMove && bestPosition == position ) // так же сравниваем тек.позицию с наилучшей... иначе это не победа

{

result += win * ( combination.Length - i ); // чем ближе победа тем лучше...

break;

}

else

{

result += loose * ( combination.Length - i ); // чем ближе проигрыш тем хуже...

break;

}

}

else

result += noCombo;

myMove = !myMove;

}

return result;

}

//запуск алгоритма тут

public override void MakeMove( ref GameSession game ) //сделать ход

{

Field currentField = game.Field;

// Ищем лучшую комбинацию используя текущую ситуацию на поле.

if ( game.PassedFigure.Code == -1 )

game.PassedFigure = new Figure( currentField.TakeRandomFigure() );

GA GenAlgo = new GA( currentField, game.PassedFigure );

GenAlgo.FitnessFunction = new GAFitnessFunction( FitnessFunction );

GenAlgo.FitnessFile = AppDomain.CurrentDomain.BaseDirectory + "\\Log\\" + "fitness.txt";

GenAlgo.Elitism = true;

int [] combination = GenAlgo.Go();

// Выбираем фигуру сопернику.

int position = combination[ combination.Length / 2 ];

int nextFigure = combination[ 1 ];

game.Field[ position ] = game.PassedFigure.Code;

game.LastMovePos = position;

game.PassedFigure = new Figure( nextFigure );

}

}

Класс виртуальный игрок суперкомпьютер

public class SuperComputer : Player

{

public SuperComputer( string name ) : base( name ) { }

public static double PessimisticFitnessFunction( Field field, int[] combination ) //пессимистичная финтес-функция

{

Field clone = field.Clone() as Field;

double result = 0, win = 10, loose = -10;

int size = combination.Length / 2;

bool myMove = true;

Stack<int> history = new Stack<int>();

for ( int i = 0; i < size; i++ )

{

int figure = combination[ i ];

int position = combination[ i + size ];

history.Push( figure );

history.Push( position );

int bestPosition = Utils.CanWinWithFigure( clone, figure );

bool gameOver = bestPosition != -1 ? true : false;

if ( gameOver )

{

if ( myMove && bestPosition == position ) // так же сравниваем тек.позицию с наилучшей... иначе это не победа

{

List<int> acceptableFiguresPool = clone.AvailableFigures

.Where( x => Utils.CanWinWithFigure( clone, x ) == -1 ).ToList();

// Победа это уже хорошо, НО, давайте посмотрим насколько она реальна? Насколько глупо сходил враг?

result += win * ( combination.Length - i ); // чем ближе победа тем лучше...

clone[ position ] = figure; // перед проверкой комбинации поставим тек. фигуру

if ( !Utils.FieldContainsCombination( clone ) ) // draw

result /= 3;

clone[ position ] = -1; // откатим текущую фигуру

// Проверим есть ли у врага другие варианты, при которых он не проиграет, скорей всего он выберет их...

if ( acceptableFiguresPool.Count == 0 )

{

// У врага не было выбора, что давать... Видимо ошибся раньше.

// Сделать откат на позицию назад и посмотреть может ли он поставить фигуру по-другому.

if ( clone.AvailableFigures.Count <= 4 && i != 0 )

{

history.Pop();

history.Pop();

while ( history.Count > 0 )

{

int previousPosition = history.Pop();

int previousFigure = history.Pop();

clone[ previousPosition ] = -1;

var safePositions = Utils.GetSafePositions( clone, previousFigure, 0 );

bool ourPositionSafe = safePositions.Any( x => x == previousPosition );

if ( !ourPositionSafe && safePositions.Count != 0 )

{

result += loose * ( combination.Length - ( i - 1 ) );

break;

}

BranchRater rater = new BranchRater( clone, previousFigure );

rater.IsFirstMove = true;

double previousRaiting = rater.Rate();

if ( rater.PositionsRates.ContainsKey( previousPosition ) )

{

double safePositionRate = rater.PositionsRates[ previousPosition ];

if ( safePositionRate == rater.PositionsRates.Min( x => x.Value ) )

{

// Худшая ветка для врага выбрана...

result += loose * ( combination.Length - ( i - 1 ) );

break;

}

}

previousPosition = history.Pop();

clone[ previousPosition ] = -1;

history.Pop();

}

}

else

if ( combination.Length > 2 && i != 0 ) // нет истории для просмотра

{

int previousFigure = combination[ i - 1 ];

int previousPosition = combination[ i + size - 1 ];

clone[ previousPosition ] = -1;

var safePositions = Utils.GetSafePositions( clone, previousFigure, 0 );

bool ourPositionSafe = safePositions.Any( x => x == previousPosition );

if ( !ourPositionSafe && safePositions.Count != 0 )

result += loose * ( combination.Length - ( i - 1 ) );

}

}

else

{

if ( acceptableFiguresPool.Any( x => x != figure ) )

// У врага был выбор, комбинация плохая, не включила его

result += loose * ( combination.Length - ( i - 1 ) );

}

break;

}

else

{

result += loose * ( combination.Length - i ); // чем ближе проигрыш тем хуже...

break;

}

}

clone[ position ] = figure;

myMove = !myMove;

}

return result;

}

public override void MakeMove( ref GameSession game ) //сделать ход

{

Field currentField = game.Field;

if ( game.PassedFigure.Code == -1 )

game.PassedFigure = new Figure( currentField.TakeRandomFigure() );

CGA CustomGA = new CGA( currentField, game.PassedFigure );

CustomGA.FitnessFunction = new CGAFitnessFunction( PessimisticFitnessFunction );

CustomGA.FitnessFile = AppDomain.CurrentDomain.BaseDirectory + "\\Log\\" + "fitnessCustom.txt";

// Ищем лучшую комбинацию используя текущую ситуацию на поле

int[] combination = CustomGA.GetCombination();

// Выбираем фигуру сопернику.

int position = combination[ combination.Length / 2 ];

int nextFigure = combination[ 1 ];

game.Field[ position ] = game.PassedFigure.Code;

game.LastMovePos = position;

game.PassedFigure = new Figure( nextFigure );

}

}

Размещено на Allbest.ru

...