Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Використання евристичної функції для створення гри.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
Використання евристичної функції для створення гри
Методичні вказівки
до лабораторної роботи № 2 з курсу:
“Системи штучного інтелекту”
для студентів
Затверджено
на засіданні кафедри
“Електронних обчислювальних машин”
Протокол №
Від 2003 р.
Львів 2003
Використання евристичної функції для створення гри. Методичні вказівки до лабораторної роботи № 2 з курсу: “Системи штучного інтелекту” для студентів , 16 с.
Укладач:
Ємець В.Ф., професор, д.т.н.
Сокіл В.М., асистент
Юрчак І.Ю, доцент, к.т.н.
Відповідальний за випуск:
Кремінь В.Т., ст. викладач кафедри ЕОМ
Рецензенти:
Березко Л.О., доцент кафедри ЕОМ, к.т.н.
Каркульовський В.І., доцент кафедри АСУ, к.т.н.
1. Мета роботи
Cтворення зразку евристичної функції, яка описує стан укладанки, що полягає у складанні в зростаючому порядку цифр від 1 до 8. Створений алгоритм має за мету розв’язання гри при мінімально можливій кількості кроків, а також розпізнавання станів, у яких гра не має розв’язку. Початковий стан гри встановлюється випадковим чином. Головними елементами евристичної функції є складові підрахунку відстаней вибраних елементів від їх попереднього місця.
2. Теоретичні відомості
Алгоритм гри є простим і базується на 3 засадах
Підраховане значення евристичної функції відбиває єдиний можливий крок, що залежить від розташування нульового елементу і для якого значення функції є мінімальним (нескінченне від біжучого значення функції)
Не варто повторювати попередній крок, якщо він призводить до заплутування алгоритму, і відповідно, не скорочує кількість кроків
Нульове значення евристичної функції означає, що даний стан гри є кінцевим станом (елементи є укладеними або їх укладання є неможливим)
Стан гри описаний 9-елементною таблицею Tab[8] цілих цифр в полях пронумерованих від 0 до 8
Приймемо наступну послідовність алгоритму:
Етап 1
Початковою метою гри є уставляння одиниці на першому місці (в таблиці це поле з номером 0). Відповідно, цей порядок повинен мати найбільший приоритет, тобто йому має відповідати складова, що має найбільшу вагу в моделі функції. Ось ця складова:
wartosc+=1000000*abs(miejsce[1]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=1000000*abs(miejsce[1]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
Де значення змінної szukana в цей момент дорівнює 0.
Найбільша вага цієї складової у зразку евристичної функції доводить, що цей елемент ніколи не буде пересунуто зі свого місця.
На цьому етапі гри нульове поле прагне до нульового місця таблиці елементів
wartosc+=abs(miejsce[0]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=abs(miejsce[0]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
Етап 2
Наступний крок полягає у встановленні 2 і 3 на свої місця. Очевидно евристична функція намагається встановити їх відповідно стану:
Де х означає поле замін перед випадковим укладанням залишкових цифр 4,5,6,7,8
Цей етап описує наступний фрагмент коду:
//відповідає за 2
wartosc+=100000*abs(miejsce[2]%3-(szukana+2)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=100000*abs(miejsce[2]/3-(szukana+2)/3);
//розглядання нормованої метрики по вертикалі
//відповідає за 3
wartosc+=10000*abs(miejsce[3]%3-(szukana+5)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=10000*abs(miejsce[3]/3-(szukana+5)/3);
//розглядання нормованої метрики по вертикалі
Елемент 2 має більшу вагу ніж 3, і його варто поставити на власну позицію першим. На цьому етапі нульове поле прагне до першого елементу таблиці.
if (Tab[0]==1) szukana++;
//до уставляння 2 i 3 у рядку
wartosc+=abs(miejsce[0]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=abs(miejsce[0]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
тобто значення змінної szukana буде зараз 1.
Зауважимо, що у момент гри представлений вище, не має можливості виконання іншого кроку, як відправлення 2 і 3 на свої місця. Це виникає з початкових умов (не можна повернутись) і окрім цього алгоритм забезпечує, що одиниця лишається на свому місці.
Очевидно, що потрібно забезпечити перед досягненням нуля евристичною функцією (що призвело би до закінчення алгоритму на цьому етапі) привласнити їй числове значення
if (Tab[0]==1 && Tab[2]==2 && Tab[5]==3) wartosc+=30;
Після встановлення 2 і 3 на власні місця мусимо скорегувати значення евристичної функції у 110000, що реалізує наступний код:
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3)
//після встановлення 2 i 3 на місця
{
szukana=3;
wartosc-=110000;
}
Алгоритм забезпечує пересування нульового елементу в таблиці до поля з номером 3, що є необхідним при переході до наступного етапу гри.
Етап 3
На цьому етапі, що є подібним до етапу 2, займемося 4 і 7. Хочемо прийти до наступного стану гри:
Де х означає поле, що можна заміняти перед випадковим укладанням залишених цифр 5, 6, 8. За це відповідає наступний фрагмент коду:
//відповідає за 4
wartosc+=1000*abs(miejsce[4]%3-(szukana+6)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=1000*abs(miejsce[4]/3-(szukana+6)/3);
//розглядання нормованої метрики по вертикалі
//відповідає за 7
wartosc+=100*abs(miejsce[7]%3-(szukana+7)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=100*abs(miejsce[7]/3-(szukana+7)/3);
//розглядання нормованої метрики по вертикалі
Елемент 4 має вищу вагу ніж 7, тому його слід поставити на власну позицію першим. На цьому етапі нульове поле прагне до третього елементу таблиці (встановлений в кінці етапу 2).
wartosc+=abs(miejsce[0]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=abs(miejsce[0]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
Тобто значення змінної szukana зараз буде 3.
Подібно, як у етапі 2 зауважимо, що у момент гри, представлений вище, алгоритм не має можливості виконання іншого кроку, як встановлення 4 і 7 на власні місця (pomimo że zwiększa to wartość funkcji heurystycznej w stosunku do wartości bieżącej). Це виникає з початкових умов (не можна повернутись) разом з алгоритмом, що забезпечує, що елементи 1,2,3 лишаються на своїх місцях.
Очевидно, що потрібно забезпечити перед досягненням нуля евристичною функцією (що призвело би до закінчення алгоритму на цьому етапі) впровадити числове значення
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3 && Tab[6]==4 && Tab[7]==7) wartosc+=20;
Аналогічно, як в етапі 2 виконуємо корекцію значення евристичної функції у 1100:
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3 && Tab[3]==4 && Tab[6]==7)
//після встановленя 4 i 7 на місця
{
szukana=8;
wartosc-=1100;
}
Нульовий елемент на потребу етапу 4 буде зараз розташований у 8 полі таблиці.
Етап 4
Є кінцевим етапом. Він однозначно прагне до встановлення нульового елементу в поле 8, за умови, що принаймі 5 або 6 або 8 знаходяться на свому місці ( якщо це не так, тоді функція приймає числове значення 10, що означає бажаний стан):
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3 && Tab[3]==4 && Tab[6]==7 && Tab[4]!=5 && Tab[5]!=6 && Tab[7]!=8) wartosc+=10;
wartosc+=abs(miejsce[0]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=abs(miejsce[0]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
Якщо це відбулося, можна вважати, що гра укладена чи не вдається до укладання. Очевидно, в обох випадках, значення функції буде дорівнювати 0. Poprawne Правильне укладання описується перед визначенням послідовності елементів в таблиці Tab, в іншому випадку гра не вдається до укладання.
Також існують стани, в яких значення функції потрібно змодифікувати, щоб алгоритм почав робити виправлення, у відповідності до етапу 1. За це відповідає наступний фрагмент коду:
if (Tab[1]!=0 && Tab[2]!=2 && Tab[2]!=0 && Tab[8]!=0 && Tab[5]==3) wartosc+=500000;
if (Tab[2]==3 && Tab[5]==2 && Tab[7]==0 && Tab[8]==1) wartosc=80;
if (Tab[0]==0 && Tab[1]==1 && Tab[3]==2) wartosc=70;
if (Tab[1]==0 && Tab[3]==1 && Tab[4]==2) wartosc=60;
if (Tab[0]==1 && Tab[3]==0 && Tab[6]==2) wartosc=50;
if (Tab[2]==2 && Tab[7]==0 && Tab[8]==1) wartosc=40;
Значення евристичної функції, наведені вище, є числовими і не мають впливового значення при розв’язуванні поставленого завдання, але в значній мірі призначені для зміни врахування кроків у застосованому алгоритмі.
Наведений нижче фрагмент коду описує використання евристичної функції:
int CPUZZLEDlg::Funkcja()
{
int miejsce[9],szukana=0,wartosc=0;
for(miejsce[0]=0;miejsce[0]<9;miejsce[0]++) if (Tab[miejsce[0]]==szukana) break;
for(miejsce[1]=0;miejsce[1]<9;miejsce[1]++) if (Tab[miejsce[1]]==szukana+1) break;
for(miejsce[2]=0;miejsce[2]<9;miejsce[2]++) if (Tab[miejsce[2]]==szukana+2) break;
for(miejsce[3]=0;miejsce[3]<9;miejsce[3]++) if (Tab[miejsce[3]]==szukana+3) break;
for(miejsce[4]=0;miejsce[4]<9;miejsce[4]++) if (Tab[miejsce[4]]==szukana+4) break;
for(miejsce[7]=0;miejsce[7]<9;miejsce[7]++) if (Tab[miejsce[7]]==szukana+7) break;
//відповідає за 1
wartosc+=1000000*abs(miejsce[1]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=1000000*abs(miejsce[1]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
//відповідає за 2
wartosc+=100000*abs(miejsce[2]%3-(szukana+2)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=100000*abs(miejsce[2]/3-(szukana+2)/3);
//розглядання нормованої метрики по вертикалі
//відповідає за 3
wartosc+=10000*abs(miejsce[3]%3-(szukana+5)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=10000*abs(miejsce[3]/3-(szukana+5)/3);
//розглядання нормованої метрики по вертикалі
//відповідає за 4
wartosc+=1000*abs(miejsce[4]%3-(szukana+6)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=1000*abs(miejsce[4]/3-(szukana+6)/3);
//розглядання нормованої метрики по вертикалі
//відповідає за 7
wartosc+=100*abs(miejsce[7]%3-(szukana+7)%3);
//розглядання нормованої метрики по горизонталі
wartosc+=100*abs(miejsce[7]/3-(szukana+7)/3);
//розглядання нормованої метрики по вертикалі
//забезпечення, щоб під час укладання функція не досягнула 0
if (Tab[1]!=0 && Tab[2]!=2 && Tab[2]!=0 && Tab[8]!=0 && Tab[5]==3) wartosc+=500000;
if (Tab[2]==3 && Tab[5]==2 && Tab[7]==0 && Tab[8]==1) wartosc=80;
if (Tab[0]==0 && Tab[1]==1 && Tab[3]==2) wartosc=70;
if (Tab[1]==0 && Tab[3]==1 && Tab[4]==2) wartosc=60;
if (Tab[0]==1 && Tab[3]==0 && Tab[6]==2) wartosc=50;
if (Tab[2]==2 && Tab[7]==0 && Tab[8]==1) wartosc=40;
if (Tab[0]==1 && Tab[2]==2 && Tab[5]==3) wartosc+=30;
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3 && Tab[6]==4 && Tab[7]==7) wartosc+=20;
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3 && Tab[3]==4 && Tab[6]==7 && Tab[4]!=5 && Tab[5]!=6 && Tab[7]!=8) wartosc+=10;
if (Tab[0]==1) szukana++;
//до уставляння 2 і 3 у рядку
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3)
//після уставляння 2 і 3 на місце
{
szukana=3;
wartosc-=110000;
}
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3 && Tab[3]==4 && Tab[6]==7)
//після уставляння 4 і 7 на місце
{
szukana=8;
wartosc-=1100;
}
//відповідає за 0
wartosc+=abs(miejsce[0]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=abs(miejsce[0]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
return wartosc;
}
3. Контрольні запитання
Застосування евристичних алгоритмів для створення ігр.
Алгоритм для укладанки
4. Лабораторне завдання
Завдання полягає у написанні програми, яка спроможна в найкоротший час або при використанні мінімальної кількості операцій впорядкувати двовимірний масив чисел, використовуючи для пересування вільну комірку
Де знак “_“ означає пусте місце, на яке можна пересувати елемент з сусідньої комірки
Програма повинна:
1. Встановити початковий стан укладанки випадковим чином або дозволити його встановлення, наприклад:
2. Перевирити, чи укладанка є можливою для укладання, тобто, чи після випадкового кроку або після впровадження початкового стану не трапляється ситуація, де переставлені елементи (тут двійка з одиницею):
3. Представити (краще графічно) наступні кроки алгоритму, так, щоб можна було докладно їх відслідкувати разом із значеннями евристичної функції, що належать окремим станам (див. пояснення нижче).
Пояснення
Евристична функція описує (зокрема і у цьому випадку) ступінь невпорядкованості стану – його ентропії. Вибір складових цієї функції, а також їх ваг залишається за автором програми. Прикладними складовими евристичної функції є:
сума відстані кожного елементу від “свого” місця wg локальної метрики (сума відстанів по вертикалі та по горизонталі)
сума квадратів відстанів кожного елементу від пустого місця (чим далі, тим складніше пересунути)
відстань від “свого” та/чи пустого місця по діагоналі (наприклад, з вагою =2)
штрафні бали (збільшення невпорядкованості) за те, що дана пара елементів є замінена місцями.
Наприклад, вага евристичної функції для стану укладанки з пункту 1
при розгляданні лише першого з описаних вище складових з вагою =1, становить:
EMBED Equation.3 0 +
//одиниця на свому місці
1 +
//пятірка знаходиться на 1 крок по вертикалі
0 +
//трійка на свому місці
2 +
//двійка знаходиться на один крок по вертикалі і на один по горизонталі
2 +
//пусте місця знаходиться від свого місця як двійка, один крок по вертикалі, один по горизонталі
2 +
//четвірка: два кроки по горизонталі
1 + // itd.
2 + //
2 +
До евристичної функції, вжитої в завданні, кожна група студентів повинна придумати оригинальний алгоритм.
5. Зміст звіту
Мета роботи.
Основні теоретичні відомості.
Результат виконання індивідуального завдання.
Висновок.
6. Список літератури
Александров Е.А. Основы эвристических решений – М.: Наука, 1995 – 280 с.
Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интелектуальных систем – СПб: Питер, 2000. - 384 с.
Глибовець М.М., Олецький О.В. Штучний інтелект – Київ: Видавничий дім “КМ Академія”, 2002. – 366 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора