Fórum: Algoritmusok

Sziasztok!

Gondoltam írok Pascal/Delphi példaprogramot. Kerestem a referenciában a C-s setvbufhoz hasonlót, de nem találtam. Egyébként a rendes S pontvrsenyben sem kellett sorokkal kiegészíteni a programot, csak betartani a formalitást. Nem elég ebben az esetben is csak az arénaprogramban állítani az ilyesmiket? Ja, és várom már Atosztól a pontos kiírást!

A képletig nekem is sikerült eljutnom már, de van itt olyan aki már talált is ezt kielégítő eloszlást? Még valami eszembe jutott: írtátok, hogy a programotok előbb az ideális mentén halad,aztán kicselezi, meg fordítva,stb. Ha megvan valakinek a keresett nemvesztő eloszlás akkor attól miért kéne eltérni? Ráadásul hogyan lehet azt kicselezni? Szóval ha valaki ki tudta számolni az eloszlást, akkor verhetetlen. És ha több valaki is kiszámolta, akkor körverseny esetén több holtversenyben első lesz, nem? Szóval én átfogalmaznám a versenyt: ki tudja az ideálishoz legközelebbi eloszlást kiszámolni valamivel aztán belesűríteni egy programba; vagy kitalálni valami cselt ennek hiányában mondjuk a másik megfigyelésével, stb. Mi a véleményetek?

Érdemben van amúgy már itt valakinek programja? Én 4 napja szinte mást se csinálok, valamiket már számoltam is, de még nem sikerült a tökéletes eloszlásra bukkannom. Ugye az az egyszerű képlet valójában egy 23751 ismeretlenes egyenlőtlenségrendszer...

a képlet helyesen:

(Helyesbítek: a leírtam (:D) képlet nem az optimális megoldásra igaz, hanem az összes nemvesztő megoldást adja.)

Egyébként pedig: a nemvesztő megoldások nem feltétlenül nemnyerőek. Többek között a csupa (25,0,0,0,0)-t is megverik. Vajon van a nemvesztőek közül legjobb?

1 pici időre félretettem a lustaságomat.

a kő-papír-atombombára igaz, amit sejtettem. nézzünk 2 eloszlást: (k₁,p₁,o₁,a₁) és (k₂,p₂,o₂,a₂), ahol nyilván k₁+p₁+o₁+a₁=k₂+p₂+o₂+a₂.

annak a feltétele, hogy a második eloszlás nem veszít: a₁k₂+a₁p₂+o₁a₂+p₁k₂+k₁o₂a₂k₁+a₂p₁+o₂a₂+p₂k₁+k₂o₁.

átrendezve: a₁(k₂+p₂-o₂)+o₁(a₂-k₂)+p₁(k₂-a₂)+k₁(o₂-a₂-p₂)0

a papírbecsomagolós hozzászólásomban szereplő feltételek mellett (a 2. játékosra) ez mindig éppen 0-t ad.

tehát ha olyan eloszlást találunk, hogy minden tárgyra igaz legyen, hogy az őt ütő tárgyak kiválasztási esélyének az összege nagyobb, mint azoké, amelyeket ő üt, akkor nem vesztő stratégiát kapunk.

a kiemelés módjából látszik (sorry, nincs türelmem értelmesen leírni), hogy ez a 25-ös (és minden ilyen) játékra is működik, vagyis ha a választási lehetőségeket gráfban képzeljük el, akkor az optimális megoldás (E):

, ahol a P_#-ek a gráf pontjai, E(P_x) pedig az x-edik pont kiválasztási esélye.

sorry, ha hiba van benne megint, nem ellenőrzöm, muszáj mennem.

Sziasztok!

Úgy látom, hogy függetlenül attól, hogy lehet-e eredményes stratégiát leprogramozni, vagy nem, sok fórumosnak birizgálja a játék a fantáziáját. Itt az ideje, lehet gondolkodni a nyerő stratégián... Lehet, hogy az 1000 kör tényleg kevés, hogy mérhető eltérést mutassanak a programok, felmehet az 10000-re is, ha egy-egy csata rövid ideig tart. (néhány mp, esetleg perc - több órás gigászi küzdelmeknek nincs értelme) A döntetlen határt is még finomíthatjuk, de a lényeg, hogy napokon belül kiírok egy időpontot, meg felteszek egy letölthető "versenykiírást" melynek minden proginak meg kell felelnie. Addig is jó gondolkodást, várom a véleményeket, Atosz!

