Программа-игра «Ним»

Программа-игра «Ним»

Системный анализ

Задача состоит в написании логической игры, основанной на конкретной математической раскладке. Главным критерием является формулирование алгоритма для реализации поставленной задачи в соответствии со всеми представленными требованиями.

Обозначим наиболее существенные проблемы выбора, с которыми предстоит столкнуться:

1. Проектирование математической модели решения поставленной задачи.

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

3. Разработка пользовательского интерфейса и выбор среды программирования.

Рассмотрим возможные пути решения данных проблем:

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

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

2. С помощью функциональных связей внутри программы следует поставить в однозначное соответствие поведение объектов визуальных (графических) с объектами программными, непосредственно участвующими в формировании поведения программы. Следовательно, основное внимание необходимо уделить технологии разработки программных модулей и организации их взаимосвязи, а также вопросу передачи управления в модулях. В этой связи была выстроена интуитивно-понятная, рациональная связь нескольких обработчиков (функций, отслеживающих действия конечного пользователя, в нашем случае — клики) событий с методами центрального алгоритмического класса программы (ЦАКП).

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

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

Выполнение этой и подобных задач выгодно производить с помощью специализированных пакетов программ-компиляторов с вложенными библиотеками и методами работы с графикой. В данной работе использовался программный набор C++ Builder 2007 from Borland — среда со стандартным компилятором C++.

Анализ требований

На данном этапе были выявлены основные требования для выбора способа решения задачи:

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

Визуализация была реализована с помощью комбинации нужных компонентов типа Shape (встроенное средство среды, позволяет избежать использования сторонних изображений в роли «камешка»), Panel, Button, RadioButton, MainMenu. Такой выбор для логической игры не случаен — предполагается сконцентрировать внимание пользователя на игровом процессе с точки зрения логики игры. Помимо всего прочего, использование именно встроенных средств уменьшит ресурсо-потребление программного продукта, позволит несколько увеличить быстродействие. Графическое представление должно быть понятно любому пользователю игры.

2. Действия программы в лице искусственного интеллекта должны быть подкреплены рациональным поведением «компьютера» в игровом процессе.

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

3. Разработать удобную и понятную систему выбора режима игры и управления (настройки).

Для решения поставленной задачи использовались так называемые RadioButton, расположенные на специальных тематических панелях. Всего 4 элемента управления в виде стандартных переключателей на двух панелях («Игрок № 2» и «Первым ходит») в состоянии заменить введение дополнительных форм, а также создание клавиш и пр. На этапе кодирования учитывались все возможные ситуации расстановки переключателей, а на этапе тестирования обрабатывались нежелательные исключения. Кроме RadioButton в программном коде фигурирует объект типа TButton, представляющий собой кнопку управления. Предполагается, что пользователь-игрок имеет право обдумать свой ход и принять взвешенное решение по удалению определенных шариков с формы.

4. Предусмотреть надежную систему контроля правил игры и поведения конечного пользователя.

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

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

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

Проектирование

В данной работе используется метод восходящего проектирования.

Технология визуального программирования, поддерживаемая средой разработки Borland C++ Builder, позволяет достаточно легко, быстро и эффективно проектировать интерфейс взаимодействия пользователя с системой на основе библиотек визуальных компонентов.

В первую очередь необходимо создать модуль «снятия» камешков с формы и основу главного игрового класса со вспомогательными методами, обрабатывающими специальные ячейки памяти. Эти ячейки могут принимать только два значения «правда» или «ложь». В программе, в качестве вместилища таких ячеек, можно использовать три булевских массива размерами, 3, 2, 1 ячеек памяти соответственно. Благодаря первичной связи модулей, необходимо наладить обращение пользователя к объектам типа Shape, которое прямым образом будет отражено на поведении трех вышеперечисленных массивов. Уже на основе состояния зарезервированных ячеек памяти программа будет выстраивать игровое решение.

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

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

При таком подходе выполняется требование 5, положенное в разделе «Анализ требований».

Взаимодействие основных модулей игры отражено в схеме алгоритма на рисунке 1. Это общее представление структуры программы.

Рисунок 1

Более детальный анализ связей и модульной зависимости игры рассмотрен на рисунке 2 и в блоке «Кодирование».

Рисунок 2

При главном окне программы содержится набор вложенных обработчиков событий, созданных средой и настроеннных на однозначную обработку действий пользователя. Сюда можно отнести и RadioButton, и Button, и сами объекты Shape.

Методы поддержки принадлежат непосредственно ЦАКП (центральному алгоритмическому классу программы). Они обрабатывают поступающие значения, передают их в класс, который затем возвращает результат итерации в главное окно программы посредством манипуляций объектами главной формы.

