Внимание! Это сайт переехал на www.simplecoding.org
С этой игрой я познакомился, когда играл в "Космических рейнджеров" (это было задание в одном из квестов). Игра показалась мне интересной, и я решил написать свою версию. При этом мне захотелось добавить возможность регулирования уровня сложности.
Правила игры очень простые. Два игрока по очереди кладут в корзину шарики трех цветов (красные, синие и зеленые). Всего нужно положить по три шарика каждого цвета. Каждый игрок за один ход может положить один или несколько шариков только одного цвета. Например, два красных или три синих, или один зеленый и т.д. Выигрывает тот, кто кладет последний шарик.
Давайте разберем подробнее принцип выбора оптимального
хода. Если в корзине нет шариков, то можно сделать девять различных
ходов, во всех остальных случаях количество возможных ходов будет
меньшим. Глубина анализа (т.е. количество просчитываемых ходов) будет
задаваться текущим уровнем сложности. Допустим, она равна трем. Это
значит, что необходимо проверить все возможные наши ходы, далее
просчитать все ходы игрока, а затем снова проанализировать, как мы
можем после хода игрока.
Для сохранения всех этих данных я использовал двумерный массив.
Количество столбцов соответствует максимально возможному количеству
ходов (девяти), а количество строк – глубине анализа (трем).
Вы, наверное, заметили, что размер массива не позволяет сохранить
информацию обо всех возможных ходах. Но это нам и не требуется, ведь мы
хотим выбрать оптимальный ход на данный момент, а на следующем ходу мы
проводим новый анализ. В массив мы будем записывать информацию о том,
приводит данных ход к победе или нет. При этом в первой строке каждая
ячейка соответствует возможному ходу. Если ход возможен и приводит к
победе (корзина заполнена) записываем в соответствующую ячейку
"1", если после хода корзина не заполнена
– "0", и "-127" если
ход не возможен. Во второй и следующих строках записываем информацию
только о лучших ходах. Т.е. просчитываем мы все возможные ходы, но
информацию пишем только о лучшем из них.
 |
 |
|
 |
|
|
 |
|
|
Рис.1
Рассмотрим следующий пример. Допустим, корзина заполнена так, как показано на рис.1 (три зеленых шарика, один синий и один красный). В соответствии с приведенными правилами будет составлен следующий массив (первые 3 элемента каждой строки массива соответствуют красному цвету, вторые 3 – синему, третьи 3 – зеленому):
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
| 0 | 0 | -127 | 0 | 0 | -127 | -127 | -127 | -127 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
Массив 1
Элементы первой строки соответствуют возможным ходам. У нас есть четыре возможных варианта ходов (1 красный, 2 красных, 1 синий, 2 синих), при этом ни один из вариантов хода не приводит к победе. Поэтому элементы 1, 2, 4, 5 первой строки имеют значение 0 (ход возможен, но не приводит к победе). Все остальные элементы первой строки имеют значение "-127" (ход не возможен). Вторая строка содержит результаты анализа возможного хода игрока. Как видно, элементы 2 и 5 содержат единицы. Это означает, что если мы сделаем ход, соответствующий ячейкам 2 или 5 первой строки (положим 2 синих или 2 красных шарика), то компьютер сможет сделать победный ход (положить 2 красных или 2 синих шарика соответственно). Третья строка содержит четыре единицы (элементы 1, 2, 4 и 5). Тут нужны некоторые пояснения. С элементами 1 и 4 понятно – они означают, что какой бы ход ни сделал игрок (вторая строка массива), наш следующий ход будет победный. Но почему элементы 2 и 5 содержат единицы? Дело в том, что во время анализа просчитываем ВСЕ возможные ходы, в том числе и "глупые". Рассмотрим подробно второй столбец массива. Он соответствует ходу двумя красными шариками. Этот ход не приводит к победе (ноль во второй ячейке первой строки). После этого у игрока есть два варианта: положить один зеленый шарик ("глупый" ход), или положить два зеленых шарика (победа). Т.к. во время анализа в таблицу мы заносим информацию только о лучшем ходе, то вторая ячейка второй строки содержит "1". Единица в третьей строке появилась потому, что мы можем победить, если игрок положит один зеленый шарик.
После этого нам нужно проанализировать данные в таблице. Очевидно, что нужно сделать ход либо одним красным (ячейка 1 первой строки), либо одним синим (ячейка 4 первой строки), т.к. они однозначно приводят к победе. Я выполнил этот анализ следующим образом. В первую очередь создаем новый одномерный массив, каждая ячейка которого соответствует возможному ходу. Затем заполняем его по следующим правилам. Если элемент массива 1 содержит "-127", то мы копируем его в соответствующий элемент нового массива. Каждой строке массива 1 присваиваем определенные вес в порядке убывания (нижней строке соответствует – 1, предпоследней – 2 и т.д.). Далее суммируем элементы столбца, учитывая их вес, т.е. при суммировании мы умножаем число на его вес, кроме этого элементы четных строк нужно умножить на "-1" (например, для второго столбца в нашем примере нужно вычислить выражение 0*3 + (-1)*2 + 1*1). В результате получится, что максимальное значение будут иметь те элементы, соответствующие столбцы которых, содержат "1" в нечетных строках (наш ход). При этом число будет тем больше, чем ближе единица к первой строке.
| 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 |
| 1 | -1 | -127 | 1 | -1 | -127 | -127 | -127 | -127 |
Массив 2
Далее нам остается только найти максимальный элемент в массиве 2 (если их несколько – выбираем любой случайным образом). Этот элемент соответствует оптимальному ходу.
Программа состоит из следующих частей:
- модуля главной формы;
- модуля окна "О программе";
- модуля окна "Настройки";
- модуля окна "Результаты";
- класса Player (файлы "Player.cpp",
"Player.h");
- класса Basket (файлы "Basket.cpp",
"Basket.h").
Как вы понимаете, наибольший интерес представляют последние два. Класс Basket предоставляет функции необходимые для работы с корзиной (в файле "Basket.h" перед объявлением каждой функции описано ее назначение). Экземпляр класса Player можно использовать только с уже созданным экземпляром класса Basket. Класс Player выполняет функции компьютерного игрока (анализ хода и сам ход). Использовать классы очень просто. Сначала нужно создать класс Basket. При его создании можно указать начальное количество шариков. Далее создаем класс Player, ему нужно передать указатель на экземпляр класса Basket, и указать глубину анализа (подробнее в файле "Player.h"). После этого для выполнения компьютером очередного хода нужно вызывать функцию NextStep класса Player.
Пример:
Basket b(1, 1, 1); //создан экземпляр класса Basket содержащий по одному шарику каждого цвета
Player p(&b, 3); //создан экземпляр класса Player, глубина анализа установлена равной 3
Если вы хотите создать свой оригинальный интерфейс программы (например, добавить анимацию), вам ничто не мешает это сделать. Классы Basket и Player не используют VCL и, поэтому, должны работать с любой средой разработки.