2. Táblás játékok *

3. A halma játék elkészítése JAVA nyelven *

4. Mellékletek *

1. Bevezetés a játékelméletbe

1. Ismertető

Az ismertetésre kerülő módszer neve játékelmélet. Akinek sok ideje van, az a stratégiajátékok elmélete elnevezést is használhatja. Aki először találkozik ezzel a valószínűtlenül hosszú elnevezéssel, feltehetően megkérdezi, hogy: Miért? Válaszunk a következő: az elnevezés onnan ered, hogy a stratégia elméletének alapja a játékok vizsgálata. A válasz valójában nem kielégítő, újra feltehetjük a kérdést:

Miért? Azért, mert a játékokban megtalálhatók a különféle konfliktusok főbb elemei, leírásuk és tanulmányozásuk viszonylag egyszerű. ( A “játék” szó használata az elmélet szempontjából nem lényeges. Szerepe csak annyi, hogy az összes vizsgált konfliktust ezzel a névvel illetjük.)

Ennek alátámasztására gondoljuk végig, hogy mi a közös mondjuk a póker játékban és egy háborús konfliktusban. A póker játékban a játékosok egy bizonyos jutalmazási rendszer szerint játszanak. A játékosok érdeke nyilván ellentétes: mindegyikük nyerni szeretne, de ha az egyik nyer, akkor mások szükségképpen veszítenek. Ez a konfliktus alapja. Az egyik játékos szemszögéből nézve vannak olyan elemei a játéknak, amelyek teljesen az ő ellenőrzése alatt állanak. Ilyen például az, hogy kiválaszthatja, kikkel óhajt játszani. Ez azonban a többi játékosra is igaz. Vannak tehát a játéknak olyan elemei, amelyek ellenőrzése teljesen az ellenfél kezében van. Végül vannak olyan elemek, amelyek ( ha a szabályokat betartják ) egyik játékos ellenőrzése alatt sincsenek.

Ilyen például a lapok sorrendje. Felfoghatjuk úgy, hogy ezek az elemek a Természet nevű hosszú életű, erős személyiség ellenőrzése alatt állnak. A Természet tudatosan nem rosszindulatú, de pajkos könnyedséggel fogja fel a saját komoly érdekeit. A leírt szempontok bizonyosan megtalálhatók minden konfliktusban.

Fontos jellemvonás a mindenkori információ ( katonai nyelven hírszerzési anyag ) szerepe. Az információ gyakran nem teljes és ezért kényelmetlen tényező. Nem tudhatjuk például, hogy ellenfelünk kezében milyen lapok vannak. Blöff is elképzelhető. Más hasonlatosságok is vannak ( előfordulhat, hogy valaki gyilkosság áldozata lesz J )

Az analógiát azonban nem vihetjük túl messzire. A póker játék sok mindenben nem tükrözi a hadviselést. A háborúban egy tank legyőzhet két tankot, a pókerben viszont a kártyalapok leterítésénél egy pár bubi mindig jobb, mint egy ász. Módosíthatjuk persze a póker játékot úgy, hogy jobban hasonlítson a tankok csatájához. Felállíthatunk olyan szabályt, hogy egy ász rosszabb ugyan akármelyik párnál, de ha a játék közben telefonál valakinek a felesége, akkor a két bubinál jobb. Ennek azonban nem volna különösebb értelme, ugyanis a játékok vizsgálata a stratégia tanulmányozásának éppen ezért jó kiindulópontja, mert a játékok a háborús konfliktusok és az egyéb jelenségek bonyolult helyzeteinek összességét nem tartalmazzák. Az elméletek, fejlődésük korai szakaszában nem képesek arra, hogy a jelenségek vizsgálatánál az összes közrejátszó tényezőt figyelembe vegyék.

Az eddigiek alapján talán világos, hogy a játékok tartalmazhatnak olyan alapelemeket, amelyek majdnem minden érdekes konfliktusban megtalálhatók. Következik-e ebből, hogy hasznos dolog tanulmányainkat játékok vizsgálatával kezdeni? Nem szükségképpen. Elképzelhető az is, hogy a háborús-, gazdasági- és társadalmi helyzetek felépítése annyira bonyolult, hogy nem közelíthetők meg a játékok fogalmából kiindulva. Ezt a lehetőséget azért kell vizsgálnunk, mert a játékelmélet jelenlegi formájában még a valódi játékok mindegyikének leírására sem képes, sőt, kénytelenek vagyunk nagyon egyszerű valódi játékok és a bonyolultabb játékok ( például a póker ) leegyszerűsített változatainak vizsgálatára szorítkozni.

Ilyen körülmények között nevetségesnek tűnhet, hogy valaki számottevő energiát fordít a játékelmélet tanulmányozására és fejlesztésére, sőt azt várja, hogy mások is érdeklődjenek a tárgy iránt. Ennek okát részben abban találhatjuk meg, hogy a játékelmélet eddigi sikerei reménnyel és a tárgy iránti hűséggel töltötték el az elmélettel foglalkozó tudósokat. A szándékosan túlságosan leegyszerűsített elméletek kitalálása a tudományok egyik fontos módszere, amelyet különösen az “egzakt” tudományok terén alkalmaznak sokszor. Ha a biofizikusok eredményesen használhatják a sejt, a csillagászok pedig a világegyetem leegyszerűsített modelljét, akkor mi is remélhetjük, hogy a leegyszerűsített játékokat nagyon jól alkalmazhatjuk bonyolultabb konfliktusok modelljeiként.

Nyilvánvaló, hogy az ilyen elméletek körében a halandóság nagyobb, mint amekkorát egy katonai szervezet eltűrhet saját megmozdulásai során. Az elmélet sikerei nyilván nem örökéletűek. A legtöbb, amit tőle várhatunk az, hogy napjainkban bizonyos meghatározott célokra sikeresen alkalmazhatjuk.

2. Egy történelmi példa

Vizsgáljuk meg egy példán, hogy mit várhatunk a sikeres tudományos absztrakcióktól. Olyan elméletet választunk, amely biztosan a valóság nagyon leegyszerűsített modelljét vizsgálja.

Tegyük fel, hogy a Naprendszer bolygóinak mozgását akarjuk tanulmányozni. Tekintsük az egyes bolygókat olyan pontoknak, amelyek tömege megegyezik a bolygókéval. Tegyük fel, hogy bármely két pont között olyan kölcsönös vonzóerő lép fel, amelyet úgy számíthatunk ki, hogy a két pont tömegének szorzatát elosztjuk távolságuk négyzetével, és ezt megszorozzuk egy állandó értékkel, továbbá minden egyéb körülménytől eltekintünk. Tételezzük fel még azt is, hogy az elmélet nem nyilvánvaló ostobaság, hiszen ha az volna, akkor el sem kezdenénk vizsgálni.

Valójában ez az elmélet, a gravitáció elmélete, két és fél évszázadon át megfelelő volt a bolygók mozgásának leírására. Az elmélet a Merkúr pályáját adta meg a legnagyobb hibával, a Merkúr ugyanis a várt helytől egy évszázad alatt a radián ötezred részével tért el. Az Einstein által javított elmélet már figyelembe veszi az ilyen hiányosságokat.

3. Összehasonlítás és tanulságok

A gravitáció elmélete természetesen nem annak az almának köszönheti megszületését, ami állítólag Newton fejére esett. A bolygók mozgásáról, nagyrészt Tycho Brahe munkásságának eredményeképpen, már korábban is sokat tudtak. Kepler felismerte a bolygók mozgásának néhány alapvető törvényét. Newton ezek felhasználásával és a matematika egy új ágának ( az analízisnek ) kidolgozásával talált rá a fenti absztrakcióra. Balszerencséjére éppen a Hold mozgásának vizsgálatával akarta kipróbálni az elméletét. A súlyosan hibás adatok miatt többévi munkája ment veszendőbe.

A példákból számos tanulságot szűrhetünk le. Egyrészt elképzelhető, hogy viszonylag bonyolult jelenségeket nagyon egyszerű elmélettel lehet magyarázni. Aki felteszi, hogy a bolygók mozgása ilyen egyszerű, az sosem vállalhat felelősséget jóslataiért. Másrészt tanulság az, hogy ha egy elmélet nagyon általános, akkor rendszerint a jelenségek széles körében eredményesen alkalmazható: a gravitáció elmélete például nemcsak a bolygók mozgására, hanem bármely, tömeggel rendelkező részecskére érvényes. A harmadik tanulság. az, hogy az elméletek gyakran nem tökéletesen, de néha ( például a fenti esetben ) szinte megtévesztő pontossággal írják le a valóságot. Újabb, nagyon fontos tanulság az, hogy az elmélet a testek mozgását meghatározó tényezők közül csak egyet ragad ki, ráadásul olyat, amelyik gyakran elhanyagolható. Például két, szorosan egymás mellett haladó repülőgép között a gravitációs erő körülbelül akkora, mint egy cigarettapapír súlya.

Tanulság az is, hogy lényeges adatok birtokában kell lennünk. Ilyen szempontból Newton jobb helyzetben volt, mint azok, akik a konfliktusok vizsgálatának területén szeretnének eredményeket elérni. Az adatok nagy részét olyan tényezők határozzák meg, mint a személyiség ( tehát az egyén fizikai, érzelmi beállítottsága, egészségi állapota, különféle képességei stb. ) és a társadalmi környezet. Az ilyen jelenségek tanulmányozása pedig nehéz feladatot ró a matematikusokra.

Újabb tanulság, vagy legalábbis sokatmondó megjegyzés az, hogy Newton csaknem egyidejűleg dolgozta ki a gravitáció elméletét és a matematika új ágát, az analízist, és az, hogy az analízis nélkül a gravitáció elmélete gyakorlatilag használhatatlan lett volna. Ezen túlmenően az analízis kétszázötven éve lényeges szerepet játszik a fizikában. Korai lenne még arról beszélni, hogy a játékelmélet is a matematika egy új ágának létrejöttét eredményezheti. A játékelmélet eddig nagyon kevés újat hozott, szinte mindent a matematika már kidolgozott ágaiból kölcsönzött. Lehetséges, sőt talán szükségszerű, hogy a módszer fejlődésével a későbbiekben új matematikai ág születik. Mindenesetre érdemes megjegyezni, hogy a játékelmélettel kapcsolatos első eredmények korunk egyik nagy matematikusának és sokoldalú gondolkodójának, Neumann Jánosnak köszönhetők.

Neumann játékelmélettel kapcsolatos első dolgozata 1928-ban jelent meg. Az első rész1etesebb mű azonban csak 1944-ben született: John von Neumann és Oskar Morgenstern: Theory of Gamcs and Economic Behavior (Princeton University Press, Princeton, N. J.). A mű hatásosságára jellemző, hogy néhányan, közöttük A. H. Copeland így értékelte: “Az utókor ezt a művet a huszadik század első felének legfontosabb tudományos eredményei közé fogja sorolni”. (Bulletin of the American Mathematical Society, 51. kötet. 1945. 498—504. old.)

A játékelmélet szellemében nagyon hasonlít a gravitáció elméletéhez, ugyanis mindkettő absztrakt modellből kiindulva közelíti meg a jelenségek széles körét. Az egyik elméletben az élőlények viselkedése meghatározott törvények szerint történik, hiszen a gravitáció elmélete lényegét tekintve pontosan megadja azt, hogy egy 12000 méter magasan, repülőgép, ejtőernyő és más eszköz nélkül tartózkodó pilóta hogyan fog mozogni. A játékelmélet pedig azzal foglalkozik, hogy bizonyos tervek esetében a lehetséges stratégiák közül kiválassza a legjobbat.

4. Elfogult megjegyzések a módszerről

Gyakran az embert körülvevő jelenségek borzasztóan bonyolultak ahhoz, hogy sikeresen elemezhessük őket. Az egyszerű elmélet megalkotásában ( egyszerűnek az olyan elméletet nevezzük, amelyben kevés axiómával és kevés szabállyal kell dolgozni és az egész többé-kevésbé kvantitatív ) segítséget nyújtottak az amatőrök, elsősorban a fizikatudósok

A játékelmélet tudósait szükségképpen az emberek közötti bonyolult konfliktusok valódi teljessége körüli tudatlanságuk hajtja előre, mivel ha nem olyan tudatlanok, akkor majdnem biztosan megpróbálják elméletileg vizsgálni a problémákat. Hűségük ( talán inkább vakmerőségük ) abból az ismeretükből ered, hogy ők és módszereik az élettelen világban rendkívül eredményesnek bizonyultak. Ezeknek a tanulmányozását sem úgy kezdték, hogy egyszerre vizsgálták a mikroszkopikus részleteket és a dolgok egészet. A részletek sokaságával és rendezésének bonyolultságával nem tudtak megbirkózni. Mivel azonban ezen a területen némi sikereket már elértek, gyanították, hogy ez a módszer a komplikált esetekben sem mond csütörtököt.

Az sem titok, hogy csak időnként érnek el sikereket, hogy tudásuk sokkal kevésbé teljes, mint az avatatlanok gondolják ( avatatlanoknak itt azokat nevezzük, akik úgy gondolják, hogy az élővilág sokkal bonyolultabb, mint az élettelen, mert az előbbi olyan jól van megalkotva. Például, a mai fizikusoknak az atom szerkezetének némely részérői csak homályos elképzelésük van ) mégis, az atombombát sikerrel le tudták írni. Az egyik fontos elemi részről, az elektronról bizonyos szempontból nagyon keveset tudnak, nem tudják például azt megállapítani, hogy egy adott időpillanatban hol van ( sőt azt is eldöntötték, hogy szigorú értelemben sohasem lehet választ adni erre a kérdésre). A matematikusoknak is vannak ehhez hasonló gyenge pontjaik. Például, évszázadokon át nem tudták eldönteni, hogy legkevesebb hány szín elegendő egy térkép kiszínezéséhez ( úgy, hogy a szomszédos országok nem lehetnek azonos színűek ), azt gyanítják, hogy négy szín elegendő, de eddig ezt nem tudták bebizonyítani.

Az elmúlt száz évben a fizikatudósok fegyvertárában új fegyver jelent meg: a matematikai statisztika. Ezt régebben csak elvétve alkalmazták. Ma már egyre növekszik a jelentősége és az élővilág vizsgálatában is egyre fontosabb szerepet kap. A játékelméletnek is sok kapcsolata van vele. A statisztika alkalmazási lehetőségeit jól mutatja egy korai példa: a statisztika elmélete sikeresen írta le azt, hogy a Porosz Hadseregben a lórúgások következtében történt elhalálozások ( az évek során ) hogyan oszlanak meg:

Az alábbi adatokra hivatkozok: Az amerikai hadsereg tíz hadtestében egy húszéves időszakban (1875—1894) hadtestenként és évenként a következő elhalálozási adatokat jegyezték fel:

Halálozások száma	Előfordulások száma
	Megfigyelés szerint	Számítások szerint
0	109	109
1	65	66
2	22	20
3	3	4
4	1	1

A számítások szerinti érték meghatározása azon az információn alapult, hogy a halálos kimenetelű szerencsétlenségek átlaga kb. húszhónaponként egy. A számítások alapja olyan statisztikai elmélet, amely ritkán előforduló eseményekre különösen jól alkalmazható.

Ha úgy vélnénk, hogy a lovak cselekedetei sokkal inkább megjósolhatók, mint az embereké, hát a módszer éppen ilyen sikeresen használható az emberi rúgások következtében elpusztult lovak számának becslésére. Annak, hogy a matematikai statisztika valóban alkalmazható az emberekkel kapcsolatban is, legjobb bizonyítéka a biztosítás. A biztosítási társaságok számadása ékesszóló bizonyítéka az elmélet sikerességének. Az emberekkel kapcsolatban is lehet becsléseket mondani.

Milyen kilátásaink vannak a játékelmélettel kapcsolatban? Egyrészt az elmélet biztosan túl egyszerű ahhoz, hogy bármely katonai, közgazdasági és társadalmi problémát minden szempontból leírjon. Másrészt azonban elég ahhoz, hogy sok érdekes konfliktus lényeges elemeit megvilágítsa.

5. Játékosok és személyek

Most lássuk magát a játékelméletet. A pókerjátékkal kezdve vezessünk be néhány használt fontosabb fogalmat. A pókerjátékban egy csomag kártyával, némi pénzzel vagy más értékkel bizonyos szabályok szerint játszanak. A szabályok az összes cselekvési lehetőséget kimerítik: megadják, hogyan kell osztani, fogadni, mi történik a lapok leterítésekor, mi lesz az összegyűlt pénzzel.

A póker ötszemélyes játék. Ez azonban inkább nyilvánvaló, mint igaz: lehet, hogy két játékos koalíciót alkot a játékban, megegyeznek egymás közt, hogy nyereményeiket és veszteségeiket közös alapba gyűjtik. Ha így van, akkor, ha a körülmények nem gátolják őket, közös érdekek alapján játszanak. Ha például a koalíció egyik tagja úgy látja, hogy a másik győzhet a lapjaival, akkor saját lapjaitól függetlenül tartani fogja a tétet. Ha már csak hárman játszanak, akkor lehet, hogy bedobja a lapot, hogy a harmadik csődbe jusson, lehet, hogy túllicitálja őt meg akkor is, ha saját lapjaival biztosan nem nyerhet. Röviden: a koalíció tagjai egyetlen, kétfejű személyhez hasonlíthatók.

