Kispad

Kispad: közös blog
4230 cikk, 53894 hozzászólás
Szerzők | Tudnivalók | Feedek


Kőpapírollógia

stsmork cikke a Torokgeek rovatból, 2005. január 28. péntek, 14:58 | 38 hozzászólás

A sesblog szerkesztőségének kétharmadát nem hagyta nyugodni ses KPO-stratégiai postja és elhatározta, hogy utánajár a dolognak. Rittyentettek is egy Perl scriptet, aminek segítségével szimulálni lehet a játékosok viselkedését. ("Ó, hogy egyesek mennyire ráérnek!" - sóhajt most egynémely olvasó...) A következőkben illusztrált beszámoló következik a világ (tudtunk szerint) legelső kőpapírollóstratégia-bajnokságáról. Vigyázat, tömény!

Első körben három kézenfekvő algoritmust eresztettünk össze, az egyik - "Same" - minden körben ugyanazt lépi (az első lépést tetszőlegesen választja), a másik - "Cycle" - szabályosan körbejár a három lehetséges lépésen (kő-papír-olló-kő-papír-olló-kő...) a harmadik pedig -"Random" - véletlenszerűen lép. Egy-egy játszma során mindenki játszott mindenkivel, a véletlen okozta eltérések kiegyenlítése végett tízezer játszmát futtattunk. Íme az összesített eredmények:

Score Random Same Cycle
Random 6685 --- 3358/3345 3327/3219
Same 6678 3345/3358 --- 3333/3333
Cycle 6552 3219/3327 3333/3333 ---

(Értelemszerűen egy pontot szerzett egy játékos, ha megnyert egy játszmát, döntetlen esetén senki nem kap pontot. A "/" jel előtt álló szám az adott sorban levő játékos pontjait jelenti, a mögötte álló pedig az adott oszlopban szereplőét. Az első oszlopban a fordulók során gyűjtött összesített pontszám szerepel, ez alapján rangsoroltunk.)

Ezután bedobtunk még egy játékost - "Random unique" - , aki szintén random játszik, de ügyel rá, hogy soha ne lépje egymás után kétszer ugyanazt. (Ennek a későbbiekben lesz jelentősége.)

Score Random Same Random unique Cycle
Random 10058 --- 3380/3356 3338/3364 3340/3294
Same 9996 3356/3380 --- 3307/3342 3333/3334
Random unique 9993 3364/3338 3342/3307 --- 3287/3339
Cycle 9967 3294/3340 3334/3333 3339/3287 ---

Az eredmények mindkét esetben ugyanazt mutatják: ha már ész nélkül játszunk, akkor nagyjából mindegy, hogy azt milyen elv szerint csináljuk. A következő menetben három új játékost dobunk be a ringbe, mindhárman valamilyen okosságot alkalmaznak, hogy az ellenfelet leigázzák.

  • A "Follow" algoritmus azt lépi, amit az ellenfél lépett az előző körben. (Kivéve az első lépést: azt véletlenszerűen generálja.)
  • A "Remember last" algoritmus megnézi, hogy az ellenfél mit lépett az előző körben, feltételezi, hogy most is ezt fogja lépni, és ennek megfelelő intézkedéseket hoz.
  • A "Predict" statisztikát készít az ellenfél valamennyi korábbi lépéséről és feltételezi, hogy a következő körben is azt fogja lépni, mint amit eddig a leggyakrabban lépett. Eredmények:
Score Remember last Predict Random unique Random Cycle Same Follow
Remember last 29127 --- 7500/2500 0/5003 3344/3345 3284/3316 9999/1 5000/0
Predict 24392 2500/7500 --- 3253/3391 3323/3346 3315/3343 10000/0 2001/0
Random unique 21847 5003/0 3391/3253 --- 3338/3393 3360/3334 3392/3315 3363/3330
Random 20085 3345/3344 3346/3323 3393/3338 --- 3286/3333 3351/3317 3364/3270
Cycle 20027 3316/3284 3343/3315 3334/3360 3333/3286 --- 3333/3334 3368/3264
Same 13323 1/9999 0/10000 3315/3392 3317/3351 3334/3333 --- 3356/3379
Follow 13243 0/5000 0/2001 3330/3363 3270/3364 3264/3368 3379/3356 ---

A remember last algoritmus magasan vezeti a mezőnyt, de ezt csak annak köszönheti, hogy az alkalmazott módszere gyakorlatilag az összes pontot begyűjti a same, és értelemszerűen a fele pontot a follow játékosoktól. Érdemes megfigyelni, hogy ugyanakkor a random játékossal például egyáltalán nem boldogul.

A predict sokkal kiegyensúlyozottabb, nem véletlen hogy ő a második helyezett.

A remember last nyilvánvaló előnye arra késztetett minket, hogy aljas tervet dolgozzunk ki ellene. Az "Analyze" algoritmus elemzi az utolsó tíz kört és ha észreveszi, hogy az ellenfél remember last algoritmust játszik, akkor direkt keresztbe tesz neki. Minden más esetben maga is remember last stratégia szerint játszik. Íme:

Score Analyze Predict Random unique Remember last Cycle Random Follow Same
Analyze 32453 --- 7497/2501 5/4978 9995/2 3344/3274 3235/3409 5000/1 3377/3333
Predict 26996 2501/7497 --- 3336/3313 2500/7500 3324/3362 3335/3278 2000/0 10000/0
Random unique 26570 4978/5 3313/3336 --- 4956/0 3386/3320 3367/3307 3291/3295 3279/3344
Remember last 24249 2/9995 7500/2500 0/4956 --- 3357/3323 3391/3308 0/10000 9999/1
Cycle 23296 3274/3344 3362/3324 3320/3386 3323/3357 --- 3348/3318 3335/3314 3334/3333
Random 23266 3409/3235 3278/3335 3307/3367 3308/3391 3318/3348 --- 3310/3332 3336/3348
Follow 23203 1/5000 0/2000 3295/3291 10000/0 3314/3335 3332/3310 --- 3261/3416
Same 16775 3333/3377 0/10000 3344/3279 1/9999 3333/3334 3348/3336 3416/3261 ---

Úgy néz ki, működik! Érdekes, hogy a random unique játékos feljött a második helyre: ennek az lehet az oka, hogy soha nem lépi kétszer egymásután ugyanazt, így a remember last nem tudja leverni. Mivel az a gyanúnk, hogy ezek az algoritmusok igazából csak azért gyűjtenek ilyen sok pontot, mert mélyen lealázzák a véletlenszerűen játszó játékosokat, most kísérletképpen egymással eresztjük őket össze:

Score Analyze Remember last Follow Predict
Analyze 17493 --- 9994/4 4/9995 7495/2501
Remember last 12504 4/9994 --- 5000/0 7500/2500
Follow 9998 9995/4 0/5000 --- 3/2000
Predict 7001 2501/7495 2500/7500 2000/3 ---

Az analyze továbbra is töretlenül vezet, hála a remember last ellenes stratégiának - egyedül a follow veri tönkre, de ő meg máshonnan nem tudott pontot szerezni. Ez a tönkreverés érdekes, mivel a follow csúnyán kikapott az előző mezőnyben az analyze-tól. Ha belegondolunk, logikus, hogy az első fordulókban dől el a lehetséges tízezer pont sorsa ennél a két játékosnál.

Mi tehát az optimális stratégia? Tudnunk kell, hogy miszerint játszik az ellenfél, és nekünk az alapján kell lépnünk. (Erre mondjuk számítógépes szimuláció nélkül is rá lehet jönni, sőt.) A kérdés csak az, hogy honnan tudjuk, milyen stratégia szerint játszik? Talán kérdezzük meg tőle? Másrészt, ha stratégia nélkül, véletlenszerűen lépeget, akkor igazából nem sokat tehetünk ellene. (Annyit tegyünk még hozzá, hogy az ember fejében nincs véletlenszám-generátor, úgyhogy ezt a stratégiát a gyakorlatban tök nehéz kivitelezni.)

Ha úgy gondoljátok, tudtok az Analyze-nál jobb algoritmust, ami helytáll a mezőny többi tagja ellen is, szóljatok bele!

