Aknakereső számítógépes játék (Minesweeper)

 

Az aknakereső egy népszerű egyszemélyes logikai játék, amely szinte minden mai személyi számítógépen megtalálható. A játék első változatai a 80-as évek elején jelentek meg, ma ismert formájában 1990-ben, a Microsoft cég Windows Entertainment Pack nevű játékgyűjteményének részeként látott napvilágot. A játék (a pasziánsszal egyetemben) a Windows 3.1 kiadása óta része az operációs rendszernek, így felhasználók milliói játsszák rendszeresen. A legtöbb számítógépes játékkal ellentétben az aknakereső során a játékosnak sokkal inkább az eszére, semmint ügyességére kell hagyatkoznia. A játék elé egyszerű ahhoz, hogy könnyedén meg lehessen érteni a szabályokat, ugyanakkor elég komplex ahhoz, hogy ne váljon gyorsan unalmassá. A későbbiekben látni fogjuk, hogy a játék még egy számítógép számára is kellően bonyolult, jelenleg nem ismert hatékony algoritmus, amely képes lenne hibátlanul megoldani minden aknakereső-táblát.

 

A játékot (alapvetően) egy személy játssza egy téglalap alakú, cellákra osztott pályán. A játék elején a számítógép előre megadott számú aknát helyez el véletlenszerűen kiválasztott cellákban, a játékos elől elrejtve. A játékos ezután bármelyik cellára rákattinthat. Ha a kiválasztott cellán akna van, a játékos vesztett, ellenkező esetben a gép ráírja a cellára, hogy a vele közvetlenül szomszédos 8 cella közül pontosan hányon van akna. A játékos a kapott információk alapján ismét kattint, és ez így megy addig, amíg egyszer vagy aknára nem kattint, vagy fel nem fedi az összes aknamentes mezőt.

A játéknak van egy kétszemélyes változata is, amely leginkább az MSN Messenger szoftverbe épített kliens által ismert. Ebben a változatban ellentétes a cél: a játékosoknak az aknamentes mezők helyett az aknákra kell kattintaniuk. Ha valaki eltalál egyet, újra ő jön; ha nem aknára kattint, a másik játékos használhatja fel a kattintás során szerzett új információkat az aknák keresésére. A két játékmód között alapvető különbségek vannak – míg egyjátékos módban csak arra kell ügyelnünk, hogy nem biztos kattintás esetén minél nagyobb valószínűséggel kattintsunk aknamentes mezőre, két játékos esetén azt is figyelembe kell vennünk, hogy minél kevesebb információt szolgáltassunk a másik játékosnak.

 

Ha matematikai szempontból vizsgáljuk a játékot, az alábbi kérdések merülhetnek fel egy adott játékállapottal kapcsolatban:

·        Konzisztens-e ez az állapot, azaz van-e olyan aknaelrendezés, ami nem mond ellent a már ismert adatoknak?

·        Mely mezők azok, amelyeken biztosan van akna?

·        Mely mezők azok, amelyeken biztosan nincs akna?

·        Az előző két kategória egyikébe sem tartozó mezők mekkora valószínűséggel tartalmaznak aknát, ha minden lehetséges aknaelrendezést azonos valószínűségűnek tekintünk?

 

A későbbi tárgyalás egyszerűsítése érdekében vezessük be az alábbi kifejezéseket:

·        biztonságos mező: olyan mező, amiről biztosan tudjuk, hogy nincs rajta akna

·        megjelölt mező: olyan mező, amelyről biztosan tudjuk, hogy van rajta akna

·        mező aknaszáma: egy mező aknaszáma azt fejezik ki, hogy hány vele szomszédos mezőn van akna

·        felfedett mező: olyan (biztonságos) mező, amelynek ismerjük az aknaszámát

·        üres mező: nem biztonságos és nem megjelölt mező

·        telített mező: olyan mező, aminek aknaszámával megegyező számú megjelölt szomszédja van

 