nem egészen világos számomra, hogyan használod ki, főleg, ha csak 1000 kör áll rendelkezésre :-))

az enyém meg az első felében nem az ideális eloszlással játszana, majd amikor a tied megpróbál lecsapni, kijátszaná. :)

amúgy a standard random függvény nem igazán random, ezt ki lehetne használni.

Szia Béla,

Látom, sikerült használni az új jelszódat. :-) Csak azt nem értem, hogy mit kellene itt moderálni.

Szerintem ki lehetne figyelni, hogy az ellenfél milyen eloszlásban választ a lehetséges lépések közül, és ha nem az ideális eloszlásban, akkor időnként lecsapni. Persze nem mindig, mert az meg az ellenfél számára lenne túl feltűnő.

Mondjuk a játéknak az első felében az ideális eloszlás szerint lépnék, a játék második felében pedig hol az ideális eloszlás szerint, hol az ellenfélről készített statisztika alapján választanék.

(Uhh, ha még sokat foglalkozom ezzel, kedvem támad beprogramozni...)

Üdv.

Géza

:)

Sziasztok!

Úgy tudom, van egy tétel, ami (bizonyos feltételek mellett: véges sok játékos, véges sok tiszta stratégia, egyetlen szinkron választás, stb.) kimondja, hogy a kevert stratégiák terében már mindig létezik "nyeregpont", azaz minden játékos számára egy-egy olyan kevert stratégia, amitől semelyiküknek nem érdemes eltérnie. Sőt, nem történhet meg az a csúfság, hogy más egyensúlyi helyzetben más a játékosok sorsa (más várható nyeremény). [Géza, ha erre jársz, moderálj :-)]

Tehát, [miután az atombombás játék szimmetrikus a két játékosra] mindig lehet olyan egyszerű véletlenszerű választást (kevert stratégiát) csinálni, aminek minden más taktika ellen 0 a várható nyereménye.

Ha jól értem a 25-ös játékot, akkor ott is van véges sok választás (az összes számötös), tehát van nemvesztő (és persze nemnyerő) kevert stratégia. Igaz, sok számötös van, ezért nehéz lehet megtalálni egy egyensúlyit, de a nemvesztőhöz nagyon közeli taktika leprogramozhatósága is elbizonytalanító.

Ezért az ilyen egyszerű játékok közül szerintem nem annyira érdemes szinkron, véges, zérusösszegű, kétrésztvevős játékból programok közt bajnokságot kiírni. Persze ha legalább az egyik résztvevő ember, akkor annál izgalmasabb a téma, de ez már nem a matematika vagy a természettudomány asztala elsősorban.

Elképzeltem, ahogy a kő becsomagolja a papírt...

arena25 v07 source

Minden működik, esetleg kisebb szépítgetések / (szabály)módosítások vannak hátra.

szerintem ez a 25-ös játék nagyon hasonlít a kő-papír-ollóhoz.

persze van különbség: az egyes számötösök nem ugyanannyi számötöst ütnek. click

hogy melyik számötös melyiket üti, szerintem gráfként érdemes elképzelni.

ha a kő-papír-ollóban az egyik játékos véletlenszerűen játszik, akkor az hosszú távon verhetetlen (a döntetlen a legjobb, amit el lehet érni ellene).

a 25-ös játékban is: ha az egyik játékos véletlenszerűen választ (olyan adatot használ fel, amit a másik progi soha nem tud meg: pl. idő, CPU lepörgött órajelek száma "random seek"-ként) a 23751 lehetőség közül, akkor hosszú távon a végeredmény csak a másik játékos választásainak az eloszlásától függ.

vajon létezik olyan eloszlás, ami verhetetlen?

először nézzünk egy egyszerűbb játékot, ami hasonlít a 25-öshöz: a kő-papír-olló-atombomba :) játékot.

ebben a játékban:

- a kő becsomagolja a papírt

- a kő szétveri az ollót

- az atombomba felrobbantja a követ

- az atombomba szétégeti a papírt

- az olló elvágja az atombomba gyújtózsinórját

(a többi eset döntetlen, azaz a papír túl vastag, hogy az olló el tudja vágni)

ha itt is minden esetet ugyanakkora eséllyel választunk ki (), akkor ha az ellenfél mindig atombombát mond, akkor vesztünk (mert mi , ő pedig eséllyel nyer).

gyártsunk olyan eloszlást, amit nem lehet megverni csupa egyforma választással!

csupa ollóval: ka; csupa atombombával: ok+p; csupa papírral: ak; csupa kővel: p+ao

azaz: p+a=o és a=k

ezekszerint például a () esélyekkel véletlenszerűen választó programot nem lehet megverni csupa egyforma választással.

úgy néz ki, hogy egyéb eloszlással sem lehet megverni (egy programmal 1 percig próbálgattattam véletlenszerű eloszlásokat), de még nem sikerült belátnom. pedig ha így van, akkor ugyanígy a 25-ös játékra is lehet verhetetlen eloszlást készíteni. ugye?

Találtam benne hibát, úgyhogy átírtam még ezt-azt, és feltöltöttem újra.

arena25 v06 source

most veszem csak észre, hogy nem is írtam annyira más témáról. :)

Már egész használható, bár néhány dolog még hiányzik: arena25 v04 source

Tetszik nekem ez az arénás játék, remélem másnak is, és lehet tényleg verseny. De gondolkodtam valamin: millió és egy féle módon lehet algoritmizálni a számokat (ráadásul szerintem véletlen beépítésére is szükség van). Ha úgy írom meg a programom, hogy mindig változtatja magát a másik számínak függvényében, ami pedig szintén változtatja magát folyamatosan az enyémek miatt, akkor kiismerhetetlen lesz mindkettő. És miért ne így írnám meg? Minden lépésben választ a belekódolt mondjuk 10 féle variáció 10000 paraméterezési lehetőségéből 1-1-et, és írja a számokat, de ezt hogy lehet megfejteni? Ráadásul én az 1000 játszmát kevésnek találom. Ennyi idő alatt gyakorlatilag véletlenszerű lesz, hogy ki nyer, és 50-en belül meg döntetlen. Szóval nagyon bejön ez a játék, és sokat gondolkodtam rajta, de 1000 kör alatt szerintem nem lehet ésszerűen összehozni nyerő programot csak szerencsével.

sorry, de most egy kicsit más témáról írok.

ezentúl ha számot mondok, természetes számot értek alatta.

világos, hogy bármilyen megfogalmazható, leírható adat "belesűríthető" egy számba (akár több szám is) (Gödel-számozás). a szám-szám függvények bizonyíthatóan (átlós módszer) nem rendelhetők hozzá a számokhoz, azonban egy részhalmazuk igen: programnyelvvel (vagy Turing-géppel, ahogy tetszik). egy szám-szám függvényhez rendelt szám maga a programkód.

ezeknek a függvényeknek részhalmaza a véges idő alatt kiértékelhető függvények halmaza. létezik olyan nyelv, amivel csak véges idő alatt kiértékelhető függvények írhatók le, de azok közül nagyon sok (vagy az összes? ezt nem tudom, de gyanítom, hogy nem). ilyen nyelv pl. a számítási utasítások mellett csak előre meghatározott maximális ismétlésszámú ciklust megengedő nyelv.

mivel a programkódokhoz számokat lehet rendelni és fordítva is, ezért a programokat (vagyis a szám-szám függvényeknek ezt a speciális részhalmazát) el lehet képzelni a számegyenesen.

számítógépre lehet olyan szoftvert írni, amely bármely programot elegendő számú input-output példa alapján meg tud találni.