UPDATE: Ezennel versenyt is hirdetnénk a legjobb játékos megalkotására! Töltsétek le a Perl futtató környezetet, benne a mintajátékosokkal, és február 28-a éjfélig küldjétek el a saját versenyzőtöket egy darab PM modul formájában. Március elején összeeresztjük a beérkezett anyagokat (más nem fog indulni, így lehet nyugodtan próbálkozni a fenti mintajátékosok egyikével is), és meglátjuk, ki hogy áll kő papír ollóban.

UPDATE2: Fenti kiírásunk sajnos komoly méretű érdeklődési hiányba fulladt, de a téma feldolgozásért kiáltott: most a Microsoft Magyarország szervezésében újra lehet nevezni egész október elejéig. Hajrá!

» Ugorj a hozzászóló ablakhoz

Megosztások Facebookon

Eddigi hozzászólások (38)

1

Balage, 2005. január 28. péntek, 16:38 (#)

Hát, le a kalappal! Ezt szépen összehoztátok! :-) Nagy izgalommal bogarásztuk át a történteteket, mi is próbáltuk kitalálni, mi miért történt, és hát voltak nagy rácsodálkozások, meg nagy röhögések. Lehet, hogy indulunk... ;-)

2

map, 2005. január 28. péntek, 16:47 (#)

Szép összeállítás. Hallottam már hasonlóan agyafúrt meccsekről Mérő László valamelyik könyvében, és bár kicsit más szabályok voltak, mégis hasonló következtetésre jutottak. Mindent egybevéve a "Tit for Tat" algoritmus nyert, azaz megfigyeled az ellenfél előző lépéseit és ugyanazt nyomod, mint ő.

3

Madsen, 2005. január 28. péntek, 17:03 (#)

de kurvára ráértek :-)) de azért killer

4

