Математическая модель цифрового устройства игры 'Крестики-нолики' с человеком
Министерство
образования и науки Российской Федерации
Государственное
образовательное учреждение
высшего
профессионального образования
«Северо-Кавказский
государственный технический университет»
КАФЕДРА
ПРИКЛАДНОЙ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ
Курсовая
работа
по дисциплине
математическое
моделирование
на тему:
«Математическая модель цифрового устройства игры «Крестики - нолики с
человеком»
Выполнила:
студентка 3 курса
группы ПМ-081
Беджанова А. В.
Проверил:
Кравцов А.М.
Ставрополь,
2011 г.
Кафедра
Прикладной Математики и Компьютерных технологий
УТВЕРЖДАЮ:
Зав. Кафедрой ______________И.О.Ф.
(Подпись, дата)
ЗАДАНИЕ
на выполнение
курсовой работы
Студентки Беджановой А.В.
. Тема курсовой работы «Математическая модель цифрового устройства игры
«Крестики-нолики с человеком"
(утверждена приказом ректора (распоряжением декана) от ______№
. Срок сдачи студентом готовой работы 24 июня 2011 год
. Исходные данные к работе Математическая модель цифровой игры «Крестики
-нолики с человеком»
. Содержание текстового документа (перечень подлежащих разработке
вопросов) Содержание. Математическая модель. Компьютерная модель игры.
5. Дата выдачи задания на выполнение курсовой работы
апреля 2011 год
Руководитель _______________________________
(подпись, дата)
Задание принял к исполнению________________
(подпись, дата)
Содержание
ВВЕДЕНИЕ
1. Проектирование математической модели
1.1 Описание игры в крестики-нолики
1.2 Модель игры на основе булевой алгебры
2 ПРОЕКТИРОВАНИЕ ЦИФРОВОГО УСТРОЙСТВА
2.1 Игровой пульт
2.2 Игровой контроллер
2.3 Строка игрового поля
Вывод
Список используемой литературы
ВВЕДЕНИЕ
В современном мире нас окружают различные приборы, большинство из них
являются цифровыми устройствами: ЭВМ, телевизоры, счетные устройства, различные
контроллеры технологических процессов. Такие устройства могут совмещать
(совмещают) в себе принципы аналоговых и цифровых устройств[5]. Несомненным
фактом является преимущество цифровых устройств перед исключительно аналоговыми
устройствами[4].
В связи со сказанным, возникает необходимость разрабатывать цифровые
электронные устройства.
Цифровые электронные устройства берут свое начало с булевой алгебры
логики[4]. Вследствие чего возникает необходимость в разработке математической
модели устройства.
В данной курсовой работе рассматривается разработка математической модели
игры в крестики-нолики с человеком.
1. Проектирование математической модели
1.1 Описание игры в крестики-нолики
математический модель логический игра
Крестики-нолики - логическая игра между двумя противниками на квадратном
поле 3 на 3 клетки или большего размера (вплоть до «бесконечного поля»). Один
из игроков играет «крестиками», второй - «ноликами». В традиционной китайской
игре (Гомоку) используются черные и белые камни[1].
Правила игры довольно просты[1]. Игроки по очереди ставят на свободные
клетки поля 3х3 знаки (один всегда крестики, другой всегда нолики). Первый,
выстроивший в ряд 3 своих фигуры по вертикали, горизонтали или диагонали,
выигрывает. Первый ход делает игрок, ставящий крестики.
Обычно по завершении партии выигравшая сторона зачёркивает чертой свои
три знака (нолика или крестика), составляющих сплошной ряд.
Рисунок 1 - выигранная партия в крестики-нолики[2]
1.2 Модель
игры на основе булевой алгебры
Игровое
поле игры в крестики-нолики может быть представлено в виде сетки, состоящей из
строк и столбцов. Каждый элемент сетки может находиться в трех состояниях:
пустое (начальное), отмечено крестиком, отмечено ноликом. Для представления
трех состояний достаточно двух бит информации (число состояний ).
Рисунок 2 - схема модели цифрового устройства игры в «крестики-нолики»
На рисунке 2 изображено игровое поле (2) и игровые пульты игроков,
отмечающие крестики (1.1) и отмечающие нолики(1.2).
Переменные
игровых пультов принимают значения
правда/ложь (единица или ноль), причем правду (единицу) при нажатии на
соответствующую кнопку пульта. Без нажатия переменные тождественно равны нулю.
Пара
переменных игрового поля служит для
индикации состояния хода игры, а также для определения победителя или ничей.
Ячейка игрового поля может находится только в одном состоянии:
.
Функции,
сигнализирующие победителя или ничью:
-
победа игрока, отмечающего крестики.- победа игрока, отмечающего нолики.-
функция, тождественно равная правде, если все ячейки игрового поля окажутся
отмеченными.- функция, тождественно равная правде при ничьей.
Таблица
1 - таблица истинности функции W1
|
|
(111)(000)(000)
|
1
|
|
(000)(111)(000)
|
1
|
|
(000)(000)(111)
|
1
|
|
(100)(100)(100)
|
1
|
|
(010)(010)(010)
|
1
|
|
(001)(001)(001)
|
1
|
|
(100)(010)(001)
|
1
|
|
(001)(010)(100)
|
1
|
|
все остальные значения
|
0
|
Таблица 2 - таблица истинности функции W2
|
Значения  Значения функции W2
|
|
|
(111)(000)(000)
|
1
|
|
(000)(111)(000)
|
1
|
|
(000)(000)(111)
|
1
|
|
(100)(100)(100)
|
1
|
|
(010)(010)(010)
|
1
|
|
(001)(001)(001)
|
1
|
|
(100)(010)(001)
|
1
|
|
(001)(010)(100)
|
1
|
|
все остальные значения
|
0
|
Таблица 3 - таблица истинности функции FR
|
W1
|
W2
|
f
|
FR
|
|
0
|
0
|
0
|
0
|
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
0*
|
|
1
|
0
|
1
|
0
|
|
1
|
1
|
1
|
0*
|
|
0
|
1
|
1
|
0
|
|
0
|
0
|
1
|
|
0
|
1
|
0
|
0
|
0* - значения не встречаются, X/Y не могут быть установлены одновременно
2 ПРОЕКТИРОВАНИЕ ЦИФРОВОГО УСТРОЙСТВА
2.1 Игровой
пульт
Игровой пульт должен содержать кнопки, соответствующие состояниям
игрового поля, для того, что бы игрок мог отмечать крестики или нолики на поле.
Рисунок 3 - игровой пульт (1), устройство ввода (2 - клавиатура) и
последовательный порт вывода (ППВ)
На рисунке 3 - изображен общий вид пульта цифрового устройства игры в
крестики-нолики.
При нажатии на какую-нибудь кнопку на шине появляется число,
соответствующее номеру нажатой кнопки. Номер кнопки соответствует номеру ячейки
игрового поля (как показано на рисунке 2).
Последовательный порт вывода (ППВ) служит для преобразования
параллельного сигнала на шине в последовательный сигнал и последующей его
передачи с пульта на игровой контроллер.
2.2
Игровой контроллер
Игровой контроллер является цифровым устройством, выполняющим определения
победителя (или ничьей), а также отображения состояния игрового поля,
последовательного хода игроков.
Для
выполнения указанных функций контроллером, устройство должно содержать ячейки
памяти для хранения состояний поля и текущего хода игрока. Для этого
потребуется 
- 9 ячеек по 2 триггера и 1 триггер текущего хода.
Триггер - устройство с двумя устойчивыми состояниями[3] , необходимое для
хранения 
состояний игрового поля.
Общая
схема игрового контроллера изображена на рисунке 4.
Устройства,
обозначенные ДШ11 - ДШ23 - дешифраторы, служат для передачи сигнала на
соответствующий канал АС (по входящему номеру кнопки).
ППВ
- последовательный порт ввода, принимает сигнал с пульта.
ОП
- определяет победителя и зажигает соответствующий индикатор. Определение
победителя основано на функциях W1, W2, FR.
СБРОС
- сигнал, выполняющий инициализацию всех строк в начальное нулевое положение.
ПХ
- порядок хода игроков, состоит из триггера, «сбрасываемого» в начале игры,
инвертированный выход служит сигналом для хода «крестиком» прямой выход для
хода «ноликом».
Таблица
4 - таблица истинности ДШ11, реализующего входы 1, 2, 3
|
x1
|
x2
|
x3
|
x4
|
f1
|
f2
|
f3
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
|
1
|
1
|
0
|
0
|
0
|
0
|
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
Таблицы истинности дешифраторов ДШ12-ДШ23 строятся аналогично для своих
входов.
2.3
Строка игрового поля
Строка игрового поля (активна строка АС) служит для хранения состояния
строки игрового поля. Состояние хранится в устройстве ТВТ (три-би-триггер).
Строка содержит защиту от преждевременного хода игрока и от хода в отмеченную
ячейку (РС).
Рисунок 5 - схема «активной строки» (АС)
Рисунок 6 - схема ТВТ (три-би-триггера)
ТВТ
служит для хранения состояний трех ячеек в строке, содержит три входа для
каждого игрока 
, а также вход «сброса».
ТВТ
состоит из элементов ВТ (би-триггеров).
Рисунок 7 - схема ВТ (би-триггера)
ВТ
(Би-триггер) состоит из двух RS-триггеров, имет два входа и два выхода
(соответствует состояниям ), а также вход
«сброса».
Рисунок 8 - схема разрешения строки (РС)
РС «разрешает» установить состояние, если в данный момент ходит
«правильный» игрок и если ячейка в начальном состоянии.
Вывод
В ходе выполнения курсовой работы была построена математическая модель
игры в крестики-нолики с человеком. Данная математическая модель представляет
собой формулы булевой алгебры логики, записанных в виде дизъюнкций элементарных
конъюнкций и конъюнкций элементарных дизъюнкций. Математическая модель может
быть обобщена для игровых полей большего размера.
Также, на основе построенной математической модели было спроектировано
цифровое устройство для игры в крестики-нолики с человеком.
Список используемой литературы
1. Гарднер
М. Крестики-нолики. -М.: Мир, 1988.
2. <http://ru.wikipedia.org/wiki/%CA%F0%E5%F1%F2%E8%EA%E8-%ED%EE%EB%E8%EA%E8>
3. W. H.
Eccles, F. W. Jordan A trigger relay utilizing three-electrode thermionic
vacuum tubes. The Electrician, Vol. 83,
P. 298 (19 September 1919)
. Д.Гивоне
Микропроцессоры и микрокомпьютеры, Мир 1980г.
. <http://ru.wikipedia.org/wiki/Intel_8080>