A későbbiekben látni fogjuk, hogy a játék által felvetett problémák még egy számítógép számára is meglehetősen bonyolultak. Van azonban pár stratégia, amelyek alkalmazásával emberi játékosok is meg tudnak oldani különböző állásokat.

Az egyik legegyszerűbb ilyen a „fennmaradó helyek” stratégiája: ha egy mezőnek pontosan annyi üres szomszédja van, mint amekkora az aknaszámának és a vele szomszédos megjelölt mezők számának különbsége, akkor az összes fel nem fedett szomszédján akna van, így azok megjelölt mezőkké válnak. Hasonlóan egyszerű stratégia az, hogy egy telített mező összes üres szomszédja biztonságossá tehető (és felfedhető), mert a telített mezőnek már az összes szomszédos aknáját felderítettük. A harmadik, legegyszerűbb stratégia az, hogy egy 0 aknaszámú mező minden szomszédja biztonságos, így felfedhetjük őket. (Ezt a stratégiát a játék tipikus implementációi automatikusan megvalósítják, ezért lehetséges az, hogy egyetlen kattintással több mezőt is felfedjünk egyszerre.)

Az előbb vázolt két (illetve három) stratégia igen hasznos, hiszen egy csomó következtetést levonhatunk gondolkodás nélkül. Ráadásul a második stratégia segítségével nagy mennyiségű új mezőt felfedhetünk, amelyekre újra alkalmazható az első stratégia... Ám nagyon hamar belefutunk egy olyan helyzetbe, amikor már nem segítenek ezek a módszerek. Ilyenkor jönnek jól a különböző ismert minták.

 

Az első minta, amivel megismerkedünk, az 1-1 minta:

 

1. Az 1-1 minta

 

Az első ábra bal oldalán kérdőjellel jelölt mezők aknaszáma lényegtelen, a lényeg csak az, hogy biztonságos mezők. (Az is előfordulhat, hogy a tábla szélén találjuk meg a mintát, így a ?-es mezők hiányoznak.) Ha valahol meglátjuk a fenti mintát, levonhatjuk a következtetést, hogy a bal oldali 1-es miatt a sárga hátterű mezők közül pontosan egyen van akna. Bármelyik mezőn is van az akna, az telítetté teszi a jobb oldali 1-est, így a minta alapján levonható a következtetés, hogy az ábra jobb oldalán (újonnan) kérdőjellel jelölt mező biztonságos. (Sőt, a jobb oldali 1-es összes eddig üres szomszédja is biztonságosnak minősíthető. Azért épp a kérdőjellel jelöltet emeltem ki, mert a mintát legtöbbször felfedett mezők összefüggő tartományainak egyenes határán szoktuk alkalmazni.)

 

A másik alapminta az 1-2 minta:

 

2. Az 1-2 minta

 

A gondolatmenet hasonló: a két sárgával jelölt mező közül legfeljebb az egyiken van akna (az 1-es miatt). Levonható következtetésként, hogy a csillaggal jelölt mezőn biztosan akna van, így azt meg kell jelölnünk. Mivel a 2-es aknaszámú mező szomszédságában kell lennie még egy aknának, kimondhatjuk, hogy a sárga mezőkön pontosan egy akna van. Ettől viszont az 1-es mező telítetté válik, így (többek között) a jobb oldali ábrán kérdőjellel jelölt mezőről megállapíthatjuk, hogy biztonságos.

Az 1-2 minta kétszeri alkalmazásával keletkezik az egyik leghíresebb minta, az 1-2-1 minta (a két mintaillesztés után még egy telítésellenőrzést is végzünk a 2-es mezőre):

 

3. Az 1-2-1 minta

 

A másik híres minta az 1-2-2-1 minta (itt is észrevesszük, hogy a 2-es mezők telítettek):

 

4. Az 1-2-2-1 minta

 

Ezzel a néhány mintával (főleg az utolsó kettővel) már meglehetősen jó eredményeket lehet elérni. Álljon itt egy példa! Néhány kattintás után az 5. ábrán látható állapotba jutottam egy aknakereső-játszma során.

 

5. Kiindulási állapot, 1-1 minta

 

6. Újabb 1-1 minta

 

7. Wddigi információ

 

8. A „rejtett” 1-2-2-1 minta

 

9. Újabb információk

 

10. A játék vége

 

A 5. ábrán sárgával jelölt mezőkön felismertem egy 1-1 mintát, amiből következően a 6. ábrán kérdőjellel jelölt mezőről megállapítottam, hogy biztonságos. Ekkor újabb 1-1 mintát találtam, amiből a 7. ábrán látható következtetést vonhattam le. Első pillantásra itt nem találtam semmit, ezért felfedtem a korábban biztonságosnak minősített mezőket. Ez látható a 8. ábrán. Ekkor vettem észre egy „rejtett” 1-2-2-1 mintát (a 8. ábrán zölddel jelölve): ha a zölddel jelölt mezők aknaszámából levonjuk a már megtalált aknaszomszédok számát, épp egy 1-2-2-1 mintát kapunk, így az 9. ábrán látható következtetéseket vontam le. Ezután felnyitottam a kérdőjeles mezőket, és kizárólag a két alapstratégia (fennmaradó helyek és telítettség vizsgálata) segítségével megoldottam a feladványt. (10. ábra)

Ennek a néhány mintának az alkalmazása igen hatékony tud lenni, ám közel sem old meg minden problémát, amivel szembekerülünk. Vannak olyan esetek, amikor egyszerűen nem lehet eldönteni, hol van az akna (ilyenkor nincs mit tenni, tippelnünk kell), és van, amikor ötletesebb, gondolkodósabb módszereket kell alkalmazni. Ezek azonban bonyolultabbak annál, hogy egy ilyen esszében könnyedén leírhatóak legyenek, és sokszor nem is eléggé „megfoghatóak”, mert csak a tapasztalt játékosok fejében léteznek.

 

Az emberi játékosok stratégiáiról térjünk most át arra, mihez kezdhet egy program egy aknakereső-táblával! Ehhez először a számítástudomány egyik fontos fogalmát kell megismernünk.

 

Az NP problémák az eldöntési problémák (olyan problémák, amelyekre egyetlen igen/nem válasz adható) egy igen érdekes és fontos osztályát alkotják. Az ebbe az osztályba tartozó problémák egy részének megoldására ugyan jelenleg nem ismert polinomiális idejű algoritmus, ám mindegyikhez létezik „pozitív tanú” algoritmus, azaz olyan polinomiális algoritmus, amely egy megfelelő „bizonyíték” alapján az „igen” választ ellenőrizni tudja. Példa erre a Hamilton-kör létezésének problémája: jelenleg nem ismert polinomiális idejű algoritmus annak meghatározására, hogy van-e egy gráfban Hamilton-kör, de egy konkrét Hamilton-kört bizonyítéknak használva polinomiális időben ellenőrizhető, hogy az tényleg kielégíti a feltételeket. Igen sok fontos NP-beli probléma van, ezek közé tartozik a már említett Hamilton-kör létezésének problémája, ill. például annak vizsgálata, hogy egy gráfban létezik-e k elemű független ponthalmaz.

Az NP-beli problémák egy kitüntetett csoportját alkotják az ún. NP-teljes problémák. Ezek olyan NP problémák, amelyekre bármelyik másik NP probléma polinomiálisan visszavezethető. Emiatt, ha valakinek valaha sikerül polinomiális idejű algoritmust adni egy NP-teljes probléma megoldására, azzal egy csapásra polinomiális időben megoldhatóvá teszi az összes NP-beli problémát. Az amerikai Clay intézet 2000-ben egymillió dolláros díjat tűzött ki annak, aki megold egy NP-teljes problémát polinomiális időben, vagy bebizonyítja, hogy ez lehetetlen.

 

 

Richard Kaye 2000-ben bebizonyította, hogy egy aknakereső-tábla konzisztenciájának ellenőrzése NP-teljes. A bizonyítás során egy ismerten NP-teljes problémát, az ún. SAT problémát (egy logikai formula kielégíthetőségének vizsgálata) vezette vissza az aknakereső-tábla konzisztenciájára. A visszavezetés során a kielégítendő logikai kifejezést először logikai áramkörré alakítjuk, majd az egyes komponenseket (kapuk, vezetékek, vezeték-metszések, kanyarok) megfelelő aknakereső-táblarészletekkel helyettesítjük. Ha az aknakereső-áramkört ki tudjuk tölteni aknákkal úgy, hogy a „kimenetén”, azaz egy megjelölt mezőben igaz érték (azaz akna) legyen, és a kitöltés ellentmondásmentes, akkor a logikai formula kielégíthető. Ha viszont az aknakereső-áramkör nem tölthető ki, akkor inkonzisztencia van jelen, tehát nem kielégíthető az eredeti logikai formula.

A bizonyítás alapvető irányvonalai után lássuk az egyes ekvivalenseket!

 

Az első alkatrész, amire szükségünk van, az egyenes (vízszintes) vezeték:

 

11. Vezeték

 

Látható, hogy a kék pöttyel jelölt „kimeneten” akkor és csak akkor van akna, ha a pirossal jelölt bemeneten akna van.

Részletesebb magyarázattal az alábbi ábra szolgál:

 

12. Vezeték működése

 

Ha a legbaloldalibb kérdéses négyzeten akna van, akkor a mellette lévőn biztosan nincs, mert különben a pirossal jelölt 1-esnek túl sok akna szomszédja lenne. Hasonlóan, ha nincs ott akna, akkor a szomszédján kell lennie. Azaz a két mező „akna-állapota” épp ellentétes: ha az egyiken akna van, akkor a másikon nincs, és fordítva. Ezt úgy jelöljük, hogy az egyik mezőbe „A”-t, a másikba „a”-t írunk. Ezt a jelölést a továbbiakban is használni fogjuk: a kis- és nagybetűk mindig ellentétes állapotú mezőket jelölnek, a különböző betűk pedig független mezőket. Az ábrát tovább töltve láthatjuk, hogy a vezeték két végén tényleg ugyanolyan állapotú mezők vannak.

Mivel időnként minden kapcsolási rajzban meg kell törnünk a vezetéket, szükségünk van „kanyar” elemre is, azaz olyan elemre, amihez egy vízszintes és egy függőleges vezeték csatlakoztatható, és a kimenetén ugyanaz az érték jelenik meg, mint a bemenetén. Egy lehetséges megvalósítás látható a 13. ábrán.

 

13. Kanyar elem

 

Előfordulhat, hogy felesleges vezetékvégek vannak az ábrán, amiket le kell zárni. A 14. ábrán látható összeállítás pirossal jelölt bemenetén mindegy, hogy van-e akna, mindkét esetben érvényes, ellentmondásmentes állapotot kapunk, így használható a szabad vezetékvégek

 

14. Vezetékek lezárása

 

lezárására.

 

Szükségünk lehet arra is, hogy egy jelet két-, vagy akár háromfelé osszunk, erre nyújt lehetőséget a 15. ábrán látható „splitter” elem (ha csak kétfelé akarunk ágazni, az előbb bevezetett lezáró elemmel megoldhatjuk a problémát).

 

15. Splitter

 

Kapcsolási rajzokon előfordul, hogy két vezeték metszi egymást, ennek megoldására a 16. ábrán látható táblarészletet használhatjuk fel. Látható, hogy a piros körrel jelölt bemenet értéke a kék körrel jelölt kimenetre kerül, a piros négyzettel jelölt a kék négyzettel jelöltre, egymástól függetlenül.

 

16. Két vezeték metszéspontja

 

Az utolsó szükséges, és egyben legbonyolultabb áramköri elem a NOR (nem-vagy, sem-sem) kapu, aminek a megvalósítása a 17. ábrán látható (pirossal jelölve a bemenetek, kékkel a kimenet). A működés bizonyításához végezzük el az áramkör analízisét (egyelőre pár új ismeretlent bevezetve)! A NOR kapu elvi igazságtáblája a 19. ábrán látható.

 

17. NOR kapu megvalósítása

 

18. NOR kapu elemzése

 

 

19. NOR kapu igazságtáblája

 

Vizsgáljuk meg, milyen következtetéseket vonhatunk le, ha a két bemeneten „hamis” logikai értéket adunk az áramkörre, azaz ha az A-val és B-vel jelölt mezőkön nincs akna, az a-val és b-vel jelölteken pedig van! Ahhoz, hogy a 18. ábrán piros háttérrel megjelölt 4-es mellett 4 akna helyezkedjen el, muszáj, hogy a P-vel, Q-val és R-el jelölt mezőkön is legyen akna. A sárga hátterű 3-asok vizsgálatával könnyen belátható, hogy ekkor az y-nal és v-vel jelölt mezőkön lesznek még aknák, az u-val és x-szel jelölteken pedig nem lesznek, és a kapott állás ellentmondásmentes. Azt kaptuk tehát, hogy ha a két bemenet egyikén sincs „igaz” jel, akkor a kimeneten „igaz” jelet kapunk, tehát ebben az esetben a kapu jól működik.

 

Vizsgáljuk meg, milyen következtetést tudunk levonni abból, ha a kimenet „igaz” állapotú, azaz az R jelű mezőkön van, az r jelű mezőkön pedig nincs akna! Ebben az esetben a sárga hátterű 3-asokat megvizsgálva azt kapjuk, hogy a v-vel, Q-val, y-nal és P-vel jelölt mezőkön muszáj aknának lennie. A piros hátterű 4-est vizsgálva láthatjuk, hogy már „megvan” mind a négy aknája, így az A és B jelű mezőkön, azaz a bemeneteken semmiképpen sem lehet akna. Az u és x jelű mezőknek „hamis” (aknátlan) értéket adva egyértelmű, ellentmondásmentes állapotot kaptunk.

Az előző két bekezdés során kiderült, hogy ha a kapu bemenetére két „hamis” értéket kapcsolunk, akkor a kimenete „igaz” lesz, és ha a kimenet „igaz”, akkor a bemeneten biztosan két „hamis” érték van. Ennek a jellemzésnek a kétváltozós logikai függvények közül kizárólag a NOR felel meg, így az ábrán látható összeállítás valóban egy NOR kaput valósít meg.

 

Ismert, hogy NOR kapuk és vezetékek segítségével tetszőleges logikai függvényt megvalósító áramkör felépíthető. Ha a SAT problémában szereplő logikai függvényt megvalósítjuk egy áramkörrel, majd az áramkör egyes komponenseit az aknakereső-ekvivalenseikkel helyettesítjük, az áramkör bemeneteire „záró” áramkört, kimenetére pedig a 20. ábrán látható „konstans igaz” elemet tesszük, olyan aknakereső-táblát kapunk, amelynek konzisztenciája ekvivalens a logikai formula kielégíthetőségével. Mivel az ekvivalens generálása polinomiális ideig tart, és egy állítólag kielégítő aknaelrendezés ellenőrzése is polinom idejű, a probléma valóban NP-teljes.

 

20. Konstans igaz áramköri elem (ha a bemenetén nincs akna, ellentmondás jön létre)

 

Az aknakereső játék megoldása (azaz annak eldöntése, melyik mezőkön van biztosan akna, és melyikeken nincs biztosan) modellezhető kényszer-kielégítési problémaként (CSP, constraint satisfaction problem). Az ilyen problémák leírása során megadunk néhány változót, azok értékkészletét (lehetséges értékeit), valamint a változókra vonatkozó kényszereket. A feladat az, hogy meghatározzuk a változók összes olyan értékét, amelyek kielégítik a kényszereket.