Ha két játékos koalíciót alkot, akkor nyilván nem ötszemélyesnek, hanem négyszemélyesnek érdemes tekinteni a játékot. Így arra a megállapításra jutunk, hogy nem az asztal körül ülő testeket, hanem az ellentétes érdekeltségű csoportokat kell megszámlálnunk. Elvünk szerint például a bridzs kétszemélyes játék, hiszen ha a partnerek nem cserélődnek, két különböző érdekeltségű csoport játssza. A “személy” és a “játékos” szavak az általunk használt értelemben épp úgy jelenthetnek jogi személyeket és szervezeteket, mint szokásosan értelmezett személyeket. Visszatérve a pókerre, azt olyan kétszemélyes játéknak is tekinthetjük, amelyben mi az egyik játékos, a többi négy személy a másik játékos. Azt is mondhatjuk, hogy a többiek által alkotott koalíció hírközlési szervei gyengék, vagy hogy valamilyen más hiba miatt bizonyul hatástalannak.

A játékban részt vevő személyek száma a különböző érdekeltségű csoportok száma, a játékelmélet egyik alapvető fogalma. Az elemzés módja és az egész helyzet minden jellemvonása ettől a számtól függ. Szempontunkból három számnak van különös jelentősége: az egynek, a kettőnek és a kettőnél többnek.

Egyszemélyes játék például a szórakozásból játszott pasziánsz. Még akkor is, ha a játékos a kártyalapokat 100 Ft-ért veszi valakitől és a nyerőhalmazba átvitt lapok darabjáért 500 Ft-t kap, ugyanaz a helyzet, csak a véletlen eseményeket kell megvizsgálni, a játékban nincs értelmes emberi ellenfél. A játékelmélet szempontjából az egyszemélyes játékok érdektelenek, és ezért valójában nem is foglalkozunk velük. Megoldásuk elvileg teljesen egyszerű: egyszerűen ki kell választani azt a cselekvéssorozatot, amelyik a legtöbb hasznot eredményezi. Ha véletlen események is szerepet játszanak a játékban, akkor a legnagyobb átlagos hasznot hozó cselekvéssorozatot kell választani. Bár ezzel igen sok gyakorlati probléma felett átsiklottunk.

Az egyszemélyes játékok ( a pasziánszt kivéve ) mégis kétszemélyeseknek tekinthetők: olyan speciális kétszemélyes játékoknak, amelyekben az egyik játékos a játszó személy, a másik a természet. Ez a nézőpont akkor is hasznos, ha hiszünk abban, hogy a természet rosszakaratú lény és tönkre szeretne tenni minket. Például lehet, hogy a játékos nem tud eleget a természet “terveiről” és ezért nem tudja kiválasztani a legtöbb hasznot hozó cselekvéssorozatot. Vagy lehet, hogy a játékos ismeri a természet lehetséges “viselkedésmódjait” és tud valamit arról, hogy a természet milyen gyakorisággal alkalmazza azokat. Ebben az esetben a játékelmélet hasznos: bizonyos meghatározott, legkedvezőbb játékmódot ajánl.

Az igazi kétszemélyes játék nagyon érdekes. A gyakorlatban ez fordul elő legtöbbször és ennek megoldásához jelenlegi fogalmi és technikai eszközeink elegendőek is. Hétköznapi értelemben ezeket tekintik konfliktusoknak. Van egy ellenfelünk, akiről fel kell tennünk, hogy intelligens és nyerni akar. Ha kedvezőnek látszó cselekvéssorozatot választunk, felfedezi tervünket, csapdába csal és így kamatoztatja felfedezését. Sok olyan játékot, amely valójában nem kétszemélyes játék, kétszemélyesnek fogunk tekinteni. Első ilyen példa a pókerjáték volt, ahol az egyik személy az egyik játékos, a másik az összes többi játékos által alkotott csoport volt. A játékelmélet eddig kidolgozott részei legfőképp a kétszemélyes játékokkal kapcsolatosak.

Ha a különböző játékosok, azaz a különböző érdekeltségű csoportok száma kettőnél több, akkor minőségileg új dolgokat kell figyelembe vennünk. A legfontosabb újdonság az, hogy a játék folyamán változhat a különböző érdekeltségű csoportok összetétele, a játékosok ( ha ez számukra hasznosnak látszik ) időleges koalíciókat alakíthatnak és szüntethetnek meg. Például a pókerben előfordulhat, hogy egy erősen vezető játékos ellen a többi játékos koalíciót alkot, nehogy a vezető játékos mindenkinek ( még a viszonylag jól állóknak is ) elvigye a pénzét. A többszemélyes játékok jóval bonyolultabbak, mint a kétszemélyesek, megértésük is nehezebb. Ezért a továbbiakban csak kétszemélyes játékokkal foglalkozok.

6. A nyereség

A játékok osztályozásának és vizsgálatának egyik fontos szempontja tehát a játszó személyek száma; a “személy” szó itt különböző érdekeltségű csoportokat jelöl. A játékelmélet másik fontos fogalma a nyereség: mi történik a játék végén? Mondjuk a pókerjáték végén? A pókerben rendszerint kicserélődnek a vagyonok. Ha két játékos van, mondjuk a Kék és a Piros, akkor, ha a Kék 1000 Ft-t nyer, akkor a Piros 1000 Ft-t veszít.

Másképp

Kék nyereménye = Piros vesztesége,

vagyis

Kék nyereménye - Piros vesztesége = 0.

Ha megállapodunk abban, hogy a nyereményt pozitív nyereségnek, a veszteséget negatív nyereségnek tekintjük, akkor ezt így is írhatjuk:

Kék nyeresége + Piros nyeresége = 1000 Ft – 1000 Ft = 0.

A nyereségek összege nem mindig nulla. Például, ha a nyertesnek a nyeremény 10 százalékával hozzá kell járulnia az elfogyasztott italokhoz és az egyéb váratlan kiadásokhoz (p1. a sarki rendőr megvesztegetéséhez), akkor a nyereségek összege nem nulla:

Kék nyeresége + Piros nyeresége = 900 Ft - 1000 Ft = -100 Ft

A fenti két eset alapján a játékokat két alapvető típusba sorolhatjuk aszerint, hogy a nyereményeket pozitív nyereségekként, a veszteségeket negatív nyereségekként számlálva a nyereségek összege nulla-e, vagy nem. Ha a nyereségek összege nulla, akkor nullaösszegű játékokról beszélünk. Ha nem nulla, akkor (a matematikusok nem valami találékonyak) nem nullaösszegű játékokról beszélünk. A megkülönböztetés fontossága nyilvánvaló: a nullaösszegű játékokban jó, tiszta, zárt rendszerrel kell foglalkoznunk. Úgy képzelhetjük, mintha a játékosok vagyonukkal együtt be lennének zárva egy szobába. Az ilyen játékok megoldását bizonyos erőfeszítések árán meghatározhatjuk. A nem nullaösszegű játékokban viszont megtalálhatjuk a nullaösszegű játékokkal kapcsolatos összes problémánkat, és további nehézségekkel is meg kell küzdenünk. Ezt a helyzetet csak úgy tudjuk leírni, hogy bevezetünk egy harmadik fiktív játékost nevezzük tudománynak, vagy sarki rendőrnek.

Így

Kék nyeresége = 900 Ft

Piros nyeresége = - 1000 Ft

A rendőr nyeresége = 100 Ft,

és most már

Kék nyeresége + Piros nyeresége + Rendőr nyeresége = 900 - 1000 + 100 = 0 Ft.

Így háromszemélyes, nullaösszegű játékot kaptunk, amelyben a harmadik személy olyan, mint a malomkőből készült nyaklánc. De ne felejtsük el azt, hogy a háromszemélyes játékok elemzése a kétszemélyesekénél lényegesen nehezebb, hiszen a többféle lehetséges koalícióval is számolnunk kell. Így a nullaösszegű játékok, különösen a kétszemélyes nullaösszegű játékok elemzése lényegesen, könnyebb feladatot jelent, mint a nem nullaösszegűeké.

A társasjátékok ( póker, sakk, amőba, halmák ) rendszerint nullaösszegű játékok. Sok más konfliktus is nullaösszegű játéknak tekinthető. A játékelmélet eddig kidolgozott részei főként az ilyen játékokra vonatkoznak. A nem nullaösszegű játékokkal kapcsolatban is születtek és születnek eredmények. A kétszemélyes játékok körében érdekes, de nehezen vizsgálható eset az, amikor a névértékben egyforma nyereségértékek hasznossága a játékosok számára nem egyforma. Ez a helyzet még a társasjátékokban is gyakran előfordul.

 

