Морской бой

     Даже  Рассел сделал некоторые изменения. Зная, что у настоящих торпед вероятность поражения цели не 100%, а меньше, он решил придать звездным торпедам возможность ошибки, и добавить случайный элемент в траектории ракет и время взрыва. Его друзья терпеть не могли новую версию, поскольку они хотели бы иметь в игре ту же степень уверенности, которая существовала в программировании. Рассел вернул программу к прежней версии и, не успели оглянуться, как «Космические войны» оккупировали компьютеры колледжей по всей стране. «Космические войны» стали настолько популярны к середине шестидесятых, что Нолан Бушнелл, создатель Atari, очень привязался к игре во время учебы в университете штата Юты. К 1970 году Бушнелл построил свою собственную машину, использовав 185 встроенных цепей для подсоединения к телевизору и для выполнения одной-единственной функции. Эта функция была игрой «Компьютерный Космос», вариант «Космических Войн», в котором ракета сражалась с летающими тарелками вместо другого корабля. «Космические Войны» были не единственным предшественником коммерческих компьютерных игр, появившихся на больших компьютерах в колледжах. Какой-то неизвестный автор начал играть в игру Star Trek («Звездный путь») в шестидесятых годах. Никто не знает, кто первым создал такую игру — он или она, вероятно, подали бы судебный иск, если бы автор игры был точно определен — но эта игра также появилась на колледжских компьютерах по всей стране к 1969 году. Игра «Звездный путь» сама по себе была не очень изощренной. В игре были линии наподобие решеток, которые позволяли звездным кораблям путешествовать от одной точки к другой, игра использовала символы для идентификации кораблей, предоставляла численную информацию в процентах, и позволяла летать быстрее, чем скорость света. К середине 70-х годов почти на каждой домашней компьютерной системе была доступна та или иная форма этой игры. Существовала версия этой же игры для IBM под названием Star Fleet («Звездный Флот»). Наконец, стоит упомянуть пожалуй наиболее важную игру, Adventure («Приключения»). В игре использовались двухсловные команды, имя ее разработчика Вилл Краудер. Это была первая приключенческая компьютерная игра. Кроме того, в конце 70-х была создана игра по имени Zork, которая стала доступна для пользователей домашних компьютеров в 1981 году. Эту игру до сих пор можно купить. Игра Zork основывается на игре Adventure.

     1.2 Описание операторов, используемых при реализации практической части курсовой работы

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

     Структурные операторы

     Оператор  if…then…

     Оператор  if…then… называется условным оператором и имеет вид:

       If expression1 then statement1; 

     где выражение expression1 является логическим. Логическое выражение принимает одно из двух возможных значений – True (истина) или False (ложь). Часто в роли логического выражения выступает какое-то условие, которое может выполнять либо нет. В первом случае его значение – «истина»,а во втором – «ложь». Если логическое выражение expression1 принимает значение «истина», то выполняется оператор statement1. В противном случае выполняется будет оператор, следующий за данным логическим оператором. 

     Оператор  if…then…else… 

     Этот  оператор является полной версией условного  оператора и имеет вид:

     If expression then statement1 else statement2; 

     Выполняется данный оператор следующим образом: если выражение expression принимает значение «истина», то управление передается на оператор statement1, если же нет, то на оператор statement2. 

     Оператор  case…of…end 

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

     case expression of 

       values_1: statement_1;

      values_2: statement_2;

       …

      values_n: statement_n;

      else statement;

     end; 

     Рассмотрим  элементы этой конструкции. Во-первых, это три зарезервированных слова: case, of и end. Между case и of находится выражение expression, принимающее значение, которое, возможно, имеется в одном из списков значений, находящихся слева от двоеточий. Данное выражение называется селектором оператора case. Каждый оператор, идущий за двоеточием, отделяется от следующего списка значений точкой запятой. Ветвь else, отвечающая всем не перечисленным значениям выражения expression, необязательна. При выполнении данного оператора вначале вычисляется значение селектора. Затем выбирается тот список значений, которому принадлежит полученное значение, и выполняется соответствующий оператор. 

     Оператор  цикла while…do… 

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

     While expression do statement ; 

     При выполнении этого оператора вначале  вычисляется значение логического  выражения expression. Если это значение истинно, выполняется оператор statement, затем значение выражения проверяется вновь и т. д., до тех пор, пока выражение не примет значений «ложь». Если выражение принимает значение «ложь» при первой же проверке, то оператор statement не выполняется вообще. 

     Операторы цикла repeat…until… 

     Оператор  цикла с постусловием имеет вид:

     Repeat statement until expression: 

     Здесь вначале выполняется оператор statement, а затем вычисляется значение логического выражения expression принимает значение «ложь». Как только это значение станет истинным, выполнение цикла прекращается. 

     Операторы цикла for…to…do… и for…downto…do… 

     Третий  вариант оператора цикла –  цикл со счетчиком. Можно считать, что  есть две очень похожих друг на друга разновидности цикла со счетчиком. Первый из этих операторов имеет вид: 

     For j := expression1 to expression2 do statement; 

     Здесь переменная j, называемая управляющей переменной цикла for, является произвольным идентификатором, который объявляется как переменная любого скалярного типа (к скалярным относится целый, символьный, булев и перечислимые типы).

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

 

      2. РАЗРАБОТКА ПРОГРАММЫ

     2.1 Постановка задачи

 

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

     2.2 Алгоритм реализации  работы

 

     Алгоритм  размещения кораблей на игровом поле

     Игровое поле нужно как-то хранить в памяти компьютера. Наиболее простая реализация - в виде матрицы 10x10 клеток (ячеек). Определим  соответствующий тип и переменные, которые нам понадобятся:  

type TPole = array[1..10,1..10] of Integer; var Pole: TPole;

 

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

procedure Init (var Pole: TPole); var X, Y: Integer; begin  Randomize;  for X := 1 to 10 do  for Y := 1 to 10 do  Pole[X,Y] := -1; end; {proc Init}

 

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

function Freedom (x, y: Integer; Pole: TPole): Boolean; const d: array[1..8,1..2] of Integer =  ((0,1),(1,0),(0,-1),(-1,0),(1,1),(-1,1),(1,-1),(-1,-1)); var i: Integer;  dx, dy: Integer; begin  if (x > 0) and (x < 11) and (y > 0) and (y < 11) and (Pole[x,y] = -1) then  begin  for i := 1 to 8 do  begin  dx := x + d[i,1];  dy := y + d[i,2];  if (dx > 0) and (dx < 11) and (dy > 0) and (dy < 11) and (Pole[dx,dy] > -1) then  begin  Result := False;  Exit;  end; {if}  end; {for}  Result := True;  end else Result := False; end; {func Freedom}

 

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

procedure Ships (var Pole: TPole); var N, M, i: Integer;  x, y, kx, ky: Integer;  B: Boolean; begin  Init (Pole);  for N := 3 downto 0 do  for M := 0 to 3 - N do  repeat  x := Random (10) + 1;  y := Random (10) + 1;  kx := Random (2);  if kx = 0 then ky := 1  else ky := 0;  B := True;  for i := 0 to N do  if not Freedom (x + kx * i, y + ky * i, Pole) then B := False;  if B then  for i := 0 to N do  Pole[x+kx*i,y+ky*i] := 0;  until B; end; {proc Ships}

 

     Это, собственно, и все, что касается размещения кораблей компьютера. Теперь достаточно сделать вызов: Ship (Pole); и корабли будут случайным образом расставлены по своим местам. Подобным образом можно помочь пользователю, что бы он каждый раз не тратил время на эту операцию, вызвав Ship (Play); где Play - поле игрока (тип TPole).

     Стратегия игры компьютера

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

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

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