Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Ітераційна гра з нульовою сумою
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2005
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра електронних
обчислювальних машин
Звіт
про виконання лабораторної роботи № 2
з курсу „ Теорія колективної поведінки інтелектуальних систем ”
Тема:
Ітераційна гра з нульовою сумою
Львів – 2005
Мета: Реалізувати програмну модель ітераційної гри з нульовою сумою та дослідити власну поведінку в цій грі.
Загальні відомості
За допомогою ітераційної гри двох гравців з нульовою сумою (zero-sum game) процес навчання досліджується. Одним гравцем виступає студент, другим – змодельоване середовище (одне з трьох: статичне детерміноване, динамічне детерміноване, стаціонарне випадкове). В кожній партії (ітерації) гри кожний з гравців обирає одиницю або двійку. Мета студента – вгадати хід суперника, мета середовища – протилежна (тобто студент виграє в тих випадках, коли він і середовище обирають однакову дію). Виграшний (правильний) хід приносить гравцю один бал. Перемагає той, хто першим набере 21 бал. Матриця виграшів має наступний вигляд:
d2=1
d2=2
d1= 1
S1 = 1
S2 = 0
S1=0
S2=1
d1= 2
S1 = 0
S2 = 1
S1=1
S2=0
d1 – стратегія (дія), яку обирає студент;
d2 – стратегія (дія), яку обирає середовище;
S1 – виграш студента;
S2 – виграш середовища.
В процесі гри визначаються три залежності:
Залежність біжучого виграшу від часу: S(t).
Залежність біжучого сумарного виграшу від часу: S((t) = (St.
Залежність біжучого проценту виграшних дій від часу: Ps(t) = (St / t.
Поведінка середовищ:
Статичне детерміноване середовище завжди обирає одиницю або двійку.
Динамічне детерміноване середовище K1=const разів обирає одиницю, далі K2=const разів обирає двійку, після чого цей цикл повторюється.
Стаціонарне випадкове середовище з ймовірністю p обирає одиницю, і з ймовірністю (1 - p) обирає двійку.
Завдання
1. Скласти програму наступного змісту (алгоритм роботи програми):
Випадково вибрати тип середовища (env_model)
Ініціалізувати середовище (випадкова ініціалізація)
Відкрити файл для збереження результатів
Цикл від 1 до T (індекс t)
Отримати стратегію (дію), обрану користувачем
Отримати стратегію (дію), обрану середовищем
Визначити біжучий виграш/програш користувача за допомогою матриці виграшів
Модифікувати значення сумарних виграшів користувача та середовища
Модифікувати значення проценту виграшних (правильних) дій користувача
Якщо користувач або середовище набрали 21 бал, то припинити гру
Запам’ятати отримані значення у файлі результатів
Перейти на п.4
Закрити файл результатів.
2. Реалізувати моделі наступних типів середовища:
2.1. Статичне детерміноване.
2.2. Динамічне детерміноване.
2.3. Стаціонарне випадкове.
3. Дослідити власну поведінку в реалізованих моделях середовища (метою поведінки є отримання максимального сумарного виграшу за найменшу кількість спроб). Отримати вказані залежності від часу для кожного з типів середовища.
4. Порівняти отримані залежності та зробити висновки. Текст програми
/* Copyright (c) 2005 alb. All Rights Reserved. * Multiagent systems Lab
* Computer Engineering Department * Lviv Polytechnic National University
* ===============================================
* Multiagent Systems. Lab work 02. Iterated zero-sum game.
*
* You are in "game of 21" with environment (opponent).
* Available strategies (action space) are D={1,2}
*
* Payoff matrix for you (used in each iteration of game) is the following
* | 1 | 2 |
* --------|-------|-------|
* 1 | 1 | 0 |
* --------|-------|-------|
* 2 | 0 | 1 |
* ________|_______|_______|
* You must try to win in this game mimimizing the number of iterations. */
#include "stdafx.h"
int t; // current time step
int T = 100; // maximum number of time steps (interactions with environment)
int env_model; // environmetn code:
// 1 - envoronment with static response
// 2 - envoronment with predetermined dynamic response
// 3 - envoronment with stationary random response:
// binary bandit task (n-armed bandit, n=2)
// variables for environment's parameters
// 1 - envoronment with static response
int env1;
// 2 - envoronment with predetermined dynamic response
int env2[2];
int max_period =6;
int env_action1;
int env_action2;
int cd1 = 0;
int cd2 = 0;
// 3 - envoronment with stationary random response:
float env3;
// file for saving results
char * res_file_name = "__TEST__.dat";
FILE * res_file;
int action=0; // current action of the user (can be 1 or 2)
int env_action = 0; // current action of the environment (can be 1 or 2)
// game results
int S = 0; // current win over time S(t)
int sumS = 0; // total win over time sumS(t)
float prcS = 0; // success percent(rate) over time prcS(t)
int env_sumS = 0; // total win over time for environment
int winer = 0; // winner code (1 - user, 0 - environment)
int randomChoice3 (void) {
int tmp;
float rand_num;
rand_num = (float)rand() / (float)RAND_MAX;
rand_num = (float)rand() / (float)RAND_MAX;
if ((rand_num >= 0) && (rand_num <= 0.333)) {tmp = 1; return tmp;}
if ((rand_num > 0.333) && (rand_num <= 0.666)) {tmp = 2; return tmp;}
if ((rand_num > 0.666) && (rand_num <= 1)) {tmp = 3; return tmp;}
return -1;
}
int randomChoice2 (void) {
int tmp;
float rand_num;
rand_num = (float)rand() / (float)RAND_MAX;
rand_num = (float)rand() / (float)RAND_MAX;
if ((rand_num >= 0) && (rand_num <= 0.5)) {tmp = 1; return tmp;}
if ((rand_num > 0.5) && (rand_num <= 1)) {tmp = 2; return tmp;}
return -1;
}
// automatic initialization of environment
void env_init (int env_id) {
int tmp;
switch (env_id) {
case 1: // environment with static response
env1 = randomChoice2();
break;
case 2: // environment with predetermined dynamic response
env_action1 = randomChoice2();
if (env_action1 == 1) env_action2 = 2; else env_action2 = 1;
tmp = (int) ((float)(max_period - 1) * (float)rand() / (float)RAND_MAX);
env2[0] = tmp + 1;
tmp = (int) ((float)(max_period - 1) * (float)rand() / (float)RAND_MAX);
env2[1] = tmp + 1;
break;
case 3: // environment with stationary random response
env3 = (float)rand() / (float)RAND_MAX;
break;
default: printf("lab1 error: wrong env model code specified\n");
}
}
// environment decision
int env_decision (int env_id) {
int decision = 1;
float ftmp;
switch (env_id) {
case 1:
decision = env1; break;
case 2:
if (cd1 < env2[0]) {
cd1 ++;
decision = env_action1;
}
else {
if (cd2 < (env2[1] - 1)) {
cd2 ++;
decision = env_action2;
}
else {
cd1 = 0; cd2 = 0;
decision = env_action2;
}
}
break;
case 3:
ftmp = (float)rand() / (float)RAND_MAX;
if (ftmp < env3) decision = 1;
else decision = 2;
break;
default: printf("lab1 error: wrong env model code specified\n");
}
return decision;
}
// print environment parameters
void env_info (void) {
printf("\nenvironment = %d", env_model);
switch (env_model) {
case 1:
printf("\n%d\n\n",env1);
break;
case 2:
printf("\n(%d) - %d, (%d) - %d\n\n", env_action1, env2[0], env_action2, env2[1]);
break;
case 3:
printf("\n(1) - %f, (2) - %f\n\n", env3, 1 - env3);
break;
default: printf("lab1 error: wrong env model code specified\n");
}
}
void res_open_file (void) {
if ((res_file = fopen(res_file_name,"w")) == NULL)
fprintf(stderr, "Cannot open file <%s> for experimental results.\n", res_file_name);
}
void res_close_file (void) {
fclose(res_file);
}
void res_store_next_string (void) {
fprintf(res_file,"%d,%d,%f\n",S,sumS,prcS);
}
int main (int argc, char* argv[])
{
// init random-number generator
srand((unsigned)time(NULL));
// random choice of environment model
env_model = randomChoice3();
// set parameters of chosen environment
env_init(env_model);
// open file for results
res_open_file();
// main cycle of program (over game interactions)
for (t=0; t < T; t++) {
// get user move from console
printf("make your move: ");
scanf("%d",&action);
// get environment move
env_action = env_decision(env_model);
// output user and environment moves
printf("your move: %d, env move: %d --> ",action, env_action);
// find who win in this iteration (payoff matrix realization)
if (action == env_action) { // user win (guessed the environment move)
S = 1;
sumS = sumS + S;
prcS = (float)sumS / ((float)t + 1);
}
else { // user lose
S = 0;
env_sumS = env_sumS + 1;
prcS = (float)sumS / ((float)t + 1);
}
// save current results in file
res_store_next_string();
// print current results
printf("%d | your total: %d | env total: %d\n", S, sumS, env_sumS);
// check total win
if (sumS == 21) {winer = 1; break;}
else
if (env_sumS == 21) {winer = 0; break;}
}
// output game result
if (winer == 1) printf("\n you win (number of moves = %d)\n",t + 1);
else printf("\n you lose (number of moves = %d)\n",t + 1);
// print information about environment
env_info();
// close file with results
res_close_file();
return 0;
}
Результати
Залежності біжучого проценту виграшних дій від часу (середнє значення виграшу, що припадає на одну дію): Ps(t) = (Rt / t для кожного типу середовища у вигляді графіку та із зазначенням чисельних характеристик середовищ, для яких отримано результати:
1. Статичне детерміноване середовище.
S(t)
S((t) = (St
Ps(t) = (Rt / t
0
0
0
1
1
0,5
1
2
0,666667
1
3
0,75
1
4
0,8
1
5
0,833333
1
6
0,857143
1
7
0,875
1
8
0,888889
1
9
0,9
1
10
0,909091
1
11
0,916667
1
12
0,923077
1
13
0,928571
1
14
0,933333
1
15
0,9375
1
16
0,941176
1
17
0,944444
1
18
0,947368
1
19
0,95
1
20
0,952381
1
21
0,954545
Залежність біжучого виграшу від часу: S(t).
Залежність біжучого сумарного виграшу від часу: S((t) = (St.
Залежність біжучого проценту виграшних дій від часу: Ps(t) = (St / t.
you win (number of moves = 22)
environment = 1
2
2. Динамічне детерміноване середовище.
Залежність біжучого виграшу від часу: S(t).
S(t)
S((t) = (St
Ps(t) = (Rt / t
0
0
0
0
0
0
1
1
0,333333
0
1
0,25
1
2
0,4
1
3
0,5
1
4
0,571429
1
5
0,625
1
6
0,666667
1
7
0,7
1
8
0,727273
1
9
0,75
1
10
0,769231
1
11
0,785714
1
12
0,8
1
13
0,8125
1
14
0,823529
1
15
0,833333
1
16
0,842105
1
17
0,85
1
18
0,857143
1
19
0,863636
1
20
0,869565
1
21
0,875
Залежність біжучого сумарного виграшу від часу: S((t) = (St.
Залежність біжучого проценту виграшних дій від часу: Ps(t) = (St / t.
you win (number of moves = 24)
environment = 2
(2) - 1, (1) – 2
3. Стаціонарне випадкове середовище.
Залежність біжучого виграшу від часу: S(t).
S(t)
S((t) = (St
Ps(t) = (Rt / t
0
0
0
1
1
0,5
0
1
0,333333
0
1
0,25
1
2
0,4
0
2
0,333333
1
3
0,428571
1
4
0,5
1
5
0,555556
1
6
0,6
1
7
0,636364
1
8
0,666667
1
9
0,692308
1
10
0,714286
1
11
0,733333
1
12
0,75
1
13
0,764706
1
14
0,777778
1
15
0,789474
1
16
0,8
1
17
0,809524
0
17
0,772727
0
17
0,73913
1
18
0,75
1
19
0,76
1
20
0,769231
1
21
0,777778
Залежність біжучого сумарного виграшу від часу: S((t) = (St.
Залежність біжучого проценту виграшних дій від часу:
Ps(t) = (St / t.
you win (number of moves = 27)
environment = 3
(1) - 0.064699, (2) - 0.935301
Висновки: виконуючи дану лабораторну роботу, я досліджував власну поведінку в ітераційній грі з нульовою сумою в різних моделях середовищ.
У грі із статичним детермінованим середовищем виграшу (21 пункт) я досягнув за 22 ітерації, оскільки воно є найпростішим для вивчення. У грі із динамічним детермінованим середовищем виграшу я досягнув вже за 24 ітерації, оскільки довелося затратити більше часу на його дослідження. А у грі із стаціонарним випадковим середовищем виграшу я досягнув за найдовший час - 27 ітерацій.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора