Интеллектуальная игра «Крестики-нолики

Министерство образования  и науки Российской Федерации 
Филиал федерального государственного автономного образовательного учреждения высшего профессионального образования 
"Казанский (Приволжский) федеральный университет" 

 

 

 

 

 

 

 

 

 

Отчет по лабораторным работам

по дисциплине:

«Система искусственного интеллекта»

на тему: интеллектуальная игра «Крестики-нолики»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                  Выполнил:                                                  

 

                                                  Проверил:

                                                 

 

 

 

 

г.

 2013 г.

 

Содержание

 

 

 

Введение

 

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

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

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

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

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

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

 

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

 

Задачей контрольной, как  говорилось ранее, является составление  программы, которая будет играть крестики нолики с пользователем. Крестики нолики – логическая игра между двумя противниками на квадратном поле 3 на 3 клетки или бо́льшего размера (вплоть до «бесконечного поля»). Один из игроков играет «крестиками», второй — «ноликами».

В нашем случае игра будет  между первым противником-пользователем  и вторым противником – искусственным интеллектом (ИИ). Игра будет проходит на поле 3 на 3 клетки, чтобы было легче отследить, то как программа запоминает и реагирует на ту или иную ситуацию. Пусть противник-«компьютер» будет ходит ноликами, а мы, то есть пользователи, крестиками.

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

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

 

2 Интерфейс пользователя

 

Запуск игры будет  осуществляться через браузер. После того как запустили игру в браузер, выводится следующее окно (рисунок 1), в котором предлагается очистить базу и ссылка для начала игры. Очистка базы возможна на любом этапе работы программы.

 

Рисунок 1 – Главная  страница игры

 

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

Рисунок 2 – Окно нашего выигрыша

 

Попытаемся проделать  данную схему выигрыша повторно, и получаем ответ от «робота» в виде препятствия ноликом в нашем направлении. Что мы видим на рисунке 3.

 

Рисунок 3 – Выбор компьютером хода,

препятствующий нашему выигрышу

 

В итоге проиграв этим способом получаем ничью:

Рисунок 4 – Окно ничьи

 

Повторим схему еще  раз и получаем проигрыш:

Рисунок 5 – Окно нашего проигрыша

 

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

 

Рисунок 5 – Очистка  базы знаний с предложением пройти назад

 

 

3 Алгоритм работы программы

 

Главное окно программы  состоит из двух ссылок, как мы рассматривали  ранее на рисунке 1. Первая для очистки  базы, вторая для начала игры. Рассмотрим подробнее очистку базы знаний.

Запуск очистки базы знаний осуществляется файлом clear.php. В ней происходит удаление старой таблицы базы данных и создание новой таблицы с пустыми ячейками в полях:

<? require_once("connect.php");

//соединение  к базе данных настройки в файле connect.php

$link=mysql_connect($sqlhost, $sqluser, $sqlpass) or die("MySQL ioeaea!".mysql_error());   

$sql="DROP TABLE `xo`"; //удаление таблицы

$datu=mysql_query($sql);

$sql="CREATE TABLE IF NOT EXISTS `xo` (    //создание таблицы

  `id` tinyint(4) NOT NULL auto_increment,       //создание полей таблицы

  `a1` tinyint(4) NOT NULL,

  `a2` tinyint(4) NOT NULL,

  `a3` tinyint(4) NOT NULL,

  `a4` tinyint(4) NOT NULL,

  `a5` tinyint(4) NOT NULL,

  `a6` tinyint(4) NOT NULL,

  `a7` tinyint(4) NOT NULL,

  `a8` tinyint(4) NOT NULL,

  `a9` tinyint(4) NOT NULL,

  `v` tinyint(4) NOT NULL,

  PRIMARY KEY  (`id`)

) ENGINE=MyISAM  DEFAULT CHARSET=cp1251 AUTO_INCREMENT=0;";

  $daty=mysql_query($sql); ?>

Кроме этого php-скрипта имеется html-тег для перехода на главную страницу: <a href=xo.php>Назад</a>

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

Если не началась игра то ссылка имеет  следующий вид http://bimet-shop.ru/xo.php Если игра идет то она имеет в зависимости ходов следующий вид, которые записываются в эту ссылку:

bimet-shop.ru/xo.php?a1=2&a2=0&a3=0&a4=0&a5=0&a6=0&a7=0&a8=0&a9=0&v=0

Условие отображение  только слова «Start» в главном окне, определяется скриптом, то есть если нет значений a1, a2 … a9 и v, то видим только «главные ссылки»:

if (isset($_GET['a1'])==false and isset($_GET['a2'])==false and isset($_GET['a3'])==false and isset($_GET['a4'])==false and isset($_GET['a5'])==false and isset($_GET['a6'])==false and isset($_GET['a7'])==false and isset($_GET['a8'])==false and isset($_GET['a9'])==false)

{ echo "<a href=xo.php?a1=0&a2=0&a3=0&a4=0&a5=0&a6=0&a7=0&a8=0&a9=0&v=0>Start</a>";}

 