7. Stratégiák

Miként a “személy” szót is, a “stratégia” szót is a hétköznapitól némiképp eltérő értelemben használjuk a játékelméletben. A mindennapi értelemben használt “stratégia” szóba beleértjük azt is, hogy a terv ügyes és jó, a játékelméletben viszont csak azt kívánjuk, hogy a terv teljes legyen. Stratégiának az olyan teljes tervet nevezzük, amelyet az ellenfél semmiféleképpen sem tud keresztülhúzni. Akármit is választ ugyanis az ellenfél, az a mi lehetséges cselekvéssorozataink halmazával együtt éppen a stratégia leírásának részét képezi.

Így a játékelmélet stratégia-fogalma két lényeges szempontból különbözik a szó hagyományos jelentésétől: a stratégiának teljesnek kell lennie, de teljesen rossz is lehet. Így például a pókerjátékban az összes lehetséges stratégia között az is benne van, amelyikben valakinek pikk Royal Flushot osztanak és bedobja a lapot. Ez nem túl okos stratégia de stratégia. Éppen így, a halmáknál is, ha visszalépünk, jobb lépési lehetőséget is nyerhetünk. Az elemzés szempontjából teljességgel megközelíthető játékokban az összes lehetőséget előre láthatjuk ( ha nem gyakorlatilag, akkor elvileg ) és így az összes lehetséges stratégiát fel tudjuk sorolni.

Most mar előhozakodhatunk a játékok osztályozásának és tanulmányozásának egy újabb fontos szempontjával: a játékosok számára lehetséges stratégiák számával. Ha a játékosokat Kéknek és Pirosnak nevezzük és például Kéknek három, Pirosnak öt stratégiája van, akkor a játékot 3 x 5-ös játéknak nevezzük.

Amikor a játékosok számáról beszéltünk, akkor bizonyos számoknak ( az egynek, a kettőnek és a kettőnél többnek ) különös jelentőseget tulajdonítottunk. Hasonlóképpen, a stratégiák számának is vannak kritikus értékei; itt két főcsoportot kell megkülönböztetnünk. Az első csoportba azok a játékok tartoznak, amelyekben a több stratégiával rendelkező játékos stratégiáinak száma is még véges szám. Ez azt jelenti, hogy a stratégiákat bizonyos meghatározott idő alatt össze tudjuk számlálni. A második főcsoportba azok a játékok tartoznak, amelyekben legalább az egyik játékos stratégiáinak száma végtelen.

Az utóbbi típusú, un. végtelen játékoknak sok érdekes és hasznos alkalmazása van, elméletük azonban meglehetősen nehéz.

 

8. A kritérium

• Ha kritériuma egyszerűen csak a mennyiség, akkor a legolcsóbb húsfajtából fog vásárolni és nyereséget kilókban mérjük.

• Ha a változatosság a kritérium, akkor a legolcsóbbal kezdve többféle húsból vesz minimális, de még használható mennyiséget. A nyereséget most a vásárolt húsfélék száma adja meg.

1. Táblás játékok

1. A táblás játékok sokszínűsége

A kétdimenzióban elhelyezett különféle rendezettségű és cella formájú játékok ősidők óta a legkedveltebb játékok közé tartoznak. Több ezer játék alakult ki az idők során, amely egyszerű kellékekkel ( táblák, bábuk, esetleg dobókockák ) és könnyen megtanulható szabályokkal bárki számára elsajátítható, kellemes szabadidő eltöltést biztosít. Ezek a játékok nagyban fejlesztik a logikai és stratégia képességeket, miközben szórakozást is nyújtnak. A matematikai és egyéb problémák megértése és tanítása is hatékonyabb egy-egy célratörő játékkal.

A játékok sokszínűségét mutatja, hogy a táblákon kirajzolódó “pálya”, a játékosok száma, a lépések szabálya, a szükséges tudásszint annyira sokrétű, hogy ezek teljességgel való leírása is problémát okoz. Némelyik játék szabályai kisebb módosításokkal kerültek a köztudatba, mint ahogy a pókert is ahány ország, annyi szabályváltozata van.

Ebben a fejezetben különböző módón osztályozva mutatok be táblás játékokat ( a teljesség igénye nélkül ), néhány szóban elemezve a programozási szempontokból.

2. Játékosok száma

Egyedül is lehet játszani, a képességeinket fejleszteni, de szinte mindenki jobban szereti, ha egy ellenféllel méri össze a tudását. Ez akár lehet hús-vér vagy virtuális intelligencia.

A játékokat 3 fő csoportba érdemes sorolni a játékosok számát illetően:

1. Egyszemélyes játékok

Ilyenek például a szoliter játékok. A szoliter egyszemélyes feladványként lett kedvelt elmejáték. Legismertebb változatainak lényege, hogy egy meghatározott alakzatban a táblára felrakott bábukat, az ütési szabályok betartásával, egyetlen egy maradóig, mind leszedjük. Pontosabban: egy, a megoldást eredményező ütéssorrend megtalálása a feladat.

A másik nagysikereknek örvendő egyszemélyes játék az aknakereső. A feladat egyszerű: meg kell keresni az összes ( gombok alá elrejtett ) aknát. A játékost segítik a bombákkal érintkező ( 8 vagy a széleken kevesebb minimum 3 ) cellákban elhelyezett számok, amelyek a környezetükben lévő aknákról árulkodnak. A játékos megítélése alapján fedi fel a gombokat törekedve arra, hogy ne aknát találjon. Ha aknát sejt alatta, akkor azt megjelöli. A játékos akkor nyer, ha az összes aknát megjelölte. Ilyenkor az “ellenfele” az elrejtett aknák és az idő. Létezik olyan elhelyezkedése az aknáknak, amit nem lehet triviálisan kiszámítani. Ilyenkor marad a véletlen kiválasztás vagy a bumm! L

Programozási szempontból az egyszemélyes játékok nem okoznak nagy problémát, hiszen a program feladata a megjelenítés, a lépések megvalósítása és a szabályok betartása. Nem kell foglalkozni ellenlépésekkel és különböző stratégiákkal.

A játékos akkor nyer, ha teljesíti a végállás feltételeit, amit a programozás során nem okoz túl bonyolult problémát. A játékok megnehezíthetőek időkorlátokkal, vagy az idő alapján adott pontokkal. Ettől versenyfeladattá válik a játék, hiszen nem csak az feladat teljesítése a fontos, hanem, hogy ki a gyorsabb.

Ez így több játékos részére is közös játékot biztosít. A játszma egyjátékos részvételét igényli, de a játszmák számától függetlenül egy közös játékká válik egymás ellen, vagy saját magunk ellen.

2. Kétszemélyes játékok

Ez a leggyakoribb játékfelállás, amikor két ember egymás ellen mérkőzik. Nagyobb versenyeken, ahol több versenyző is részt vesz, össze tudják mérni a tudásukat, hiszen kettesével mérkőznek meg és a legjobbak maradnak bent a döntőben. A döntőig eljuthatunk kieső ágon ( Az összepárosított játékosok közül a nyerteseket párosítják újra össze és így addig folytatják, amíg el nem érik a döntőt. A vesztesek búcsúznak, vagy a dobogós helyezésért játszanak. Megeshet, hogy a “második tudású” versenyző az első körben kiesik a legjobb “segítségével”… ) vagy a másik módszer a körmérkőzés ( Ez egy kicsit igazságosabb módszer, hiszen mindenki játszik mindenkivel és a nyert játszmák alapján rangsorolják őket. Holtverseny esetén szétlövés következik ).

A kétszemélyes játékok lényege, hogy egyenlő esélyekkel ( egyenlőtlen felállás esetén revans ) küzdenek egymás ellen. A két játékos közül csak az egyik nyerhet, a másik veszít, de mindkét játékos nyerni akar. Esetleges döntetlen esetén még egy játszma, vagy sorsolás dönti el a nyertest. ( kockadobás, pénzfeldobás )

Tehát az emberi elmék stratégiai képességei mérik össze erejüket. A két játékos stratégiája lehet különböző is, hiszen sok játékban például a felállás és a szabályok is azonosak a résztvevőknek, de a lépést kezdő játékos mégis előnyben van, ezért a kezdő az előny megtartásával totális győzelmet akar elérni, míg a lépéshátrányban szereplő játékos megpróbálja átvenni a lépéselőnyt, de legalább döntetlent kiharcolni. Ilyenek például a sakk, a dáma, fonákollós játékok. A másik ok a stratégiák különbözőségére a szabályok vagy kezdőállások különbözőségéből adódik. Itt a játékosoknak másképpen helyezkednek el a bábúik vagy még a bábúk száma sem egyezik meg.

Ilyenek például: “agarak és rókák”, “farkas és kutyák”, “várjáték”, “róka és libák”, “tablut”, “pókháló” játékok, ahol a az üldöző és üldözött bábuk száma nem azonos. A szabályok többségében az üldözők vannak többen.

Programozási szempontból a kétszemélyes játékoknál kezdődik a nehézség. ( Ha a játék megjelenítése, a szabályok felügyelete csak a feladat, akkor az egyszemélyes játékokhoz hasonlóan ez nem okoz problémát, csak a játékosok sorrendjére kell figyelni. Azonban a játék végkimenetelét nem mindig könnyű meghatározni. ) Ma már igény, hogy az “intelligens” gépekkel mérjük össze stratégiai képességeinket. Hiszen manapság ritkán ér rá két ember néhány jó partira. Ennek az oka “felgyorsult világ”, az emberi érintkezés távolódása és egyéb szociális problémák, de ennek felderítése nem célja a dolgozatomnak. Ennek ellenére az évek során a játék ismét divatba jött. Régen ez többnyire a gyerekek kiváltsága volt, de ma már mindenki szeretne játszani a televíziós műsorokban a rádiós játékokban, az interneten…

Tehát programoznunk kell egy okos ellenfelet aki legalább olyan jó mint játékos parnere, mert különben nem lenne élvezetes a játék. Érdekes pszichológiai tulajdonság, hogy ha az ellenfelünkkel szemben mindig nyerünk, vagy olyan erős, hogy hosszú gyakorlás után sem vagyunk képesek megverni, akkor elmegy a kedvünk az ellenfelünkkel való játéktól.

A gép elleni játszmák alatt sokat lehet tanulni, taktikákat lehet ellesni kigondolni. Ezáltal sokat fejlődhet a stratégiai képességünk. Ez egy kis paradoxont is okozhat, ha a programunk jól játszik, de néha tudunk ellene nyerni, és gyakorolva már ügyes játékosokká válunk, de a program azonos szinten marad, akkor megunjuk a gyenge ellenfelet. Ha viszont erős az ellenfél, akkor meg elmegy a kedvünk a gyakorlástól. Erre a legegyszerűbb módszer, ha a gép a lépési stratégiáit nehézségi szintekre bontjuk, és mi határozhatjuk meg, hogy milyen erős legyen az ellenfél. ( az a megoldás is beválik, ha az gép néha-néha direkt hibázik )

3. Többszemélyes játékok

A többszemélyes játékok az “igazi” társasjátékok. A játék ilyenkor felszabadultabb, hiszen nem ketten mérik össze tudásukat és az egyik nyertes, a másik a vesztes, hanem többnyire egy nyertes van, a többiek pedig kollektívan a vesztesek. A másik oka, hogy ezek a játékok nagy részébe bele szól a szerencse, dobókocka, vagy egyéb eszköz dönti el a lépéslehetőséget. Pl.: “Ki nevet a végén?” játékban nagyobbrészt a szerencse játszik szerepet, mint a taktikázás. Az egyetlen általunk irányított dolog, hogy a dobásunk eredményét melyik bábúnkkal akarjuk lelépegetni. Ez nem ad túl nagy szabadságot a stratégia területén, de ezeknél a játékoknál nem is ez a lényeg, inkább a közös szórakozás kerül az előtérbe.

Ezen játékok között is van olyan, amely nagyobb stratégiai készséget igényel. Ilyen a RISK hadi játék, ahol “háború” folyik a világtérképet imitáló pályán a különböző országokért. A játék alatt meglehet egymást támadni, szövetséget lehet kötni és a hadtesteinket átszállíthatjuk gyarmatainkra. Bár a játékot nem vesszük komolyan, és itt is szerepe van kis részben a szerencsének, de jó ellenfelekkel komoly stratégiákat lehet kieszelni.

3. A résztvevő bábúk száma

A rengeteg játékszabály alakult ki, ezekben szinte minden variációban fellelhető a bábúk száma és viszonya. A legtöbb játékban a résztvevő ellenséges bábúk száma megegyezik és egyenrangúak. De sok az olyan táblajáték, ahol az ellenfeleknek nem azonos számú és lépés szabályú bábúik vannak. Vannak játékok, ahol a bábúk száma változik ( leütik, beér …)

1. Azonos számú és rangú bábúk

• vagy megmaradnak a bábuk a játszma végéig és ilyenkor a cél elérése lehet a pálya egy másik pozíciójának gyorsabb elérése, ilyenek a halma játékok.
• vagy a játék során egyre több bábuval játszanak egy maximum eléréséig.

1. Eltérő erőviszonyok, előnyadós játékok

• “Róka és libák” nevezetű játéknak két változata is van, az egyikben 13, a másikban 17 liba van az egy szem rókával szemben. A céljuk is más, róka sorban “megeszi” a libákat, míg a libák feladata a róka beszorítása. A ütéskényszer nehezíti a róka feladatát.
• “Várvédelem”-ben 2 védő harcol a 20 támadó ellen. A játékban a létszámfölényt a védőjátékosok nagyobb szabadságfokú lépéseivel egyensúlyozzák.

1. Változó bábú szám

1. Jellegzetes lépések

Ebben a fejezetben bemutatok néhány lépés fajtát, melyek jellemzőek játékok csoportjaira. Bár a lépés szabályok hasonlóak vagy azonosak ezekben a csoportokban, mégis a pálya mássága, vagy a szabályok alakítása jól elkülöníti a játékokat.

1. Egyedi lépésszabályok

• sakk, pályamódosított változata a hexasakk, vagy a kamikáze franciasakk. Lépésszabályai igen sokszínűek és bonyolultak, ezért is számít az egyik legnehezebb stratégiajátéknak.
• go, változatai csak a pályaméretben különböznek. Lépésszabályai igen egyszerűek, de a játék maga igen bonyolult tud lenni. Sokan vélik, hogy azonos nehézségű mint a sakk.
• Kicsit furcsa táblán játsszák a blackgamon nevezetű játékot, ebből adódik, hogy a lépésszabályai sem általánosíthatóak.

1. “Átugrálós”

• A szoliterekben természetesen saját bábúinkat ugorjuk át és csak egyszer tehetjük meg egy lépésben. Az átugrott bábút “leütjük”, levesszük.
• A dámákban csak az ellenfél bábúit ugorhatjuk át, üthetjük le, akár több ugrást is lépésenként. Itt nem csak ugrani lehet, hanem az egyszerű előre haladás is megengedett. A dámának nagyon sok variációja létezik a pálya méret és a bábúk elhelyezésének variálásával.
• A halmákban egyesével is haladhatunk és akár a saját akár az ellenfél bábúját is átugorhatjuk sorozatban is. Természetesen itt nem az ütés játszik szerepet.
• Az egyenlőtlen felállású játékok nagy része is ezt a játékszabályt követi. A kevesebb létszámú csapat előre-hátra esetleg átlósan is haladhat, míg az ellenfél csak oldalt és előre. De az ütések az átugrás szabályainak megfelelően történek akár sorozatban is.

1. “Szaporodás-hódítás”

• 1 variáció: bármely a mi területünk melletti cellák közül egyet elfoglalunk, azaz szaporodunk egyet.
• 2 variáció: a pálya alakjától függően más irányok közül választva egy, a saját cellánktól 2 távolságban lévő szabad cellába átköltözünk.

• hexák. A játék alapverziójában egy hatszög alakú terület van feltöltve hatszög alakú cellákkal, mint egy méhkas.
• Othelló. Ez egy négyzethálós területen játszható játék. A lépések kicsit kötöttebbek, mert csak szaporodással lehet lépni és kötelező a hódítás.

1. “Malom” játékok

• Alapszabály: mindkét játékos törekszik arra, hogy malmot ( egyvonalban 3 saját bábú ) alakítson ki. Malom esetén az ellenfél bábúiból bármelyiket leveheti. Ez a játék egész ideje alatt fennáll.
• Kezdő állapot. Ilyenkor egyesével, felváltva a játékosok elhelyezik a bábuikat az üres csomópontokba, törekedve arra, hogy már most malmot érjenek el.
• A küzdelem. Bármely saját bábúval egy szomszédos mezőre lépünk.
• Végjáték. Akinek már csak 3 bábúja maradt, az bármelyik bábújával bármely szabad csomópontra ugorhat.

1. A halma játék elkészítése JAVA nyelven