ez úgy működik, hogy én előre gondolok egy ilyen programkódra (szám-szám függvényre), és megadok néhány változó-függvényérték (input-output) párost a gépnek. a gép a függvények számegyenesén 0-tól indulva meg tudja keresni, hogy melyik az első programkód, ami illik az összes megadott példapárra. ha az így megtalált program nem ekvivalens az enyémmel, akkor létezik olyan input, amelyre nem azonos az outputja az én programommal. ha erre az inputra is kap példát, akkor muszáj újból elindulnia a számegyenesen. mivel értelemszerűen balra nem találhat megoldást, jobbra kell keresnie. tehát ha ezt a műveletet elégszer elvégzem, akkor a gépnek előbb-utóbb muszáj megtalálnia azt a programkódot, amire én gondoltam.

egy ilyen szoftver szerintem nagyon hasznos lehet, mivel egy véges idő alatt kiértékelhető programokat generáló programnyelvvel nagyon sok mindent le lehet írni. gondoljatok csak bele: be lehet adni a szoftvernek bemenetnek, hogy honnan és mekkora sebességgel dobtuk a labdát, kimenetnek meg hogy hova esett. mondjuk 10000 különféle esetben, és a 10001-edik outputot már meg fogja tudni jósolni, mielőtt eldobtuk volna a labdát.

mit gondoltok?

tudom, mi a legnagyobb baja ennek a módszernek: K**VA LASSÚ. valami olyasmi gyorsítást lehetne belevinni, ami képes kizárogatni függvényeket. vagy egy másik ötlet: azokat a függvényeket, amikre "rájött", belevenné a nyelvbe alapműveletnek, és így lehetne fokozatosan tanítani.

Mégis jó a setvbuf(stdout,0,_IOLBF,0); is.

Elírás, helyesen: setvbuf(stdout,0,_IOLBF,80);

Hali!

Több referenciában is megnéztem, mindenhol azt írják, hogy a szabványos kimenet (stdout) csak akkor vált sorosan (vagy egyáltalán nem) bufferelt módba, ha a fájlleíró tábla megfelelő (szám szerint 1-es) bejegyzésében speciális, terminálra (tty) vonatkozó bejegyzést talál. Tehát ha át van írányítva (fájlba vagy csőbe), akkor teljesen (blokkosan) bufferelt módba vált. Eddig nem találtam megoldást, - és félek, hogy nincs is - amellyel az aréna "átverhetné" az induló program szabványos csatornákat létrehozó mechanizmusát, hogy terminálnak "lássa" a pipe végét.

A jó hír az, hogy C/C++ progikban csak egyetlen sor (setvbuf(stdout,0,_IOLBF,0);) hozzáadása szükséges (a program elejére) a soronkénti bufferelés beállításához. Pascalról/Delphiről egyelőre nem tudok nyilatkozni, ha valaki esetleg találkozott már ezzel a kérdéssel, legyen szíves, írjon! :)

Mostantól előre láthatólag 3 napig nem leszek gépközelben.

ui: mailt megkaptam, köszi (Atosz)

Szia!

Örülök, hogy sikeredik - biztos vagyok benne, hogy hamarosan összejön. Addig is szeretnék mindenkit a [15]-ös hozzászólásban írt játékra invitálni. Részletek később...

Minden jót, Atosz!

ui: küldtem egy emilt (2501)

Reggel óta sikerült összehoznom egy hibrid megoldást. Az a lényege, hogy az aréna indítja el (fork+exec) a soron következő két progit (illetve egyelőre még csak egyet, a hibakeresés miatt), és mindkettő szabványos be- és kimenetét átirányítja az általa létrehozott pipeokba. (Azért választottam ezt a módszert, mert ez win alatt is járható út.) Tehát tudja írni-olvasni a progik szabványos be- és kimenetét. A "lépések" formátuma a következő: 5 darab szám szóközök, tabok és újsorok bármilyen kombinációjával elválasztva. Az utolsó szám után kötelező lennie valahol egy újsornak, ugyanis a szabványos be- és kimenet alapértelmezetten soronként bufferelt. Ezzel kapcsolatban botlottam bele az első nehézségbe: a próba progi, amit csináltam, valamiért (gondolom a szabványos csatornák átirányítása miatt) soronkéntiből blokkos bufferelési módba kerül (emiatt az aréna nem tudja olvasni a "lépéseit"). Ha viszont minden sor után kényszerítem a buffer ürítését (fflush), vagy a program elején átállítom a kimenet bufferelési módját soronkéntire, minden rendben működik. Under construction.