Ітераційна дилема ув’язненого. Звіт про виконання лабораторної роботи з Теорія колективної поведінки інтелектуальних систем . Робота № 111390

Перехід до торгівельного партнера Binance

Ітераційна дилема ув’язненого

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра електронних обчислювальних машин

Інформація про роботу

Рік:

2005

Тип роботи:

Звіт про виконання лабораторної роботи

Предмет:

Теорія колективної поведінки інтелектуальних систем

Група:

КІ-44

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра електронних обчислювальних машин Звіт про виконання лабораторної роботи № 6 з курсу „ Теорія колективної поведінки інтелектуальних систем ” Тема: Ітераційна дилема ув’язненого Львів – 2005 Мета: Ознайомитись з принципами співвідношення співпраці та суперництва в колективі агентів. Загальні відомості Для дослідження принципів співвідношення співпраці та суперництва використовується модель колективної поведінки під назвою "дилема ув’язненого" [1,3,4,5]. Дилема ув’язненого це гра двох осіб з не нульовою сумою (general-sum game). Кожний з гравців має дві можливості: співпрацювати (C - cooperate) чи протидіяти (D - defect). Якщо перший гравець протидіє, то якщо другий буде співпрацювати, то отримає за свою наївність найбільше у грі покарання (S), тоді як перший гравець отримає найбільше у грі заохочення (T) за свою підступність. В іншому випадку, якщо другий гравець буде також протидіяти, то обидва вони отримають однакове невелике покарання (P) за взаємну протидію. Якщо обидва гравця співпрацюють, то вони отримають невелике заохочення (R) за добре ставлення один до одного. Дилема ув’язненого має зміст, якщо T>R>P>S, де R>(S+T)/2. Матриця гри для дилеми ув’язненого виглядає наступним чином A2 C D A1 C R1, R2 S1, T2 D T1, S2 P1, P2 Один з можливих варіантів гри: T = 5, R = 3, P = 1, S = 0. Ітераційна дилема ув’язненого (iterated prisoner’s dilemma, IPD) – це гра з багатокроковим повторенням, в якій кожний з опонентів пам’ятає деяку кількість (глибина пам’яті) результатів минулих розіграшів. Згідно теорії ігор оптимальною (стійкою) стратегією в однокроковій IPD є протидія (D) (див. основне припущення теорії ігор та принцип обережності). В той же час при збільшені кількості кроків виникає задача максимізації середнього виграшу окремого гравця, яка не має тривіального рішення. Це означає, що постійна протидія не гарантує максимального середнього виграшу в IPD. При дослідженні ітераційної дилеми ув’язненого розглядають наступні стратегії поведінки гравця (IPD-агента): ALLC: завжди співпрацювати; ALLD: завжди протидіяти; TFT (Tit for tat, "зуб за зуб"): спочатку співпрацювати, потім віддзеркалювати дії опонента; Grim ("невблаганний"): співпрацювати до першої протидії, потім завжди протидіяти; Stochastic: обирати співпрацю та протидію випадково з фіксованими ймовірностями (стаціонарне випадкове середовище) та ін. [2]. В найпростішому випадку в стратегії (алгоритмі) поведінці гравця враховується результат лише попередньої партії (ітерації) гри. Зі збільшенням глибини пам’яті гравця стратегія (алгоритм) його поведінки суттєво ускладнюється. Ітераційна дилема ув’язненого для двох агентів (N=2) узагальнюється для випадку, коли N>2, за допомогою механізму випадкової парної взаємодії (див. адаптивне управління з наслідуванням). Текст програми /* Copyright (c) 2005 alb. All Rights Reserved. * Multiagent systems Lab * Computer Engineering Department * Lviv Polytechnic National University * =============================================== * Multiagent Systems. Lab work 06. * Multiagent design II: Iterated Prisoners Dilemma (iterated general-sum game) * * Here user (student) or RL-agent are in IPD with opponent called IPD-agent. * Available strategies (set of actions) are {C,D} C=1 -> cooperate, D=2 -> defect. * Payoff matrix for players (used in each iteration of game) * | C#2 | D#2 | * _______|_______|_______| * C#1 | R1,R2 | S1,T2 | * _______|_______|_______| * D#1 | T1,S2 | P1,P2 | * _______|_______|_______| * requirements: T > R > P > S, and R > (S + T) / 2. * example: T = 5, R = 3, P = 1, S = 0. * The aim is to obtain maximum total win over T iterations. * Implemented here IPD-agents are ALLC, ALLD, Stochastic, Grim, TFT. */ #include "stdafx.h" int T = 5, R = 3, P = 1, S = 0; int t; // current time step int Time = 50; // maximum number of time steps (interactions with IPD-agent) int pda_model; // IPD-agent code: // 0 - ALLC // 1 - ALLD // 2 - IPD-agent with predetermined dynamic response // 3 - IPD-agent with stationary random response // 4 - grim IPD-agent // 5 - TFT (tit for tat) IPD-agent // variables for IPD-agent // 2 - IPD-agent with predetermined dynamic response int pda2[2]; int max_period =6; int pda_action1; int pda_action2; int cd1 = 0; int cd2 = 0; // 3 - IPD-agent with stationary random response float pda3; // probability of cooperation for stochastic IPD-agent // 4 - grim IPD-agent int pda4_state = 1; // initially cooperate // 5 - TFT (tit for tat) IPD-agent int pda5_prev = 1; // previous action of opponent (initially think that cooperate) // file for saving results char * res_file_name = "maqs.tk"; FILE * res_file; int human = 1; // who plays with IPD-agent (0 = RL-agent, 1 = human) int prev_action = 1; int action = 1; // current action of the user (can be 1 or 2) int pda_action = 0; // current action of the environment (can be 1 or 2)// human/RL-agent results int W = 0; // current win over time W(t) int sumW = 0; // total win over time sumW(t) float prcW = 0; // success percent(rate) over time prcW(t) // IPD-agent results int pda_W = 0; // current win over time W(t) int pda_sumW = 0; // total win over time sumW(t) float pda_prcW = 0; // success percent(rate) over time prcW(t) // common result float avr_sumW = 0; // average total win over time float avr_prcW = 0; // average total success rate over time int winer = 0; // winner code (1 -> human/RL-agent, 0 -> IPD-agent) int actNumber = 2; // action number of RL-agent int Sa[2]; int ka[2]; double Qa[2]; double epsilon = 0.1; // probability of random move int randomChoice (int _n) { int r; srand( (unsigned)time( NULL ) ); r = (int) ((float)_n * (float)rand() / (float)RAND_MAX); return r + 1; } // automatic initialization of IPD-agent void pda_init (int pda_id) { int tmp; switch (pda_id) { case 0: // ALLC break; case 1: // ALLD break; case 2: // IPD-agent with predetermined dynamic response pda_action1 = randomChoice(2); if (pda_action1 == 1) pda_action2 = 2; else pda_action2 = 1; tmp = (int) ((float)(max_period - 1) * (float)rand() / (float)RAND_MAX); pda2[0] = tmp + 1; tmp = (int) ((float)(max_period - 1) * (float)rand() / (float)RAND_MAX); pda2[1] = tmp + 1; break; case 3: // IPD-agent with stationary random response (Stochastic) pda3 = (float)rand() / (float)RAND_MAX; break; case 4: // Grim break; case 5: // TFT break; default: printf("lab6 error: wrong IPD-agent code <pda_id> specified\n"); } } // IPD-agent decision int pda_decision (int pda_id) { int decision = 1; float ftmp; switch (pda_id) { case 0: // ALLC decision = 1; break; case 1: // ALLD decision = 2; break; case 2: // IPD-agent with predetermined dynamic response if (cd1 < pda2[0]) { cd1 ++; decision = pda_action1; } else { if (cd2 < (pda2[1] - 1)) { cd2 ++; decision = pda_action2; } else { cd1 = 0; cd2 = 0; decision = pda_action2; } } break; case 3: // IPD-agent with stationary random response (Stochastic) rand();rand();rand(); ftmp = (float)rand() / (float)RAND_MAX; if (ftmp < pda3) decision = 1; else decision = 2; break; case 4: // Grim if (pda4_state == 0) decision = 2; else if(prev_action == 2) {pda4_state = 0; decision = 2;} else decision = 1; break; case 5: // TFT decision = prev_action; break; default: printf("lab6 error: wrong IPD-agent code <pda_id> specified\n"); } return decision; } void pda_info (void) { // print IPD-agent parameters printf("\nIPD-agent code = %d", pda_model); switch (pda_model) { case 0: printf(" ALLC\n\n"); break; case 1: printf(" ALLD\n\n"); break; case 2: printf(" Predetermined dynamic"); printf("\n(%d) - %d, (%d) - %d\n\n", pda_action1, pda2[0], pda_action2, pda2[1]); break; case 3: printf(" Stochastic"); printf("\n(1) - %f, (2) - %f\n\n", pda3, 1 - pda3); break; case 4: printf(" Grim\n\n"); break; case 5: printf(" TFT\n\n"); break; default: printf("lab6 error: wrong IPD-agent code <pda_model> 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,"%f,%f,%f\n",prcW,pda_prcW,avr_prcW); } int maxQa (void) { int j; int mi; // index of maximum Qa mi=0; for (j=1; j<actNumber; j++) if (Qa[j] > Qa[mi]) mi = j; mi++; return mi; } // epsilon greedy RL int ag_epsilon_greedy (void) { int i; int ca = action - 1; // current action index float rand_num; if(t==0) { for(i=0; i<actNumber; i++) {Sa[i] = 1; ka[i] = 1; Qa[i] = 1;} action = randomChoice(actNumber); } else { Sa[ca] = Sa[ca] + W; ka[ca]++; Qa[ca] = (double)Sa[ca] / (double)ka[ca]; rand_num = (float)rand() / (float)RAND_MAX; if (rand_num < epsilon) action = randomChoice(actNumber); else action = maxQa(); } return action; } int main(int argc, char* argv[]) { char *a1, *a2; // init random-number generator srand((unsigned)time(NULL)); // random choice of environment model pda_model = randomChoice(5); // set parameters of chosen IPD-agent pda_init(pda_model); // open file for results res_open_file(); // main cycle of program (over game interactions) for (t=0; t < Time; t++) { prev_action = action; if (human == 1) { // get user move from console printf("make your move: "); scanf("%d",&action); } else action = ag_epsilon_greedy(); if (action == 1) a1 = "C"; else a1 = "D"; pda_action = pda_decision(pda_model); // get IPD-agent move if (pda_action == 1) a2 = "C"; else a2 = "D"; printf("(%s, %s) --> ",a1,a2); // output user and environment moves // PD payoff matrix: find who win in this iteration if ((action == 1) && (pda_action == 1)) { // C#1,C#2 -> R1,R2 W = R; sumW = sumW + R; prcW = (float)sumW / ((float)t + 1); pda_W = R; pda_sumW = pda_sumW + R; pda_prcW = (float)pda_sumW / ((float)t + 1); } if ((action == 1) && (pda_action == 2)) { // C#1,D#2 -> S1,T2 W = S; sumW = sumW + S; prcW = (float)sumW / ((float)t + 1); pda_W = T; pda_sumW = pda_sumW + T; pda_prcW = (float)pda_sumW / ((float)t + 1); } if ((action == 2) && (pda_action == 1)) { // D#1,C#2 -> T1,S2 W = T; sumW = sumW + T; prcW = (float)sumW / ((float)t + 1); pda_W = S; pda_sumW = pda_sumW + S; pda_prcW = (float)pda_sumW / ((float)t + 1); } if ((action == 2) && (pda_action == 2)) { // D#1,D#2 -> P1,P2 W = P; sumW = sumW + P; prcW = (float)sumW / ((float)t + 1); pda_W = P; pda_sumW = pda_sumW + P; pda_prcW = (float)pda_sumW / ((float)t + 1); } avr_sumW = ((float)sumW + (float)pda_sumW) / 2; avr_prcW = avr_sumW / ((float)t + 1); res_store_next_string(); // save current results in file // print current results printf("(%d,%d) | total: (%d,%d) | average: %f\n",W,pda_W,sumW,pda_sumW,avr_sumW); } // check total win if (sumW > pda_sumW) winer = 1; else winer = 0; // output game result if (winer == 1) printf("\n you win (number of moves = %d)\n",t); else printf("\n you lose (number of moves = %d)\n",t); pda_info(); // print information about environment res_close_file(); // close file with results return 0; } Результати Залежності середнього виграшу від часу для кожного із реалізованих в даній роботі агентів: Людина – IPD-агент –– ––– you win IPD-agent code = 0 ALLC you lose IPD-agent code = 1 ALLD you win IPD-agent code = 2 Predetermined dynamic (2) - 3, (1) - 5 you win IPD-agent code = 3 Stochastic (1) - 0.791833, (2) - 0.208167 you win IPD-agent code = 4 Grim you win IPD-agent code = 5 TFT Кількість кроків у кожній грі – 50. RL-агент – IPD-агент –– ––– you win IPD-agent code = 3 Stochastic (1) - 0.903134, (2) - 0.096866 you lose IPD-agent code = 4 Grim you win IPD-agent code = 5 TFT Сумарний результат гри з агентом "зуб за зуб" може відрізнятися лише на один виграш. В середньому виграш і програш RL-агента у грі з TFT-агентом рівноможливі. * Графік сірого кольору (––) – середнє значення середнього виграшу обох агентів. Кількість кроків у кожній грі – 50. Висновки: виконуючи дану лабораторну роботу я ознайомився з принципами співвідношення співпраці та суперництва в колективі агентів, досліджуючи модель колективної поведінки під назвою "дилема ув’язненого". У грі з IPD-агентами, що завжди співпрацюють (ALLС) та завжди протидіють (ALLD), найкращою поведінкою є "завжди протидіяти". Найкращий результат, якого можна досягнути у грі із ALLD-агентом – сумарний виграш у обох агентів рівний. RLагент (в даному випадку використано (-жадібний алгоритм) найгірший результат показує у грі із Grim ("невблаганним") IPD-агентом. Це пов’язано із тим, що Grimагент починає постійно протидіяти після першої протидії суперника (після чого не зважає на дії суперника), а RLагент в основному спирається на результати попередніх дій. У взаємодії із стохастичним IPD-агентом, RLагент у більшості випадків виграє, оскільки може дослідити імовірності вибору суперником відповідних дій.

Звіт про виконання лабораторної роботи Теорія колективної поведінки інтелектуальних систем

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись