• 2. Математичні та алгоритмічні основи рішення задачі
  • 3. Функціональна модель вирішення задачі
  • 4. Програмна реалізація рішення задачі
  • (Setq field (read
  • (Setq
  • (Return t)
  • *)) (setf (nth l (nth
  • (Defun set_missing
  • (If (and (/ = (
  • (eql (nth j (nth
  • (Setq n (nth j (nth
  • ((Or (equal n *) (equal
  • 5. Приклад виконання програми
  • Список використаних джерел та літератури
  • Гра в "Морський бій" з комп'ютером




    Скачати 27.98 Kb.
    Дата конвертації23.08.2017
    Розмір27.98 Kb.
    Типкурсова робота

    ЗМІСТ

    Вступ

    1 Постановка завдання

    • 2 Математичні та алгоритмічні основи рішення задачі
    • 3 Функціональні моделі та блок-схеми рішення завдання
    • 4 Програмна реалізація рішення задачі
    • 5 Приклад виконання програми
    • висновок
    • Список використаних джерел та літератури

    Вступ

    Гра «морський бій» досить добре відома і популярна. Практично кожен школяр в той чи інший період свого життя грав в цю гру. В останні роки в зв'язку з появою комп'ютерів і нових навчальних і розвиваючих програм знову зріс інтерес до неї. Якщо набрати запит про пошук гри в Інтернет, то пошукова машина видасть кілька тисяч посилань. Тут і реклама, і різні варіанти гри, і якісні дослідження оптимальних стратегій гри і т.д. Але мало хто знає про те, що ця гра має серйозне наукове і практичне застосування, і для її аналізу можуть бути використані сучасні математичні та комп'ютерні методи. Як приклад такого додатка можна привести проблему ефективного пошуку записів у великих базах даних, що володіють складною багаторівневою структурою.

    Зупинимося на деяких основних правилах класичного варіанту гри. Перший гравець, гравець А, розставляє кораблі на квадратному ігровому полі з n клітин (зазвичай це поле клітин). Кораблі діляться на класи: одноклітинні, двоклітинного, трехклеточние і четирехклеточние. Гравець В на своєму полі розставляє свої кораблі. Зауважимо, що кораблі не повинні торкатися один одного. Гра полягає в тому, що гравці по черзі називають координати клітин, в яких, як вони припускають, розташовані кораблі супротивника, тобто як би роблять постріл з обраної клітці. Про попадання або промаху гравцеві повідомляється після пострілу. Гра продовжується до тих пір, поки у одного з гравців не будуть знищені всі кораблі.

    На перший погляд, ця гра носить чисто імовірнісний характер, так як гравці ведуть обстріл, не знаючи розташування кораблів супротивника. Але, придбавши деякий досвід гри, можна помітити, що існують стратегії розстановки кораблів, які зменшують ймовірність попадання в останній одноклітинний корабель. Наприклад, можна розташувати весь флот таким чином, щоб він займав мінімальне місце на ігровому полі, а один або два корабля ставлять на останньому просторі як на малюнку 1. Пошук кораблів також можна проводити, дотримуючись певної системи, яка дозволяє найбільш швидко виявити на початку гри багатоклітинні кораблі, а потім на останньому просторі шукати одноклітинні кораблі.

    Малюнок 1

    Ці якісні міркування показують, що у гравців А і В існує безліч нерівнозначних різних стратегій гри, тобто може бути поставлено питання про пошук оптимальних стратегій.

    Зауважимо, що вся ця різноманітність стратегій, як це буде показано нижче, визначається правилом, що забороняє ставити кораблі впритул, а також правилом закінчення гри.

    Надалі будемо розглядати тільки односторонню гру: гравець А розставляє кораблі, а гравець В веде їх пошук.

    Математичну модель гри можна будувати двома способами. Перший спосіб полягає в тому, що після кожного пострілу враховуються зміни поля гри і ймовірності виявлення кораблів. Така форма гри називається розгорнутою, а сама гра представляється багатокрокової. Складність застосування цього підходу пов'язана з необхідністю визначення ймовірностей подій, які є комбінацією великого числа елементарних подій. При збільшенні числа пострілів k кількість комбінацій зростає пропорційно k! (Факторіалом k).

    Другий спосіб полягає в тому, що в якості вихідного безлічі подій розглядається безліч стратегій, елементи яких представляють повну послідовність n пострілів. У цьому випадку гра стає однокрокової, тобто гравець робить вибір не однієї клітини при пострілі, а вибирає послідовність з n пострілів. Така форма гри називається нормальною. Другий підхід до побудови гри носить інтегральний характер, проте, в цьому випадку виникає проблема, пов'язана з поняттям закінчення гри.

    1. Постановка завдання

    Завдання полягає в розробці алгоритму, за яким комп'ютер зможе грати в «Морський бій» з максимальною якістю, і при цьому не підглядаючи розташування флоту гравця.

    Додаткове і очевидне умова: при кожній новій грі незалежно від розміщення сил противника комп'ютер повинен грати по-різному, тобто його ходи повинні бути не передбачувані.

    Необхідно згадати правила гри: учасники поєдинку роблять ходи по черзі, причому, якщо один з гравців потрапляє по кораблю суперника, то він отримує право наступного ходу. Якщо реалізувати пошук мети комп'ютером у вигляді окремої процедури, то треба якось навчити його запам'ятовувати результати минулих пострілів, щоб адекватно зробити наступний. З цього факту випливає, що найпростіше і раціональне рішення даної проблеми можна оформити у вигляді кінцевого автомата, найбільш точно описує послідовність дій.

    Можна виділити три стани:

    1) простріл ігрового поля по випадковим координатам до потрапляння по кораблю, після чого перехід в другий стан;

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

    3) розстріл корабля в отриманому напрямку до повного його знищення, після чого перехід в перший стан.

    І так, вся гра зациклена на трьох основних діях: простріл, обстріл і розстріл. Всі ці дії повинні тривати до тих пір, поки в однієї зі сторін не будуть знищені всі кораблі.

    простріл

    На цьому етапі комп'ютер повинен зловити будь-якої з кораблів противника. Для цього він буде стріляти по довільним незайнятим клітинам поля гравця. Набагато ефективніше спочатку розправитися з великими кораблями, тому вибираючи координати для пострілу треба перевіряти, що б в цій позиції міг розміститися найбільший з решти кораблів. Процес припиняється, як тільки відбудеться потрапляння. Позначимо підбиту частина корабля значенням «*», а промах «~» відповідної комірки поля. Якщо у гравця залишилися тільки однопалубні кораблі, то цим потраплянням корабель знищений повністю і обстрілювати його немає сенсу. В іншому випадку треба перейти до другого стану.

    обстріл

    На цьому кроці завдання полягає у визначенні напрямку спійманого корабля. Для цього треба обстріляти чотири осередки (якщо вони вільні), які можуть служити продовженням. У разі, коли всі чотири клітини обстріляні, а потрапляння не відбулося (однопалубний корабель), треба перейти до першого стану. Якщо в якийсь момент вдалося підбити ще одну палубу противника, то можна переходить до розстрілу даного корабля, т. К. Його напрямок стало відомо. Аналогічно першому стану, якщо у гравця залишилися кораблі не більше двох палуб, то цим потраплянням корабель знищений повністю і треба повернутися до прострілу.

    розстріл

    На попередньому етапі вдалося встановити в якому напрямку розміщений спійманий корабель. Тепер завдання полягає в його повному знищенні. Для цього треба стріляти праворуч або ліворуч (зверху чи знизу) підбитих палуб, поки не доб'ємо його цілком, після чого повернемося в стан прострілу. При цьому слід враховувати максимально можливий корабель і намагатися потрапити по четвертій палубі, коли чотирьох палубний корабель знищений, немає ніякого сенсу.

    приклад

    поле кораблів

    1

    1

    1

    1

    0

    0

    1

    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    0

    0

    0

    0

    0

    0

    0

    1

    0

    1

    0

    0

    0

    1

    0

    0

    0

    1

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    0

    0

    0

    0

    0

    0

    1

    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    0

    0

    0

    0

    1

    1

    0

    0

    0

    0

    1

    0

    1

    0

    0

    0

    0

    1

    1

    1

    Стратегія гри комп'ютера.

    1. Вибирається випадкова клітина, розглядається її значення.

    2. Якщо значення = 1 - потрапили в корабель, відзначаємо удар «*»;

    3. Якщо значення = 0 - промазали, відзначаємо удар «~»;

    4. Якщо значення = "*" або значення = "~", значить в цю клітку нами вже був проведений удар, повертаємося до кроку 1.

    Після того як всі кораблі розбиті, припиняємо бій. Поле розбитих кораблів

    *

    *

    *

    *

    ~

    ~

    *

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    *

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    *

    ~

    *

    ~

    ~

    ~

    *

    ~

    ~

    ~

    *

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    0

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    *

    ~

    ~

    ~

    ~

    ~

    0

    *

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    *

    ~

    ~

    ~

    ~

    *

    *

    ~

    ~

    ~

    ~

    *

    ~

    *

    ~

    ~

    ~

    ~

    *

    *

    *

    Нулями позначені ті клітини, в які ми не потрапили.

    2. Математичні та алгоритмічні основи рішення задачі

    Для того щоб приступити до побудови та аналізу математичної моделі гри, необхідно визначити ймовірності виявлення кораблів при різному їх розташуванні і різних системах пошуку

    На поле з n клітин розташований одноклітинний корабель. Визначимо ймовірність попадання в корабель k-им пострілом, тобто його знищення.

    Як простору елементарних фіналів вибору гравця В розглянемо безліч стратегій обстрілу ігрового поля, кожна стратегія складається з n пострілів,

    ,

    де - номер обраної клітини, тобто розглянемо безліч всіх вибірок з n по n клітин. Очевидно, що цей простір містить елементів і всі ці стратегії рівноможливими. Кількість стратегій з успішним результатом, тобто кількість вибірок, що містять на k-му місці шукану клітку

    .

    ймовірність влучення

    .

    Визначимо ймовірність знищення корабля за k пострілів. Ця подія полягає в тому, що корабель може бути знищений або першим пострілом, або другим і т.д., тобто сприятлива вибірка з k клітин містить шукану клітку з кораблем. Кількість сприятливих стратегій визначиться як число невпорядкованих вибірок з безлічі n - 1 клітин по k - 1 (одна клітина, зайнята кораблем не враховується при вибірці), помножене на число перестановок в самій вибірці k! і число перестановок клітин залишилися за вибіркою (n - k)! :) !. Ймовірність влучення в одноклітинний корабель за k пострілів

    . (1)

    Ускладнити завдання. На поле з n клітин розташований двоклітинного корабель. Визначимо ймовірність першого попадання в корабель (в одну з його клітин) пострілом з номером k. Повне число всіляких стратегій, як і в попередньому випадку, так само, а число сприятливих стратегій визначається як сума сприятливих стратегій попадання в одну клітку і попадання в другу клітку, тобто. Ймовірність влучення k-им пострілом дорівнює.

    Очевидно, що при обстрілі m-клітинного корабля або m одноклітинних кораблів, ймовірність попадання k-им пострілом дорівнює

    .

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

    ,

    де - вибірки, де зазначено першу клітку, або другу клітку, - вибірки, що містять одночасно дві клітини. отже

    і після перетворень отримаємо

    . (2)

    Зауважимо, що аналогічним чином можна визначити ймовірність попадання за k пострілів в корабель з m клітин. Завдання потрапляння за k пострілів в багатоклітинний корабель хоча б один раз є завданням пошуку корабля. Очевидно, що якщо врахувати геометрію корабля, то можна запропонувати систему його пошуку, при якій ймовірність виявлення стає вище. Дійсно, при пошуку двухклеточного корабля можна розглянути підмножина всіх стратегій, що містять обстріл, наприклад, клітин тільки з парними або з непарними номерами. Пошук двухклеточного корабля зведеться до пошуку одноклітинного корабля на цьому підмножині. Вважаючи n парних, для оптимальної ймовірності попадання за k пострілів отримаємо

    . (3)

    Знайдене значення ймовірності більше ймовірності, отриманої вище

    ,

    при всіх значеннях.

    Оптимальна стратегія пошуку трехклеточного і четирехклеточного корабля може бути отримана аналогічним чином.

    Ймовірність влучення в грі «Морський бій»

    Всього клітин 100

    а) ймовірність потрапити в який-небудь корабель дорівнює;

    б) ймовірність потрапити в чотирипалубних дорівнює;

    в) ймовірність потрапити в однопалубний дорівнює;

    Всього кораблів 10, не однопалубних 6, «клітинок» 16.

    а) ймовірність потрапити в чотирипалубних дорівнює;

    б) ймовірність потрапити в трипалубний дорівнює;

    в) ймовірність потрапити в двопалубний дорівнює.

    3. Функціональна модель вирішення задачі

    Функціональна модель вирішення задачі представлені на малюнку 2.

    Малюнок 2 - Функціональна модель вирішення задачі для функції BLOW

    4. Програмна реалізація рішення задачі

    ; про ткриваем файл для читання

    (Setq'>(Setq_field_(read'>(Setq input_stream (open «d: field.txt»: direction: input))

    ; з читав поле противника

    (Setq field (read input_stream))

    ; з акриваем файл

    (Close input_stream)

    ; до олічество кораблів

    (Setq user_ship 10)

    ; у Біван корабель

    (Defun set_missing_comp (lst ij ip jp)

    (Setq k (if (> = (- i 1) 0) (- i 1) i))

    (Setq l (if (> = (- j 1) 0) (- j 1) j))

    (loop

    (do

    ()

    ((Or (> k (+ i 1)) (> = k 10)))

    (do

    ()

    ((Or (> l (+ j 1)) (> = l 10)))

    (If (eql (nth l (nth k lst)) 1)

    (progn

    (Setq k 10)

    (Return t)

    )

    )

    (Setq l (+ l 1))

    )

    (Setq k (+ k 1))

    )

    (Return nil)

    )

    (Setq k (if (> = (- i 1) 0) (- i 1) i))

    (Setq l (if (> = (- j 1) 0) (- j 1) j))

    (loop

    (do

    ()

    ((Or (> k (+ i 1)) (> = k 10)))

    (do

    ()

    ((Or (> l (+ j 1)) (> = l 10)))

    (If (not (eql (nth l (nth k lst)) *)) (setf (nth l (nth k lst)) ~))

    (Setq l (+ l 1))

    )

    (Setq k (+ k 1))

    )

    (Return nil)

    )

    t

    )

    ; ш агаем за напрямом «хреста»

    (Defun set_missing (lst ij ip jp)

    (If (> = (- i 1) 0)

    (If (and (/ = (- i 1) ip) (eql (nth j (nth (- i 1) lst)) 1))

    (set_missing lst (- i 1) jij)

    )

    )

    (If (> = (- j 1) 0)

    (If (and (/ = (- j 1) jp) (eql (nth (- j 1) (nth i lst)) 1))

    (set_missing lst i (- j 1) ij)

    )

    )

    (If (<(+ i 1) 10)

    (If (and (/ = (+ i 1) ip) (eql (nth j (nth (+ i 1) lst)) 1))

    (set_missing lst (+ i 1) jij)

    )

    )

    (If (<(+ j 1) 10)

    (If (and (/ = (+ j 1) jp) (eql (nth (+ j 1) (nth i lst)) 1))

    (set_missing lst i (+ j 1) ij)

    )

    )

    (If (eql (nth j (nth i lst)) 1) (setf (nth j (nth i lst)) *))

    )

    ; ф ункції, що реалізує удар по полю

    (Defun blow (lst)

    ; в ибірать випадкову клітку

    (Setq i (random 10))

    (Setq j (random 10))

    (Setq n (nth j (nth i lst)))

    (cond

    ((Eql n 1)

    (progn

    ; з начение в клітці = 1

    ; у Біван корабель

    (Set_missing lst ijij)

    (Set_missing_comp lst ijij)

    (Setq user_ship (- user_ship 1))

    (If (/ = user_ship 0) (blow lst))

    )

    )

    ((Eql n 0)

    (progn

    ; з начение в клітці 0

    ; п ромахнулісь

    (Setf (nth j (nth i lst)) ~)

    (Blow lst)

    )

    )

    ; у ж були в цій клітці - вибираємо іншу

    ((Or (equal n *) (equal n ~)) (blow lst))

    )

    lst

    )

    ; у Біван противника !!!

    (Blow field)

    ; ф айл для записи

    (Setq output_stream (open «d: destroy_field.txt »: direction: output))

    ; з апісиваем побите поле противника

    (Print field output_stream)

    ; з акриваем файл

    (Close output_stream)

    5. Приклад виконання програми

    Приклад 1.

    Малюнок 3 - Поле кораблів

    Малюнок 4 - Розстріляне поле кораблів

    Приклад 2.

    Малюнок 5 - Поле кораблів

    Малюнок 6 - Розстріляне поле кораблів

    Приклад 3.

    Малюнок 7 - Поле кораблів

    Малюнок 8 - Розстріляне поле кораблів

    висновок

    Наведений приклад аналізу гри «Морський бій» показує можливість використання логічних ігор для поглибленого вивчення таких розділів математики, як комбінаторика, теорія множин і теорія ймовірностей. Зауважимо, що вивчення навіть найпростіших ігрових ситуацій дозволяє сформулювати проблеми, які становлять інтерес для сучасної інформатики і теорії пошуку.

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

    Список використаних джерел та літератури

    Бронштейн, І.М. Довідник з математики для інженерів і учнів втузів [Текст] / І.М. Бронштейн, К.А. Семендяев. - М .: Наука, 2007. - 708 с.

    Кремер, Н.Ш. Вища математика для економістів: підручник для студентів вищих навчальних закладів. [Текст] / Н.Ш. Кремер, 3-е видання - М.: ЮНИТИ-ДАНА, 2006. C. 412.

    Петросян, Л.А. Ігри пошуку [Електронний ресурс] / Л.А. Петросян, А.Ю. Гарнаев. - М .: СПбГУ, 1992. С. 314.

    Реалізація гри «Морський бій» [Електронний ресурс] - Режим доступу: http://aka-alex.narod.ru/index.htm

    Семакін, І.Г. Основи програмування. [Текст] / І.Г. Семакін, А.П. Шестаков. - М .: Світ, 2006. C. 346.

    Сіманков, В.С. Основи функціонального програмування [Текст] / В.С. Сіманков, Т.Т. Зангиев, І.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.

    Степанов, П.А. Функціональне програмування мовою Lisp. [Електронний ресурс] / П.А. Степанов, А.В. Бржезовскій. - М .: ГУАП, 2003. С. 79.

    Хювенен Е. Світ Лиспа [Текст] / Е. Хювенен, Й. Сеппянен. - М .: Світ, 1990. - 460 с.




    Скачати 27.98 Kb.