Ebben a fejezetben bemutatom, hogy hogyan kezdtem a programozási feladatom a játék megismerésével, majd elemzésével, a program tervezésével és hogyan jutottam el a kész programig, miként teszteltem. Ez egy hosszú folyamat eredménye, mely során felmerülő problémák és megoldásuk lényegét tudom csak bemutatni. A játék kiválasztásánál törekedtem arra, hogy ne legyen túl bonyolult, de mégis minél jobban megmutassa a hasonló alkalmazásokban felmerülő problémákat. A megoldás során sok olyan elméletet és algoritmust alkalmaztam, mely a főiskolai képzés anyagaira épül (operáció kutatás, számítógépes grafika, algoritmusok és adatszerkezetek, mesterséges intelligencia…), de azon túl is használtam tudás anyagot, mely az elkészítés során elengedhetetlen volt. ( JAVA, PERL, Fly, stb. )

1. A játék szabályai

A Halmáknak két fő változata van, az egyiket négyzethálós táblán játsszák, a másikat pedig hatágú csillag alakú területen, mely átlói egyenlőszárú háromszögeket alkotnak (Ezt a változatait “kínai sakk” néven ismerik a halma háromszög-rácsozatú játékmezőn játszható, hatszemélyes alapváltozatát. Amikor a GO kezdett hódítani Európában, akkor egy élelmes német játékgyártó igyekezett a halmát is keleti játékként népszerűsíteni. Mint tapasztaljuk: sikeresen).

A pályák méretétől függ a bábúk száma vagy a játékosok száma. A jobboldali elrendezésben (10x10-es játékmezőn 4x10 db koronggal) négyen, a baloldaliban akár hatan is versenyezhetnek, különböző színű korongjaikkal. Játszható kétszínű korongokkal is, akár mint páros játék, akár mint olyan hatszemélyes játék, amelyben 3-3 játékos alkot egy-egy csapatot. Megegyezés szerint: teljes helycsere, vagy egy bábucsoport gyorsabb áttelepítése a verseny célja.

A halmák: "helycserélős", ütés nélküli, békés, ugyanakkor kombinatív játékok Lehet egyedül is játszani, mint feladványmegoldásként, de lehet 2, 4, akár 6-an is játszani.

A társas halmajátékok célja: a tábla egyik sarkában felállított korongjainkat az átellenes sarokba (ellenfelünket megelőzve) áttelepíteni bábuinkat az ellenfél bábuinak helyére, vagy a nekünk kijelölt helyre.

Lépésszabály: tetszés szerinti irányban - jobbra, balra, négyzethálós pályán (4): fel, le míg háromszögrácsos pályán (6): átlósan is - a szomszédos üres pozícióra léphetnek a korongok: egy lépésben, egy korong, egy pozícióval. Ugrani is szabad, mind a saját, mind az ellenfél korongját átugorhatja a "lépő-haladó korong" (de az ellenfél korongjait nem ütjük ki).

2. A program tervek

• grafikailag jól átlátható és értelmezhető – színbeli megkülönböztetések, felíratok
• könnyen és egyszerűen kezelhető – “drag and drop” technika, gombok, csúszkák
• “intelligens” ellenfél – egyben gép-gép elleni tesztek, gyors rutinok
• jól skálázható – változtatható játékos szám, ellenfél tudás szintek, reakcióidő
• program írása során tesztvisszajelzések – tábla állás, lépéskeresési útvonal
• összesített elemzések készítése
• hibamentes működés – jól átlátható rutinok, hibakereső teszttervek
• képlékeny adatkezelés – későbbi bővítések lehetősége (más pálya, több játékos)

1. A pálya kialakítása

• Minden mezőről 2-6 másik mezőre léphetünk, melyek kapcsolatban vannak egymással. Ebből adódik egy irányítatlan gráf lehetősége. Hozzunk létre egy olyan gráfot, amely tartalmaz egy azonosítót – pl sorszám – egy tárolót a tartálmáról – üres-e, vagy milyen manó van a mezőn – és az összes szomszédjára hivatkozó mutatót. A következő táblázatban a gráf első pontjainak adatai találhatók a kezdő állásnál. Ezek az adatok vektorokba rendezve tárolhatók, ahol az első szám a csomópont azonosító azaz egy sorszám, utána a mező tartalma – ez lehet üres, piros, fehér ás zöld – majd a csomóponthoz kapcsolódó további csomópontok azonosítói. Összesen az alap pálya 37 mezőjéhez 37 ilyen vektorra van szükség minden pályaállás ábrázolásához.

• Próbálkozzunk a táblásjátékoknál általában jól bevált kétdimenziós tömbbel. Azaz alakítsuk át a háromszögrácsos táblát kétdimenziós ( négyzetrácsos ) tárolóvá. Osszuk fel sorokra a táblát és csúsztassuk egymás alá az eltolódott oszlopokat. Így kapunk egy 7 x 9-es mátrixot, aminek cellatartalma a hozzá tartozó mezőn található manó azonosítója ( 1-piros, 2-fehér, 3-zöld ) ezenkívül meg kell különböztetnünk az üres mezőket és azokat a területek, melyek nem vesznek részt a játékban, mert a “csillagon” kívül esnek. ( 0-üres, -1-tiltott mező ). Nézzük, hogy alakul a kezdő állás a tároló mátrixban:

• Az előző ábrán látszik, hogy a cellák soronként féllel el vannak tolva és így jobban modellezik a mezők elhelyezését. Próbáljuk meg ezt a modellt megalkotni. Tehát olyan mátrixot kellene létrehozni, aminek minden második sora fél cellával el van csúsztatva. Sajnos ilyet egyszerűen nem tudunk létrehozni, de kis átalakítással egy olyat igen, ami hasonló jó tulajdonságokkal rendelkezik. Vegyünk vízszintes irányban kétszer akkora mátrixot, mint az előbb és csak a nekünk megfelelő cellákat használjuk az ábrán megadott módon. Minden páros sorban a páros cellákat és minden páratlan sorban a páratlan cellákat használjuk majd.

1. A manók elhelyezése

A játék a képen látható alapfelállásból indul. Ehhez a különböző színű manókat a nekik megfelelő cellákra kell irányítani. Ennek a legegyszerűbb módja, ha sorban megadjuk a manóhoz tartozó cella koordinátákat és természetesen a tabla tömbben lefoglaljuk nekik a helyüket, hogy ne üres területként érzékeljük.

A program ezen része igen egyszerű, csak a játékosok számára figyel, hogy 2 vagy 3 játékos manóit kell elhelyeznie a pályán. Ha csak ketten játszanak akkor a zöld manók nem kerülnek elhelyezésre. Itt állítja be a kezdo változó értékétől függően a kilep változót ( amit a beállítások ablakban lehet megadni ), azaz ki kezdi az első lépést. Ha a kezdo értéke nagyobb mint a beállított játékosok száma – user – akkor véletlen sorsolás történik.

////a kezdő poziciók feltőltése 2 ill. 3 játékos figyelembevételével

public void kezdes(){

if(user==3){

mano[2][0].setPos(0,2);

mano[2][1].setPos(2,2); //mano[2][1].setPos(6,2);

mano[2][2].setPos(4,2);

mano[2][3].setPos(1,3);

mano[2][4].setPos(3,3);

mano[2][5].setPos(2,4);

for(int i=0;i<6;i++){mano[2][i].setVisible(true);}

}else{

for(int i=0;i<6;i++){mano[2][i].setVisible(false);}

}

mano[1][0].setPos(8,2);

mano[1][1].setPos(10,2);

mano[1][2].setPos(12,2);

mano[1][3].setPos(9,3);

mano[1][4].setPos(11,3);

mano[1][5].setPos(10,4);

mano[0][0].setPos(6,8);

mano[0][1].setPos(5,7);

mano[0][2].setPos(7,7);

mano[0][3].setPos(4,6);

mano[0][4].setPos(6,6);

mano[0][5].setPos(8,6);

//cél pozíciók

endx[0]=6;endy[0]=0;

endx[1]=0;endy[1]=6;

endx[2]=12;endy[2]=6;

//a kezdő játékos beállítása

kilep=kezdo;if(kilep>=user){kilep=(int)(Math.random()*user);}

lepesszam=0;ellep=0;

}

 

2. Lépések ellenőrzése

• “ugrás”: az aktuális pozíciótól egyenes vonalban 2 lépésre üres helyet találunk, és a köztes mező már foglalt másik manó által.
• “sorozatos ugrás”, az előbb említett ugrás egymásutánjai a végpozíciókból kezdőpozíciók képzésével.

1. “Lépéstávolság”

Az emberi intelligencia könnyen felismeri, a játékszabályokat követve, ahhoz hogy átérjünk a “túloldalra”, egy bizonyos irányba kell mozgatnunk a manóinkat. Érzékeljük, hogyha ebbe az irányba haladunk, akkor egyre “közelebb” jutunk a célhoz.

Felvetődik a kérdés, hogy tudjuk meghatározni azt, hogy milyen távol vagyunk még a céltól? Hogyan mérjük ezt és mit tudunk kezdeni vele? “Lemérjük centivel?” azaz koordináta számítással kiszámítjuk a manók távolságát a ??? mitől is? Hiszen nem tudjuk melyik hova fog beérni. Kis csalással, de a lényegen nem változtatva vegyük az egyik célterületi pontot (praktikusnak tűnik mindegyik csoportnál a legtávolabbi pont) és ehhez határozzuk meg a távolságokat. Sajnos itt is eltévedhetünk, hiszen a manók nem egyenes vonalon haladnak a cél felé. Akkor próbáljuk meg felbontani x és y cellatávolságokra. Sajnos a pálya nem raszteres volta miatt (bár mi átalakítottuk, de ezzel torzítottunk rajta) a különböző manócsoportokra nem tudunk azonos és korrekt algoritmust írni.

Ezek után kézenfekvőnek tűnik, hogy ha nem megy egyenes vonalban, nem megy raszteresen, akkor próbáljuk meg lépésvonalban meghatározni minden manóra. Ha belegondolunk ez azt jelenti, hogy hány lépés kell az aktuális manóknak ahhoz, hogy beérjen. Nos hova is? Ha rögzítünk egy pontot (legyen ez a már előbb említett legtávolabbi sarok) és összeadjuk a manók szükséges lépéseinek számát, amivel elérhetik ezt a célpontot, akkor kapunk egy “lépéstávolság” értéket, ami jól jellemzi és összehasonlíthatóvá teszi a manócsoportok erőviszonyait.

Hogyan lehet ezt megoldani, hiszen egy torzított táblát használunk? Legjobb, ha lerajzoljuk. Az ábrán látható, a pálya, a manónk és a számára elérhető pozíciók. Természetesen csak a fehér területekre tud lépni, ha nincsenek letiltva. A cellákban látható számok azt az értéket mutatják, hogy a manónak hány lépésre van szüksége a számozott cella eléréséhez. A távolságok nem túl triviális képet mutatnak, de geometriai jellegzetességük miatt matematikailag megfoghatóak. Nem érdemes kódtáblát készíteni.

A problémát az okozza, hogy függőleges irányba haladva a lépéstávolság megegyezik az y különbség értékével, viszont vízszintes irányban haladva a lépéstávolság pont kétszerese az x különbségnek. Ha a manó körüli pályát diagonális irányban felbontjuk, akkor láthatjuk, hogy a diagonál által letakart cellák és a felső és alsó negyedben a lépéstávolság megegyezik az y különbséggel függetlenül az x különbségtől. Ha viszont a maradék területet nézzük, arra jöttem rá, hogy az így elérhető cella az x és y különbség összegének fele.

Tehát, ha a célterület a diagonálon van, vagy az fölötti-alatti negyed, akkor a

táv_i = abs( y_manó - y_cél )

egyébként:

táv_i = abs( x_manó - x_cél ) + abs( y_manó – y_cél ) / 2

//a virtuális táblán milyen közel vannak a 'szam' manoi a célhoz?

public int reltav(int[][] tablak,int szam){

int tav=0,xx,yy;

for(int j=0;j<9;j++){

for(int i=0;i<14;i++){

if(tablak[i][j]==szam+1){

//kivonom az aktuális helyzetből a célpozició koordinátáit -> távolság

xx=Math.abs(i-endx[szam]);

yy=Math.abs(j-endy[szam]);

if (xx>yy){tav+=(xx+yy)/2;}else{tav+=yy;} }

}

}

return tav;

}

Egy kicsit előre gondolkodva az ehhez szükséges rutint paraméteresen oldottam meg, hogy bármilyen felállású tábla és manócsoport lépéstávolsága kiszámítható legyen.

Ezt az elvet, rutint később jól feltudjuk használni.

2. Beértünk-e?

• Letároljuk a 6 manó elhelyezkedési variációit a “célterület” koordinátáival. Ha a játékállásból generált vektor megegyezik a tárolt vektorok valamelyikével, akkor bent vannak. Ez egy kissé idő és tárigényes feladat, ráadásul külön algoritmus kell az ellenőrző tábla generálására. Ezt a megoldás nem gazdaságos.
• Egy jóval egyszerűbb megoldás, hogy a célterület koordinátáit minden lépés után pásztázzuk, és ha az összes koordinátán csak a hozzá tartozó manók vannak, akkor ezek beértek. Ez már jó megoldásnak tűnik, de csoportonként 6 koordinátát kell eltárolnunk és ellenőriznünk.
• Én inkább kihasználva a az előbb tárgyalt “távolság” elméletet vettem segítségül, mivel ezt később a pálya átalakítása, vagy játékosok számának növelése esetén könnyebben változtatható. Az elve a következő: ha a kijelölt terület legtávolabbi sarkát vesszük, és megnézzük minden manó x, y távolságát ettől a saroktól. Ha az dy<=2 vagy dx+dy<=4 akkor ez a manó már biztosan a célterületen van. A pálya adottságait kihasználva ez mindegyik manócsoportra hatékonyan használható, csoportonként 1 koordináta megadásával.

1. Ellenfél, a stratégia

Programozói szemmel ez a legnehezebb része a játékprogramoknak. ( a grafikát és a designt a megfelelő szakemberekre hagyva ) Mondhatnám úgy is, hogy ez a lelke a játéknak. Hiszen egyfajta szellemi vetélkedésre, küzdelemre készteti a humanoid ellenfelét. Ellenfél készítése igen magas szintű jártasságot igényel a játékban. Ezen felül komoly elemzési képességek is elengedhetetlenek. Természetesen ez a szint játékoktól függően igen tág skálán mozog, hiszen nem a azonos tudásszintet követel egy tick-tack-toe nevezetű játék vagy a sakk ellenfél algoritmus elkészítése.

 

1. Mi az elérendő cél?

Ezzel a játékprogrammal jól demonstrálható egy ellenfél stratégia kialakítása, hiszen lépésről lépésre változnak a lehetőségek, erőviszonyok. A lépéskombinációk nem bonyolultak, de nem alkalmazható előre legyártott lépéssor. Valódi küzdelem folyik, bár nincs leütés a játékban. A cél a saját és az ellenfél manóinak felhasználásával a leggyorsabban a túloldalra jutni és ott elfoglalni a helyünket. Azaz minél kissebre csökkenteni az előzőekben tárgyalt távolságot.

2. Memória vagy gondolkodás?

Felvetődik a kérdés, hogy milyen stratégiát válasszunk. Képezzük az összes lehetséges lépéskombinációt és abból szűrjük le a biztos nyerő, vagy előnyt megtartó lépéseket, vagy minden lépésnél használjunk egy optimális lépést kiszámító algoritmust?

Nézzük az első felvetést. Ha le akarnánk tárolni az összes lépéslehetőséget és az ezekhez tartozó “nyerési” indexet mondjuk egy fastruktúrában, akkor mekkora tárolóra is lenne szükségünk? Egy pályaállás eltárolására minimum 7x9=63 byte szükséges. 3x6=18 manó van a pályán ami 37 mezőből áll. Egyszerűség kedvéért színfüggetlen manókkal számolok ( ennél több lenne, ha megkülönböztetném őket ).

lépésállás, amit még meg kell szoroznunk a mátrix méretével azaz 63 byte-al. Tehát több mint 1.113.375.872.700 byte ami 1 Terrabyte fölötti érték. Ez a tárolóhely igény mintha sok lenne egy játéknak.

Lehet-e egyszerűsíteni? Ha kiszedjük azokat a pályaállásokat, amelyek számunkra nem optimálisak ( ezek olyan állások, amelyek kívül esnek egy paralerogramma által meghatározható előnyös útvonalon ). Ezzel se sok memóriát nyerünk, viszont a lebutított program nem tudna mit kezdeni az előbb elvetett állások esetén. Konklúzió: a lépéstárolás értelmetlenné válik a nagy variációk száma miatt.

Mi lenne, ha megkeresnénk ( feltéve hogy létezik ilyen ) a nyerő és legoptimálisabb lépésállásokat, kombinációkat és csak ésszerű mennyiséget kiszelektálva tárolnánk el. A program megpróbálná ráilleszteni a tárolt lépéseket az épen aktuális állásokra és ha egyeznek akkor annak megfelelően lépi a következő kombinációt, ellenkező esetben pedig megpróbál egy optimális lépést találni valamilyen algoritmus alapján, akár úgy, hogy közelebb kerüljön egy tárolt álláshoz.

Ezzel az elmélettel az a gond, ami az előbb is problémát okozott, hogy a nyerő vagy optimális állasok, kombinációk megkereséséhez iszonyatos memória igény szükséges. Bár, ha már elkészült egy ilyen lépéskombinációs táblázatlista, annak már nincs túl nagy mérete.

Ha egy ilyen játék pár száz kilobyte feletti mérettel rendelkezik, akkor nehézkessé válik a használata, főleg internetes közegben.

Mi lenne, ha ezeket a lépéskombinációkat nem tárolt táblázatok alapján, hanem manó-lépéspozíció párokkal fastruktúrában kezelve, mélységi útkereséssel játszanánk végig az összes lehetőséget, és csak a nyerő lépéssorozatokat tárolnánk el. Nos ez a megoldás sem túl kecsegtető, hiszen az előbbi riasztó számok itt is megjelennek műveleti számban is.

Lehet-e realtime algoritmust használni? Úgy tűnik nem maradt más hátra csak ez a lehetőség. Muszáj valamilyen egyszerű vagy bonyolult valósidejű, az aktuális állást elemző és ez alapján lépő algoritmus megalkotása. “Tanítsuk meg gondolkodni a programot!”

3. Lépéslehetőségek keresése, mohó algoritmus

• Az első, a gép azonos állásoknál mindig ugyan azt a lépést lépte, tehát kiszámíthatóvá válik. Ez hosszú távon unalmassá teszi a játékot. Mit lehet tenni ez ellen?

• A másik amin javítani lehetne, hogy a mohó algoritmus önmaga egy lokális optimumot keres. Tehát globálisan létezik jobb lépés is, de nem ezt keresi. Mit jelent az, hogy globálisan jobb? A cél úgy fogalmazható meg egyszerűen, hogy ne csak az aktuális lépésre figyeljen, hanem előbbre, lépéskombinációkban “gondolkodjon”.

1. Rekurzív algoritmus

• Az 1 lépéses rutinnak átlagosan 14,7 lépés kellett a nyeréshez, ez 10 és 21 közötti lépésszám.
• A 2 lépéses rekurziónak átlagosan 12,3 lépés kellett ami sokkal jobb eredmény, de érdekes a 8 és 23 közötti lépésszámból a 23, ami azt sejteti, hogy túlkombinálták egymást.
• A 3 lépéses rekurziónak pedig átlagosan 14,9 lépés kellett 11 és 21 közötti lépésszámmal, és exponenciálisan megnőtt lépésidővel. Amint látható most romlott a nyeréshez szükséges átlag lépésszám, ami azzal magyarázható, hogy egy lépést kiszámítani és meglépni 100% biztonságú, amíg egy kétlépéses számolás második lépésébe már beleszólhat a másik két játékos lépése, de három lépésnél már a harmadik lépést szinte biztosan keresztül húzza a másik két játékos körönkénti lépése. Ezért nem is érdemes további ismétlésszámokkal próbálkozni.

1. További lehetőségek?

Elemezve tovább az emberi gondolkodás stratégiáját, még lehet trükköket beépíteni az ellenfelet szimuláló programba. Most a program a saját előrejutását keresi minél hatékonyabb módon. Egy emberi ellenfél nemcsak ilyen pozitív gondolkodást képvisel, hanem a lépéseibe belekalkulálja azt is, hogyha teheti akadályozza az ellenfelét. Tehát továbbfejlesztve a programot, azt is meg lehet oldani, hogy nem csak a saját manóknak keresi a legjobb lépést, hanem az ellenfél válaszreakcióit is kiszámítja és ezek után választja ki a számára legkedvezőbb, de az ellenfél részére minél kedvezőtlenebb lépést.

Rá lehet hangolni a programot, hogy megkülönböztesse a biztos és a bizonytalan lépéskombinációkat, hiszen vannak olyan ugrássorok, amelyek több útvonalon is elérhetők, tehát az ellenfél lépése után is nagyobb eséllyel léphetők meg.

2. Tesztelés

Lépéskör	Piros 1 szint	Fehér 1 szint	Zöld 1 szint	Nyerő lépések
10000	3336	3372	3292	14,7

Lépéskör	Piros 2 szint	Fehér 2 szint	Zöld 2 szint	Nyerő lépések
10000	3392	3313	3295	12,3

Lépéskör	Piros 3 szint	Fehér 3 szint	Zöld 3 szint	Nyerő lépések
10000	3656	3341	3003	14,9

Lépéskör	Piros 1 szint	Fehér 2 szint	Zöld 3 szint	Nyerő lépések
10000

Lépéskör	Piros 1 szint	Fehér 2 szint	Zöld 1 szint	Nyerő lépések
10000	2833	4453	2714	13,5

1. Grafika

• a funkciógombok elkülönüljenek a “játéktértől”
• a gombok árulkodóak legyenek
• a különböző csoportba tartozó manók jól elkülöníthetőek legyenek
• a pálya mezői ( rácspontjai ) könnyen megtalálhatóak legyenek
• egyértelmű eredmény és “ki következik” kijelzés
• gyors és villogásmentes megjelenítés

1. Kezelőfelületek és egyéb rutinok

• beállítható a játékosok száma 2 vagy 3-ra
• megadható, hogy az egyes csoportok emberi ( kézi mozgatással ) vagy gépi irányítással játszanak és ezen belül milyen szinten játsszon a gép.
• kiválasztható a kezdő játékos, de lehet olyan beállítás is, ahol a gép véletlenszerűen dönti el, hogy ki lesz a kezdő.
• látható még egy csúszka, ami a gép lépések közötti késleltetést állítja be, ezzel gyors játékot vagy jobban észlelhető lépéseket hangolhatjuk.
• és természetesen egy start gomb amivel a beállításokat érvényesítjük és elkezdhetjük a játékot.

• “Új játék” Amint a neve is mutatja megszakíthatjuk az éppen futó játszmát vagy a lejátszott menet után egy újat kezdhetünk.
• “Beállítás” Ezzel a gombbal lehet megjeleníteni a beállítás kezelő panelt.
• “Géplép” Itt lehet egy a programmal kalkulált lépést kérni. Segíthet dönteni, de jó szolgálatot tesz tesztelés során.
• “Távolság” Kiírja a JAVA-konzolra a manócsoportok aktuális lépéstávolságát.
• “Tábla” Tesztkijelzés a tabla tárolóról a menet közbeni változások ellenőrzése érdekében.

1. A program életciklusa

1. Mellékletek

1. Rendszer igények

A programot JAVA nyelven írtam, ami platformfüggetlen. Internetről a böngészők segítségével is futtatható. Alkalmas internetes játék, tovább fejlesztve egymás elleni küzdelmekre is. Cél volt, hogy mérete ne legyen túl nagy és ne okozzon gondot a különböző operációs rendszereknek vagy a böngészőknek. A játék egyaránt futtatható internetről és lokális gépről is.

A futtatáshoz szükséges fileok:

A fő JAVA program Jump.class 11.895 byte

A Canvas JAVA program Mano.class 4.144 byte

A háttér képe hatter.gif 26.959 byte

Három színű manók piros.gif 295 byte

feher.gif 289 byte

zold.gif 285 byte

A manók mosolya mosoly.gif 73 byte

Négy darab jel jel0..4.gif 275 byte

---

HTML oldal index.html 225 byte

Összesen 44.550 byte

Ez a méret internetes letöltés esetén sem jelentős, kb. 9 mp alatt letölti egy 56 kb/s-os modem.

A program JAVA 1.02 implementációt és annak engedélyezését igényli, ami ma már minden újabb verziójú böngészőben megtalálható. Internet Explorer 3 vagy nagyobb Netscape Navigátor 3 vagy nagyobb.

Természetesen ha internetről szeretnénk használni, akkor internet csatlakozás is szükséges.

 

3. Ábrák a gépi lépés szemléltetésére

M1. Ábra

 

 

M2. Ábra

M3. Ábra

M4. ábra

M5. ábra

M6. Ábra

M7. ábra

M8. ábra

 

 

 

 

 

 

 

 

M9. ábra



M10. ábra

M11. ábra

 



M12. ábra

 

 

 

 

 

 

5. Irodalomjegyzék

Boruzs – Jacsmerik: Nagy játék könyv Kheirón ’97 Kiadó 2000

A racionális gondolkodás korlátai és a mesterséges intelligencia

Varga Balázs Játékkoktél Minerva 1967

Lukácsy András Népek játékai Móra Könyvkiadó 1964

COGITORG kft Táblás játékok Internet 2001