Modellezzük az aknakereső játékot a következőképpen: a tábla i. sorának j. mezőjéhez rendeljünk egy x_ij változót, aminek értékkészlete a {0, 1} halmaz. A tábla minden mezőjére írjunk fel egy kényszert az alábbi módon:

 

·        ha az (i,j) mező biztonságos (vagy felfedett), vegyük fel az x_ij=0 kényszert

·        ha az (i,j) mező megjelölt, vegyük fel az x_ij=1 kényszert

·        ha az (i,j) mező felfedett, vegyünk fel egy olyan kényszert, ami a vele szomszédos üres és megjelölt mezőkhöz tartozó változók összegére előírja a mező aknaszámának értékét

 

Ha a kapott CSP-t kielégítő minden megoldásban x_ij=0, akkor az (i,j) mező biztosan biztonságos. Ha az összes megoldásban x_ij=1, akkor a mezőn biztosan akna van.

A következőkben bemutatok egy példát, hogy hogyan fogalmazhatunk át egy aknakereső-problémát CSP problémává. Tekintsük a 21. ábrán látható aknakereső-táblát!

 

21. Példajátszma CSP generálásához

 

Felírva a kényszereket (a triviális, x_ij=0 alakúakat kihagyva):

 

 

Mező	Kényszer
(1,5)	x16+x26=1
(2,5)	x16+x26+x36=2
(3,5)	x26+x36+x46=2
(4,5)	x36+x46+x56=1
(5,5)	x46+x56+x66+x65+x64=2
(5,4)	x63+x64+x65=2
(5,3)	x42+x52+x62+x63+x64=3
(4,3)	x42+x52=1
(3,3)	x42=1
(3,2)	x41+x42=1
(3,1)	x41+x42=1

 

Egy lehetséges megoldás lépései:

·        A (2,5) és (1,5) egyenletek különbségéből következik, hogy x₃₆=1, azaz (3,6) biztosan akna.

·        Az (5,5) és (5,4) egyenletek különbségéből következik, hogy x₄₆+x₅₆=0, és mivel minden változó pozitív, következik, hogy (4,6) és (5,6) biztonságos.

·        A (3,3) egyenletből következik, hogy (4,2) biztosan akna.

·        A (3,2) és (3,3) egyenletek különbségéből következik, hogy x₄₁=0, azaz (4,1) biztonságos.

·        A (4,3) és (3,3) egyenletek különbségéből következik, hogy x₅₂=0, azaz (5,2) biztonságos.

·        Tudjuk, hogy x₄₆=0 és x₃₆=1, így a (3,5) egyenlet alapján következik, hogy x₂₆=1, azaz (2,6) biztosan akna.

·        Az előző pontból és az (1,5) egyenletből következik, hogy x₁₆=0, azaz (1,6) biztonságos.

 

A korábbi következtetéseket grafikusan ábrázolva a 22. ábrán láthatók:

 

22. CSP megoldásának eredménye

 

A fenti típusú CSP problémák megoldására találhatunk módszereket az [5] cikkben, amely azt is bemutatja, hogyan lehet hatékonyan meghatározni a nem egyértelmű változók értékének valószínűségi eloszlását.

 

[1] Sean Berett: Minesweeper: Advanced Tactics (http://nothings.org/games/minesweeper/)

[2] Richard Kaye: Minesweeper is NP-complete. The Mathematical Intelligencer, 22(2):9–15, 2000.

[3] Richard Kaye's Minesweeper page (http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm)

[4] Minesweeper is NP-complete (http://sed.free.fr/complex/mines.html)

[5] Raphael Collet: Playing the Minesweeper with Constraints, Multiparadigm Programming in Mozart/Oz, Springer Lecture Notes in Computer Science, 2005, Volume 3389/2005, 251-262  (http://www.springerlink.com/content/l0cxhkuwv5edjpc0/fulltext.pdf)

 

Szerző: Peregi Tamás, BME