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

Министерство образования и науки Российской Федерации Государственное образовательное учреждение

высшего профессионального образования

«Северо-Кавказский государственный технический университет»

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

Курсовая работа

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

Выполнила:

студентка 3 курса группы ПМ-081

Асланова А. М.

Проверил:

Кравцов А.М.

Ставрополь, 2011 г.

Кафедра Прикладной Математики и Компьютерных технологий

УТВЕРЖДАЮ:

Зав. Кафедрой ______________Ф.И.О.

(Подпись, дата) ЗАДАНИЕ на выполнение курсовой работы Студентки Аслановой А.М.

1. Тема курсовой работы

«Математическая модель цифрового устройства для игры «Шашки»

(утверждена приказом ректора (распоряжением декана) от ______№

2. Срок сдачи студентом готовой работы 24 июня 2011 год

3. Исходные данные к работе Математическая модель игры «Шашки»

4. Содержание текстового документа (перечень подлежащих разработке вопросов) Содержание. Математическая модель. Компьютерная модель игры.

5. Дата выдачи задания на выполнение курсовой работы 28 апреля 2011 год

Руководитель _______________________________

(подпись, дата) Задание принял к исполнению________________

(подпись, дата)

1.Определение Булевых функций

1.1 Унарные функции

1.2 Бинарные функции

2. Представление булевых функций

2.1 Дизъюнктивная нормальная форма (ДНФ)

2.2 Конъюнктивная нормальная форма (КНФ)

3. Правила и стратегия игры в шашки

4. Математическая модель цифрового устройства для игры в шашки Заключение Список литературы Приложение

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

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

Развитие ЭВМ стимулировало более интенсивное развитие вычислительных методов, создало предпосылки решения сложных задач науки, техники, экономики. Широкое применение при решении таких задач получили методы прикладной математики и математического моделирования.

Определение Булевых функций

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

Бумлева фумнкция (или логимческая функция, или функция амлгебры ломгики) от n переменных — в дискретной математике отображение > B, где B = {0,1} — булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения Bn называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается, а от n переменных — (n).

Унарные функции

При n = 1 число булевых функций равно 221 = 22 = 4. Определение этих функций содержится в следующей таблице.

Таблица значений булевых функций от одной переменной:

Бинарные функции

При n = 2 число булевых функций равно 22І = 24 = 16.

Таблица значений булевых функций от двух переменных:

Дизъюнктивная нормальная форма (ДНФ)

Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция:

· правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);

· полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;

· монотонная, если она не содержит отрицаний переменных.

Например — является ДНФ.

Теорема (о СДНФ)

Всякая тождественно не равная 0 функция f (, ,…,) допускает представление f (, ,…,) = ?f (,…,))x…x (1) ,

где дизъюнкция берется по всем наборам C=(,…,) из 0 и 1, для которых f© = 1

Доказательство: Пусть функция f (, ,…,)?0. По лемме о разложении функции по компонентам при k=n получаем:

f (, ,…,) = ?f (,…,))x…x правой части этого равенства выбросим все нулевые дизъюнктивные слагаемые, для которых f (,…,) =0, останутся слагаемые, в которых f (,…,)=1. Равенство принимает вид:

f(, ,…,) = ?f()= 1x…x

Определение: Правая часть представления (1) называется СДНФ функции f.

Замечание: Каждое слагаемое в СДНФ называется конституентой единицы. Конституента единицы x…x=1 на единственном наборе , =,, , =,, , =.

Замечание: Всякая функция допускает представление в виде СДНФ, которая построена из функций множества F={&, ?, } (2). Следовательно, множество F составляет полную систему. Система F3={x/y}, состоящая из единственной функции (штрих Шеффера), составляет полную систему

Замечание: Для всякой не равной тождественно нулю функции существует единственная СДНФ.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию, где. Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является, что можно упростить до .

Конъюнктивная нормальная форма (КНФ)

Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

Теорема (о СКНФ):

Всякая не равная тождественно 1 функция f (, ,…,) допускает представление

f(, ,…,) = & f(, ,…,) x?…?x) (3),

где конъюнкция берется по всем наборам C = (, ,…,) из 0 и 1, для которых f (C) = 0.

Доказательство: заметим, что (xc) = xc. Пусть функция f(, ,…,) ?1. Тогда f?0 и потому функция f допускает представление в виде СДНФ.

f(, ,…,) =?f(C)=1 x…x

Берем отрицание от обеих частей.

f (, ,…,) = ?f (C)=0(x…x) = &f (C)=0(x…x) = &f (C)=0(x…x) = &f (C)=0(x…x)

Определение: Правая часть представления (3) называется СКНФ для функции f.

Замечание: для всякой функции f?1 СКНФ единственна.

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

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

Правила и стратегия игры в шашки

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

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

Игра может вестись не на всей доске, а на ее части. Для полей 4Ч4, 6Ч6 и 8Ч8 возможно соответственно построение 20, 105 и 336 квадратов разного размера и расположения. Несмотря на большое количество возможных вариантов построения квадратов и, соответственно, трудность предусмотреть и предвидеть возможные тактические ходы, существует беспроигрышная стратегия при игре на полях 6Ч6 и 8Ч8 для черных.

Начинающий вторым игрок дублирует ходы белых относительно одной из двух осей симметрии игрового поля либо относительно центра доски. Асимметричная стратегия: на ход x1 следует ход y7 или y8. Раз выбранная ось симметрии выдерживается всю игру. Центросимметричная стратегия: на ход x1 следует ход y8 и т. д. Игра при такой стратегии становится монотонной и неинтересной, и применять ее следует разве что при необходимости обязательного выигрыша. На полях 5Ч5 и 7Ч7 эта стратегия не применима ввиду отсутствия графических осей и центра симметрии.

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

Математическая модель цифрового устройства для игры в шашки

Разработаем математическую модель для игры в шашки, будем использовать для этого игровое поле 4*4. Обозначим наши переменные следующим образом:

Пусть — переменная для белых шашек, где x = 1,2,3,4,5,6,7,8.

Тогда — переменная для черных шашек, где у = 1,2,3,4,5,6,7,8.

Из этого следует что:

= 0 — если клетка игрового поля пуста,

= 1- если на клетке стоит белая шашка,

= 0 — если клетка игрового поля пуста,

= 1- если на клетке стоит черная шашка.

Ниже представлен рисунок нашей игровой доски.

Посмотрев на рисунок можно отметить что х1=1 и х2=1 так как только на них расположены белые шашки, остальные значения х=0, тоже можно и заметить и с у7 и у8 которые соответственно тоже равны единице, а все остальные нулю.

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

Таблица№ 1 Выигрыш черных шашек.

математический модель игра булевая функция Таблица№ 2 Исход игры: ничья.

Таблица№ 3 Выигрыш белых шашек.

Заключение

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

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

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

1. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 2009.

2. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 2002. — 344 с.

3. Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.

4. Яблонский С. В.

Введение

в дискретную математику. — М.: Наука, 2006.

5. Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А.Д. Поспелов

6. Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006

7. http://psi-logic.narod.ru/bool/bool.htm 2011.

8. Учебные пособия кафедры математической кибернетики ВМиК МГУ.

Приложение

Программа для игры «шашки» на языке С++ Builder

=====НАЧИНАЕМ ХОД======

{

POINT Point;

if (WhoseTurn == Black) // =====ПРОВЕРЯЕМ, ДЕЙСТВИТЕЛЬНО ЛИ ХОДИТ ЧЕЛОВЕК=====

return;

SetCapture (HWindow);

GetCursorPos (&Point);

ScreenToClient (HWindow, &Point);

MoveStartPoint = bd->GetValidSquare (Point, WhoseTurn);

if (MoveStartPoint. x)

{

MovingPieceType = bd->GetPieceType (MoveStartPoint);

HDC hDC = GetDC (HWindow);

bd->ClearSquare (hDC, MoveStartPoint);

HoldingPiece = TRUE;

ReleaseDC (HWindow, hDC);

}

}

Функция WMLButtonUp ():

void TCheckersWindow: WMLButtonUp (TMessage&)

{

POINT Point;

ReleaseCapture ();

if (! HoldingPiece || WhoseTurn == Black)

return;

GetCursorPos (&Point);

ScreenToClient (HWindow, &Point);

MoveEndPoint = bd->GetEmptySquare (Point);

HDC hDC = GetDC (HWindow);

if (MoveEndPoint. x && bd->UserMove (MoveStartPoint, MoveEndPoint))

{ // ====ЕСЛИ ЧЕЛОВЕК МОЖЕТ СЮДА ПОСТАВИТЬ ФИШКУ… =====

bd->RedrawBoard (hDC); // =========ТО ПЕРЕРИСОВЫВАЕМ ДОСКУ=======

EnableMenuItem (hMenu, CM_UNDO, MF_BYCOMMAND | MF_ENABLED);

EnableMenuItem (hMenu, CM_REDO, MF_BYCOMMAND | MF_DISABLED | MF_GRAYED);

if (! bd->AnotherJump ()) // =====МОЖНО СДЕЛАТЬ ПОВТОРНЫЙ ХОД? ========

{

if (bd->NoMoreBlack ()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК КОМПЬЮТЕРА… . ===

{

if (GetApplication () — >ExecDialog (new TEndDialog (this, «UserWonDlg»)) // ТО ЧЕЛОВЕК ВЫИГРАЛ!

== IDYES)

{

PostMessage (HWindow, WM_COMMAND, CM_FILENEW, 0L);

ReleaseDC (HWindow, hDC);

return;

}

else

{

PostMessage (HWindow, WM_COMMAND, CM_EXIT, 0L);

ReleaseDC (HWindow, hDC);

return;

}

}

PostMessage (HWindow, WM_COMMAND, CM_MOVE, 0L); // ==ПЕРЕКЛЮЧАЕМСЯ НА ХОД===

} // =======КОМПЬЮТЕРА=======

else // НЕЯВНЫЙ ВЫЗОВ ФУНКЦИИ

; // ComputersMove ()

}

else

{

bd->DrawPiece (hDC, MovingPieceType, MoveStartPoint);

}

HoldingPiece = FALSE;

ReleaseDC (HWindow, hDC);

}

Функция ComputersMove ():

void TCheckersWindow: ComputersMove (RTMessage)

{

bd->EndUsersTime ();

WhoseTurn = Black;

EnableMenuItem (hMenu, 0, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);

EnableMenuItem (hMenu, 1, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);

EnableMenuItem (hMenu, 3, MF_BYPOSITION | MF_DISABLED | MF_GRAYED);

ModifyMenu (hMenu, CM_MOVE, MF_BYCOMMAND | MF_ENABLED |

MF_STRING, CM_STOP, «&Stop»);

DrawMenuBar (HWindow);

bd->ComputersTurn (); // =======ПЕРЕКЛЮЧАЕМСЯ НА РАБОТУ ИИ========

HDC hDC = GetDC (HWindow);

bd->RedrawBoard (hDC);

ReleaseDC (HWindow, hDC);

WhoseTurn = Red;

POINT CursorPoint;

GetCursorPos (&CursorPoint);

ScreenToClient (HWindow, &CursorPoint);

#pragma warn — stv

if (PtInRect (&MainWndRect, CursorPoint))

/*SetCursor (CursorHand) */;

#pragma warn +stv

ModifyMenu (hMenu, CM_STOP, MF_BYCOMMAND | MF_ENABLED |

MF_STRING, CM_MOVE, «move you»);

EnableMenuItem (hMenu, 0, MF_BYPOSITION | MF_ENABLED);

EnableMenuItem (hMenu, 1, MF_BYPOSITION | MF_ENABLED);

EnableMenuItem (hMenu, 3, MF_BYPOSITION | MF_ENABLED);

DrawMenuBar (HWindow);

if (bd->NoMoreRed ()) // ====ЕСЛИ БОЛЬШЕ НЕОСТАЛОСЬ ФИШЕК ЧЕЛОВЕКА…. ===

{

if (GetApplication () — >ExecDialog (new TEndDialog (this, «GameWonDlg»)) // ===ТО КОМПЬЮТЕР===

== IDYES) // ======ВЫИГРАЛ======

{

PostMessage (HWindow, WM_COMMAND, CM_FILENEW, 0L);

return;

}

else

{

PostMessage (HWindow, WM_COMMAND, CM_EXIT, 0L);

return;

}

}

bd->StartUsersTime (); // ======ХОД ЧЕЛОВЕКА========

}

Размещено на