Если это условие  не выполняется, идет выполнение проверки на статуса игры: выигрыш, проигрыш, ничья. Если статус игры не соответствует представленным вариантам, то идет процесс игры.

Статус игры видим в следующих  кодах:

//если проигрыш

if (($_GET['a1']==$_GET['a2'] and $_GET['a2']==$_GET['a3'] and $_GET['a2']==1) or ($_GET['a4']==$_GET['a5'] and $_GET['a4']==$_GET['a6'] and $_GET['a4']==1) or ($_GET['a7']==$_GET['a8'] and $_GET['a7']==$_GET['a9'] and $_GET['a7']==1) or ($_GET['a1']==$_GET['a4'] and $_GET['a1']==$_GET['a7'] and $_GET['a1']==1) or ($_GET['a2']==$_GET['a5'] and $_GET['a2']==$_GET['a8'] and $_GET['a2']==1) or ($_GET['a3']==$_GET['a6'] and $_GET['a3']==$_GET['a9'] and $_GET['a3']==1) or ($_GET['a1']==$_GET['a5'] and $_GET['a1']==$_GET['a9'] and $_GET['a1']==1) or ($_GET['a3']==$_GET['a5'] and $_GET['a3']==$_GET['a7'] and $_GET['a3']==1)) {

echo "<a href=xo.php?a1=0&a2=0&a3=0&a4=0&a5=0&a6=0&a7=0&a8=0&a9=0&v=0>Game over</a>";

}

else {

//если выигрыш

if (($_GET['a1']==$_GET['a2'] and $_GET['a2']==$_GET['a3'] and $_GET['a2']==2) or ($_GET['a4']==$_GET['a5'] and $_GET['a4']==$_GET['a6'] and $_GET['a4']==2) or ($_GET['a7']==$_GET['a8'] and $_GET['a7']==$_GET['a9'] and $_GET['a7']==2) or ($_GET['a1']==$_GET['a4'] and $_GET['a1']==$_GET['a7'] and $_GET['a1']==2) or ($_GET['a2']==$_GET['a5'] and $_GET['a2']==$_GET['a8'] and $_GET['a2']==2) or ($_GET['a3']==$_GET['a6'] and $_GET['a3']==$_GET['a9'] and $_GET['a3']==2) or ($_GET['a1']==$_GET['a5'] and $_GET['a1']==$_GET['a9'] and $_GET['a1']==2) or ($_GET['a3']==$_GET['a5'] and $_GET['a3']==$_GET['a7'] and $_GET['a3']==2))

{echo "<a href=xo.php?a1=0&a2=0&a3=0&a4=0&a5=0&a6=0&a7=0&a8=0&a9=0&v=0>You win</a>";

require_once("connect.php");

$sSQL="INSERT INTO xo (id,a1,a2,a3,a4,a5,a6,a7,a8,a9,v)

VALUES ('','".$_GET['a1']."','".$_GET['a2']."','".$_GET['a3']."','".$_GET['a4']."','".$_GET['a5']."','".$_GET['a6']."','".$_GET['a7']."','".$_GET['a8']."','".$_GET['a9']."','".$kol."');"; //выигрыш записывается в базу знании для того чтоб программа не давала нам выиграть в следующий раз

mysql_query($sSQL) or die(mysql_error());}

else {

//если ничья

if ($_GET['a1']<>0 and $_GET['a2']<>0 and $_GET['a3']<>0 and $_GET['a4']<>0 and $_GET['a5']<>0 and $_GET['a6']<>0 and $_GET['a7']<>0 and $_GET['a8']<>0 and $_GET['a9']<>0)

{echo "<a href=xo.php?a1=0&a2=0&a3=0&a4=0&a5=0&a6=0&a7=0&a8=0&a9=0&v=0>new game</a>";

}}}

 

Скрипт, в котором программа  делает ходы, выполняется поверка количеств ходов своих и проивника, чтобы ходы были выполнены по очереди и чтоб компьютер не ходил несколько раз:

$kol1=0;

$kol2=0;

$kol=0;

for ($i=1; $i<=9; $i++) {

if ($_GET['a'.$i]==1) {$kol1=$kol1+1;} //подсчет ходов робота

if ($_GET['a'.$i]==2) {$kol2=$kol2+1;}} //подсчет наших ходов

$kol=$kol2+$kol1;

 

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