ses, 2005. január 28. péntek, 17:08 (#)

Szvsz az analógia (2) nem áll, mert ott egyrészt csak két variáció volt, másrészt együttműködés esetén mindenki nyert.

5

eszpee, 2005. január 28. péntek, 17:09 (#)

Ráadásul az nem kő-papír-olló, hanem fogolydilemma volt.

6

ses, 2005. január 28. péntek, 17:12 (#)

Igen, ezért volt két variáció. Eh... :)

7

akakij, 2005. január 28. péntek, 18:01 (#)

Nagyon jo. Csak a nevezett modulokat eresztitek ossze, vagy az emlitettek biztosan benne lesznek az arenaban?
Azert kerdezem, mert felteszem, hogy senki nem lesz olyan hulye, hogy egy Follow-val nevezzen, de ha megis ott van, akkor lehet szamolni vele, hogy tole is lenyuljak nehany pontot.

8

akakij, 2005. január 28. péntek, 18:03 (#)

Jo. kozben megtanultam olvasni. :) Ignore me!

9

Ali, 2005. január 28. péntek, 19:14 (#)

Nekem is rögtön Mérő László ugrott be, ahogy a postot olvastam. Javasolnám is, hogy haladó hagyományt teremtődjék, minden hónapban (vagy kapacitáshiány esetén kéthavonta) hirdettessék meg a Sesblog Mérő László kupája egymás ellen eresztett olvasói algoritmusok formájában.

Nyilván akkor nekem is be kellene küldeni egy algoritmust, de bevallom, hogy a perl-t valahogy mindig elkerültem, bár bash, m4 területen elhagyta pár tíz kilobyte a terminálomat...

Viszont olyan szívesen olvasnék egyszer egy könyvet, amiben kevés a rizsa és sok az ehhez hasonlóan felépített cikk + a forráskód is ott van, nekem ti. ez a leghatékonyabb befogadási módom: egyszerű példa, kicsit bonyolultabb, még egy kicsit, aztán már csak értem a lényeget is, még ha a végén az elméletet össze is foglalják, azt legfeljebb átugrom. :)

10

atya, 2005. január 28. péntek, 22:43 (#)

Én speciel szeretem a Perl nyelvet, de annak, aki nem szereti, kellene csinálni egy TCP-n keresztül elérhető felületet, és akkor tetszőleges nyelven és platformon lehetne fejleszteni a kőpapír-ollé! játékosokat. És akkor azon a felületen lehetne később másfajta megmérettetéseket is csinálni, és tényleg lehetne belőle egy rendszeres agyedzés :)

11

stsmork, 2005. január 29. szombat, 04:41 (#)

Atya, igazad van - de mit csináljunk azokkal, akik a TCP/IP-t sem szeretik? ;-)

12

gz, 2005. január 29. szombat, 05:38 (#)

sracok, nem rontottatok el vmit? same vs. follow-nak 0/0 koruli eredmenyt kellene adnia, nem? egyebkent nincs tul sok ertelme ilyen szinten foglalkozni a temaval, hiszen az igazi (tehat nem pszeudo) random-ot semmilyen algoritmus nem fogja megverni. annak lenne esetleg ertelme, hogy az algoritmus ember ellen jatszon.

13

gz, 2005. január 29. szombat, 05:40 (#)

ja, es egyebkent sziasztok, meg nem talalkoztunk :)

14

.dot, 2005. január 29. szombat, 15:36 (#)

egyebkent telleg ki kene probalni egy teljesen random algoritmust egy-egyben jatszatni barmelyik ellen. valamiert nekem is ugy tunik, hogy az igazi random algoritmus dontetlent jatszik barmi ellen. (random ellen milyen algoritmust lehet irni?)
emberek ellen lehet strategiat gyartani, mert ahogy ti is irtatok a cikkben, az ember fejeben nincs veletleszam generator.

15

blumi, 2005. január 29. szombat, 16:15 (#)

Ez marhaság, már bocs, az algoritmusnak nem a random ellen kell győznie, hanem a bajnokságban, azaz körmérkőzések vannak, és mint látható, a random az középmezőny (nem eszít, de nem is nyer).

16

.dot, 2005. január 29. szombat, 16:25 (#)

ezt ertem blumi, en csak azt mondom, hogy nem lesz olyan algoritmus, amelyik a randomot le tudna nyomni. (hanem olyanok lesznek, amelyek arra hajaznak, hogy a tobbi gyenge pontjain pontot szerezzenek)

17

.dot, 2005. január 29. szombat, 16:31 (#)

tehat ha tfh a versenybe egy ember kivetelevel mindenki random jatszana, akkor a maradek egy szamolgathatna napestig, nem jutna elore.

18

.dot, 2005. január 29. szombat, 17:00 (#)

oke, vegigolvastam megegyszer a cikket, nem szoltam :-)))

19

gz, 2005. január 29. szombat, 17:22 (#)

ok, ha mindenkeppen a gyozelem a cel, akkor fel kell tennunk, hogy van legalabb egy ellenfel, aki nem a random-ot hasznalja (legyen o 'NR'). ki kell ismernunk NR mukodesi elvet, es ezek utan tudunk nyerni. tehat az MI teruleten jarunk. egyebkent akit erdekel az ilyen, az latogasson el ide: http://atlantis.cyty.com/robocom/
annyival kulonbozik ez a kpo-tol, hogy nem ismert garantaltan dontetlenre vezeto algoritmus, meg kicsit bonyolultabb. jaes, magyarazzal el vki lecci, hogy a same vs. follow miert nem 0/0!

20

blumi, 2005. január 29. szombat, 19:07 (#)

dot: ha akár csak egyetlenegy versenyző van (rajtunk kívül), aki nem véletlenszerűen játszik, már akkor meg lehet nyerni a körmérkőzést a jobb algoritmussal.

21

.dot, 2005. január 29. szombat, 19:52 (#)

azt hiszem megvan a megoldas. ki kell fejleszteni egy olyan algoritmust, amelyik a szerencsen alapszik. azaz jatszatunk egymas ellen ket randomot es amelyik nyer, az jut tovabb. ezt persze tobb szazezerrel meg kell csinalni kieseses rendszerben. amelyik legutoljara marad, az mar hihetetlenul szerencses, igy aztan megver bakit! :-)))

22

.dot, 2005. január 29. szombat, 20:13 (#)

jo, de en a randomot a biztosan nem legyozhetore hoztam fel peldanak (majd utana elolvastam megegyszer, hogy mirol van szo). errol tenyleg csak annyit tudni, hogy soha nem lesz utolso, de soha nem lesz elso se. (ha van legalabb meg ket jatekos eltero strategiaval).

23

gino, 2005. január 29. szombat, 21:38 (#)

ez a same vs. follow problematika engem is érdekel! max az elsőben nyerhet az egyik, a többi utána végig döntetlen - elvileg.

hogyisvanez? teccikérteni?

24

Blogadmin, 2005. január 30. vasárnap, 18:36 (#)

Respekt, jópofa.

25

vlajos, 2005. január 31. hétfő, 09:31 (#)

Azert valami komolyabb algorimust is kiprobalhatnatok.
Neuron hálózat és/vagy megerõsítéses tanulás alapuak valoszinuleg egesz jol belerazodnanak az ellenfel stategiajaba.
(google://reinforcement learning, neural networks)

26

pblue, 2005. február 5. szombat, 14:37 (#)

dehát csak szót csépeltek itt ahelyett, hogy a kiírásnak megfelelően írnátok a felsorakoztatott remek ötleteknek megfelelően a jobbnal jobb algoritmusokat a versenyre. jó, igaz, a perltől engem is kiráz a hideg így első ránézésre...

27

jsaak, 2005. február 5. szombat, 14:58 (#)

Ha megoldható az, hogy a perl shellt hív, akkor lehet összedobok egy mindentverő algoritmust. De mielőtt belevágnék valaki aki ért hozzá biztosítson afelől, hogy menni fog ez így!

28

eszpee, 2005. február 20. vasárnap, 13:24 (#)

Figyelem, a letölthető rendszer egy új változata került ki a lapra, az előzőben volt egy kis bug. További jó fejlesztést!

29

pblue, 2005. február 23. szerda, 13:29 (#)

így is van egy hiba az analyze.pm-ben (hiányzik a GetLastArrayItem() hivások elől a $self->) de apróság, gondolom mindenki észreveszi, csak a rend kedvéért szóltam

30

eszpee, 2005. augusztus 24. szerda, 15:10 (#)

Üdvözöljük a Microsoft Magyarország olvasóit! :)

http://weblabor.hu/hirek/20050824/kopapirollo

31

Ali, 2005. augusztus 24. szerda, 16:07 (#)

Jellemző...

32

Ali, 2005. augusztus 24. szerda, 16:10 (#)

...azért majd szóljatok, ha a Pentagon is ide hivatkozik! :)

33

agysejt, 2005. augusztus 25. csütörtök, 00:44 (#)

Gratula, jó kis tanulmány! :-)

Megsúgnátok nekem minden ambvivalencia nélkül, hogy miért kellett 10000-szer lefuttatni azokat a párosításokat is melyekben egyik játékos sem volt véletlenszerű???? :-))) LOL

34

gaba, 2005. augusztus 25. csütörtök, 14:05 (#)

Linkeljük be azért a Microsoft-kihívás hivatalos oldalát is: http://www.devportal.hu/kodparbaj/

35

eszpee, 2005. augusztus 25. csütörtök, 14:14 (#)

Ott van a post végén, update-eltem tegnap :)

36

gaba, 2005. augusztus 25. csütörtök, 19:07 (#)

jaj, de figyelmetlen vagyok, bocsánat.

37

moszi, 2005. augusztus 26. péntek, 23:06 (#)

gyerekek a same/follow-t elszurtatok. valamelyik algoritmus ott nem jo... es a "az a gyanúnk, hogy ezek az algoritmusok igazából csak azért gyűjtenek ilyen sok pontot, mert mélyen lealázzák a véletlenszerűen játszó játékosokat" mondat sem teljesen helyenvalo, mivel a random alazza a tobbit :p:p ...

amugy keszitettem egy jo par algoritmust, (szamszeruleg 14-et...) ami elemezget egy par dolgot, es belekever random-ot is, viszont a szimpla random jatekost nem tudtam sehogysem lenyomni ... "tul" randomul jatszik :D

38

Ollókezű Edward, 2005. augusztus 31. szerda, 11:30 (#)

Úgy látom nekem nem sok esélyem lenne.

Ollókezű Edward


Hozzászólsz?

Igen

Hozzászólást csak névvel együtt fogadunk el. Ha linket írsz be, akkor előtte és utána hagyj egy szóközt, főleg akkor, ha zárójelbe teszed.


Az oldal tetejére | Szerzők, tudnivalók, feedek | sesblog és Kispad © 2003-2010 ervin, eszpee, stsmork