Анализ мотиваций искусственного интеллекта показал следующую зависимость для игры с {3,2,1} кучками объектов: тот, кто берет первый камешек, при правильной игре оппонента, должен понести поражение. Наиболее красочно эту зависимость описывает граф, представленный на рисунке 3.

Рисунок 3

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

Разработка алгоритма итерации игрового цикла кратко представлена на рисунке 4.

Рисунок 4

логический игра математический программа

Кодирование

Основной функциональный цикл программы, отображенный на рисунке 4, запускается благодаря клику по единственной управляющей кнопке проекта: Button1.

Ниже представлено описание ЦАКП (центрального алгоритмического класса программы).

// ;

class CGame {

private:

bool list1 [3];

bool list2 [2];

bool list3 [1];

bool gamer; // определяет, чей ход

int index; // проверяет, правильно-ли передан ход

int mod1, mod2, mod3; // измеряет длину list’а

public:

CGame ();

~CGame ();

// устанавливает разводящего игрока

void setGamer (TPanel *Gamer1, TPanel *Gamer2);

// перекрашивает шарики по клику

void color (TShape *Shape);

// задает граничное условие одного ряда

bool useHelp (TShape *Shape1, TShape *Shape2,

TShape *Shape3, TShape *Shape4,

TShape *Shape5, TShape *Shape6);

// задает граничное условие одного хода, определяет игрока

bool indexator (TPanel *Gamer1, TPanel *Gamer2);

// фиксирует снятые шарики в памяти

void fixap (int num, TShape *Shape);

// программно удаляет шарики с формы

void solution (TShape *Shape1, TShape *Shape2,

TShape *Shape3, TShape *Shape4,

TShape *Shape5, TShape *Shape6);

// определяет победителя

bool win (TPanel *Gamer1, TPanel *Gamer2);

// создает новую игру

void endGame (TShape *Shape1,

TShape *Shape2, TShape *Shape3, TShape *Shape4,

TShape *Shape5, TShape *Shape6, TButton *Button1, TRadioButton * RB1,

TRadioButton * RB2, TRadioButton * RB3, TRadioButton * RB4);

// управляет доступом к кнопке передачи хода и переключателям

void obj (TShape *Shape1, TShape *Shape2,

TShape *Shape3, TShape *Shape4,

TShape *Shape5, TShape *Shape6,

TButton *Button1, TRadioButton *RadioButton1,

TRadioButton *RadioButton2, TRadioButton *RadioButton3,

TRadioButton *RadioButton4);

// ;

// процедура, просчитывающая ход компьютера

void compClick (void);

};

Рассмотрим ход компьютера. Ход игрока выполняется прямо пропорционально проходу очередной итерации.

// ;

void CGame: compClick ()