if ($kol1+1==$kol2) { //условие где наши ходы на один ход превышают ход компьютера

require_once("connect.php");

  $link=mysql_connect($sqlhost, $sqluser, $sqlpass) or die("MySQL ошибка mysql_error());

$sql="SELECT id,a1,a2,a3,a4,a5,a6,a7,a8,a9,v FROM xo order by v";

  $data=mysql_query($sql);

  while ($line=mysql_fetch_row($data)) {

//проверка  условия на повтор выигрышных  для пользователя ходов

  if (isset($_GET['a9']) and isset($_GET['a1']) and (($_GET['a1']==$line[1]) or ($_GET['a1']==0)) and isset($_GET['a2']) and (($_GET['a2']==$line[2]) or ($_GET['a2']==0)) and isset($_GET['a3']) and (($_GET['a3']==$line[3]) or ($_GET['a3']==0)) and isset($_GET['a4']) and (($_GET['a4']==$line[4]) or ($_GET['a4']==0)) and isset($_GET['a5']) and (($_GET['a5']==$line[5]) or ($_GET['a5']==0)) and isset($_GET['a6']) and (($_GET['a6']==$line[6]) or ($_GET['a6']==0)) and isset($_GET['a7']) and (($_GET['a7']==$line[7]) or ($_GET['a7']==0)) and isset($_GET['a8']) and (($_GET['a8']==$line[8]) or ($_GET['a8']==0)) and (($_GET['a9']==$line[9]) or ($_GET['a9']==0))) 

  {$li=0;

//рисование  «0» там где в таблице записан «Х» а на игре еще этот крестик не поставлен

  if ($line[1]==2 and 0==$_GET['a1']) {$_GET['a1']=1; break;} else {

  if (($line[2]==2) and (0==$_GET['a2'])) {$_GET['a2']=1;break;} else {

  if ($line[3]==2 and 0==$_GET['a3']) {$_GET['a3']=1;break;} else {

  if ($line[4]==2 and 0==$_GET['a4']) {$_GET['a4']=1;break;} else {

  if ($line[5]==2 and 0==$_GET['a5']) {$_GET['a5']=1;break;} else {

  if ($line[6]==2 and 0==$_GET['a6']) {$_GET['a6']=1;break;} else {

  if ($line[7]==2 and 0==$_GET['a7']) {$_GET['a7']=1;break;} else {

  if ($line[8]==2 and 0==$_GET['a8']) {$_GET['a8']=1;break;} else {

  if ($line[9]==2 and 0==$_GET['a9']) {$_GET['a9']=1;break;}

  }}}}}}}}} else {

   $li=1;} } //если в таблице нет такой комбинации, то li=1

 

Если в таблице такой комбинации нет в таблицы базы, то рисует нолик в любое свободное место:

if (((isset($li) and $li==1) or (isset($li)==false)) and ((0==$_GET['a1']) or (0==$_GET['a2']) or (0==$_GET['a3']) or (0==$_GET['a4']) or (0==$_GET['a5']) or (0==$_GET['a6']) or (0==$_GET['a7']) or (0==$_GET['a8']) or (0==$_GET['a9']))) {

$m=0;

     while ($m==0) {

$lil=mt_rand(1,9);

  if (0==$_GET['a1'] and $lil==1) {$_GET['a1']=1; $m=1;} else {

  if (0==$_GET['a2'] and $lil==2) {$_GET['a2']=1; $m=1;} else {

  if (0==$_GET['a3'] and $lil==3) {$_GET['a3']=1; $m=1;} else {

  if (0==$_GET['a4'] and $lil==4) {$_GET['a4']=1; $m=1;} else {

  if (0==$_GET['a5'] and $lil==5) {$_GET['a5']=1; $m=1;} else {

  if (0==$_GET['a6'] and $lil==6) {$_GET['a6']=1; $m=1;} else {

  if (0==$_GET['a7'] and $lil==7) {$_GET['a7']=1; $m=1;} else {

  if (0==$_GET['a8'] and $lil==8) {$_GET['a8']=1; $m=1;} else {

  if (0==$_GET['a9'] and $lil==9) {$_GET['a9']=1; $m=1;}

  }}}}}}}}}}}

 

Отображение крестиков  и ноликов зависит от ссылки:

xo.php?a1=2&a2=1&a3=0&a4=0&a5=2&a6=0&a7=0&a8=0&a9=0&v=0

то есть по данной ссылке можно сказать, что у нас крестик  стоит в ячейках 1 и 5-ая, нолик  во второй ячейке. Двойки означают наш  ход, единицы – ход компьютера.

 

 

 

Нумерация ячеек представлена ниже:

a1=2	a2=1	a3
a4	a5=2	a6
a7	a8	a9

 

В каждую чеку пишется  скрип на проверку: делался ли в данную ячейку ход, и происходит переписывание значений всей ссылки. Также тут происходит выбор отображения значения в зависимости от того, какова запись например код приведен для ячейки а1=2, то тут пишется «Х»:

if (isset($_GET['a1']) and ($_GET['a1']<>0)) {echo $_GET['a1'];} else {echo "2";} //делается ход нами если не было хода в данную ячейку

//перезапись  всех ходов:

echo "&a2=";

if (isset($_GET['a2'])) {echo $_GET['a2'];} else {echo "0";}

echo "&a3=";

if (isset($_GET['a3'])) {echo $_GET['a3'];} else {echo "0";}

echo "&a4=";

if (isset($_GET['a4'])) {echo $_GET['a4'];} else {echo "0";}