{

if (list1 == true && list1 == true && list1 == true &&

list2 == true && list2 == true &&

list3 == true) {

if (gamer) gamer = false;

else gamer = true;

}

if (gamer) gamer = false;

else gamer = true;

// ;

// ;

// если одна строка равна другой

if ((mod1 == mod2) && (mod1≠ mod3) && (mod2≠ mod3)

&& mod1≠ 0 && mod3≠ 0) {

if (! list3 [0]) {

list3 = true;

mod3 -= 1;

}

else if (! list1 [2]) {

list1 = true;

mod1 -= 1;

}

else if (! list1 [1]) {

list1 = true;

mod1 -= 1;

}

else if (! list1 [0]) {

list1 = true;

mod1 -= 1;

}

}

else if ((mod1 == mod3) && (mod1≠ mod2) && (mod3≠ mod2)

&& mod2≠ 0) {

if (! list2 [0]) {

list2 = true;

mod2 -= 1;

}

if (! list2 [1]) {

list2 = true;

mod2 -= 1;

}

}

else if ((mod2 == mod3) && (mod1≠ mod2) && (mod1≠ mod3)

&& mod1≠ 0) {

if (! list1 [0]) {

list1 = true;

mod1 -= 1;

}

if (! list1 [1]) {

list1 = true;

mod1 -= 1;

}

if (! list1 [2]) {

list1 = true;

mod1 -= 1;

}

}

// ;

// случаи завершения игры

else if ((mod1 == 0 && mod2 == 0)) {

list3 = true;

mod3 -= 1;

}

else if (mod1 == 0 && mod3 == 0) {

list2 = true; list2 = true;

mod2 -= 2;

}

else if (mod2 == 0 && mod3 == 0) {

list1 = true; list1 = true; list1 = true;

mod1 -= 3;

}

// ;

// случай равенства трех

else if ((mod1 == mod2) && (mod2 == mod3) && (mod1 == mod3)) {

if (! list2 [0]) {

list2 = true;

mod2 -= 1;

}

else {

list2 = true;

mod2 -= 1;

}

}

// ;

// реккурентные сравнения: 1 и 2

else if ((mod1 > mod2) && mod3 == 0) {

if (! list1 [0]) {

list1 = true;

mod1 -= 1;

}

else if (! list1 [1]) {

list1 = true;

mod1 -= 1;

}

else if (! list1 [2]) {

list1 = true;

mod1 -= 1;

}

}

else if ((mod1 < mod2) && mod3 == 0) {

if (! list2 [0]) {

list2 = true;

mod2 -= 1;

}

else if (! list2 [1]) {

list2 = true;

mod2 -= 1;

}

}

// ;

// реккурентные сравнения: 2 и 3

else if (mod1 == 0 && mod2 > mod3) {

list2 = true;

mod2 -= 1;

}

// ;

// реккурентные сравнения: 1 и 3

else if (mod2 == 0 && mod1 > mod3) {

if (! list1 [0]) {

list1 = true;

mod1 -= 1;

}

if (! list1 [1]) {

list1 = true;

mod1 -= 1;

}

}

// ;

// патовые ситуации: 1 и 2

else if (mod1 == mod2 && mod3 == 0) {

if (! list1 [0]) {

list1 = true;

mod1 -= 1;

}

else if (! list1 [1]) {

list1 = true;

mod1 -= 1;

}

else if (! list1 [2]) {

list1 = true;

mod1 -= 1;

}

}

else if (mod1 == mod3 && mod2 == 0) {

list3 = true;

mod3 -= 1;

}

else if (mod2 == mod3 && mod1 == 0) {

list3 = true;

mod3 -= 1;

}

}

Как видно из функции, определяющей ход компьютера, за основу взяты условные длины массивов объекта класса. В результате выполнения программы они изменяются по модулю, однако точный учет изменений необходим для принятия обоснованного решения в игровой ситуации. Дело в том, что «компьютер», если он ходит первым — максимально отсрочить вое поражение и, если он ходит вторым, подводить всякие две строки к равному значению за итерацию. В таком случае, дублируя ходы оппонента удастся добиться победы. Это есть основной алгоритм, согласно которому компьютер отвечает реальным угрозам.

Перекрашивание объектов производится по заданному шаблону в специальной функции-методе ЦАКП. color (), вызываемой прямо из-под объекта.

// ;

void CGame: color (TShape *Shape)

{

if (Shape->Brush->Style≠ bsClear)

{

Shape->Brush->Style = bsClear;

index++;

}

else

{

Shape->Brush->Style = bsSolid;

Shape->Brush->Color = clAqua;

index -;

}

}

Далее программа, уже по снятым «образам» регистрирует этот факт в массивах булевых значений. За это отвечает метод. fixap ().

// ;

void CGame: fixap (int num, TShape *Shape)

{

switch (num) {

case 1:

if (Shape->Brush->Style == bsClear) {

list1 = true;

mod1 -;

}

else {

list1 = false;

mod1++;

}

break;

case 2:

if (Shape->Brush->Style == bsClear) {

list1 = true;

mod1 -;

}

else {

list1 = false;

mod1++;

}

break;

case 3:

if (Shape->Brush->Style == bsClear) {

list1 = true;

mod1 -;

}

else {

list1 = false;

mod1++;

}

break;

case 4:

if (Shape->Brush->Style == bsClear) {

list2 = true;

mod2 -;

}

else {

list2 = false;

mod2++;

}

break;

case 5:

if (Shape->Brush->Style == bsClear) {

list2 = true;

mod2 -;

}

else {

list2 = false;

mod2++;

}

break;

case 6:

if (Shape->Brush->Style == bsClear) {

list3 = true;

mod3 -;

}

else {

list3 = false;

mod3++;

}

break;

}

}

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

На этом рабочая итерация программы завершается. Дальше алгоритм поведет себя в соответствии с расставленными переключателями. А доступ к переключателям имеет только конечный пользователь.

Ниже представлен алгоритм обработки нажатий пользователя.

Тестирование

логический игра математический программа

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

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

1. Уязвимость «двух линий».

2. Уязвимость передачи хода.

3. Уязвимость в условиях определения победителя.

4. Некоторые внутренние конфликты (исключения).

1. Дописанный метод ЦАКП, проверяющий правильность взятия игровых объектов. Это основное и наиболее важное правило игры: брать камни можно только из одной кучки.

// ;

bool CGame: useHelp (TShape *Shape1, TShape *Shape2,

TShape *Shape3, TShape *Shape4,

TShape *Shape5, TShape *Shape6)

{

if (((Shape1->Brush->Style == bsClear || Shape2->Brush->Style == bsClear

|| Shape3->Brush->Style == bsClear) &&

(Shape4->Brush->Style == bsClear || Shape5->Brush->Style == bsClear

|| Shape6->Brush->Style == bsClear))

||

((Shape4->Brush->Style == bsClear || Shape5->Brush->Style == bsClear)

&&(Shape1->Brush->Style == bsClear || Shape2->Brush->Style == bsClear

|| Shape3->Brush->Style == bsClear || Shape6->Brush->Style == bsClear))

||

(Shape6->Brush->Style == bsClear &&

(Shape1->Brush->Style == bsClear || Shape2->Brush->Style == bsClear

|| Shape3->Brush->Style == bsClear || Shape4->Brush->Style == bsClear

|| Shape5->Brush->Style == bsClear))) {

return 0;

}

else return 1;

}

Проверка основывается на подсчете перекрашенных и неперекрашенных камешков. Поэтому, как только конечный пользователь подберет какой-либо камешек, например, из 3-ей строки и захочет взять затем новый объект из какой-либо другой — программа сразу определит и пресечет это нарушение.

2. Так же в игре использовалась проверка правильности передачи хода. За эту функцию отвечает метод ЦАКП. indexator ().

// ;

bool CGame: indexator (TPanel *Gamer1, TPanel *Gamer2)

{

if (index == 0) {

MessageBox (NULL, «Вы должны взять хотя бы один шарик!»,

«Внимание!», MB_ICONWARNING);

index = 0;

return 0;

}

else {

index = 0;

if (gamer) {

gamer = false;

// -ход второго игрока

Gamer1->Color = clMoneyGreen;

Gamer2->Color = clSkyBlue;

}

else {

gamer = true;

// -ход первого игрока

Gamer1->Color = clSkyBlue;

Gamer2->Color = clMoneyGreen;

}

return 1;

}

}

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

3. Дополнительные проверки внедрялись и в функции. win (), фиксирующей победителя.

// ;

bool CGame: win (TPanel *Gamer1, TPanel *Gamer2)

{

if (list1 == true && list1 == true && list1 == true &&

list2 == true && list2 == true &&

list3 == true) {

Gamer1->Color = clSkyBlue;

Gamer2->Color = clSkyBlue;

if (gamer) {

MessageBox (NULL, «Игрок № 1 одерживает победу.»,

«Игра завершена.», MB_ICONINFORMATION);

}

else {

if (Gamer2->Caption == «Comp. 1.1»)

MessageBox (NULL, «Comp. 1.1 одерживает победу.»,

«Игра завершена.», MB_ICONINFORMATION);

else MessageBox (NULL, «Игрок № 2 одерживает победу.»,

«Игра завершена.», MB_ICONINFORMATION);

}

return true;

}

return false;

}

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

if (list1 == true && list1 == true && list1 == true &&

list2 == true && list2 == true &&

list3 == true) {

if (gamer) gamer = false;

else gamer = true;

}

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

5. Также, для того, чтобы исключить сбои программы, замеченные на предварительном тестировании, пришлось использовать специальные средства: метод-заглушку и активный деструктор ЦАКП.

// ;

void CGame: obj (TShape *Shape1, TShape *Shape2,

TShape *Shape3, TShape *Shape4,

TShape *Shape5, TShape *Shape6,

TButton *Button1, TRadioButton *RadioButton1,

TRadioButton *RadioButton2, TRadioButton *RadioButton3,

TRadioButton *RadioButton4)

{

if ((RadioButton1->Checked == false && RadioButton2->Checked == false)

||(RadioButton3->Checked == false && RadioButton4->Checked == false)) {

Button1->Enabled = false;

Shape1->Enabled = false;

Shape2->Enabled = false;

Shape3->Enabled = false;

Shape4->Enabled = false;

Shape5->Enabled = false;

Shape6->Enabled = false;

}

else {

Button1->Enabled = true;

Shape1->Enabled = true;

Shape2->Enabled = true;

Shape3->Enabled = true;

Shape4->Enabled = true;

Shape5->Enabled = true;

Shape6->Enabled = true;

}

}

Метод-заглушка обеспечивает неприкосновенность игровых манипуляторов управления во время игры и кнопки хода в момент настройки игры.

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