Az S. 27. feladat (2007. május)

S. 27. Írjunk programot, amely a páros aknakereső játékban egy tetszőleges állásban lépést javasol.

A játék egy N×M-es táblán folyik, amelynek mezőin K db akna van elrejtve (egy mezőn legfeljebb csak egy). Kezdetben az összes mező felderítetlen. A játék során a két játékos felváltva választ egy-egy, még felderítetlen mezőt. Ha a kiválasztott mező aknát rejt, a játékos 1 pontot szerez, és újból választhat. Ellenkező esetben megtudjuk, hogy a kiválasztottal szomszédos 8 mező közül összesen hány rejt aknát - ez egy 0 és 8 közötti egész szám -, és a másik játékos következik. Kivételt képez az az eset, amikor a játékos olyan (aknamentes) mezőt derít fel, amely körül egy akna sincs, ugyanis ekkor az összes szomszédos mező is felfedésre kerül, illetve ha így olyan mező kerül felfedésre, amely körül szintén nincs egy akna sem, az eljárás rekurzívan ismétlődik. Természetesen ezután ebben az esetben is a másik játékos következik.

A játék végeztével, azaz az összes akna megtalálása után, az nyer, akinek több pontja van.

A program az aktuális játékállást a standard bemenetről olvassa. A bemenet első sorában három egész szám szerepel: a tábla N szélessége és M magassága, továbbá az elrejtett aknák K száma, egy-egy szóközzel elválasztva. Az ezt követő M sor mindegyike N karaktert tartalmaz: a bemenet (i+1)-edik sorának j-edik karaktere a játéktábla i-edik sorának és j-edik oszlopának kereszteződésében lévő mezőt írja le. Ez

- pont (.), ha a mező még federítetlen

- csillag (*), ha a mezőt már felderítette valamelyik játékos, és aknát tartalmaz

- 0 és 8 közötti számjegy, ha a mező már felderített, de nem rejtett aknát (ekkor ez az érték a mező szomszédságában lévő aknák száma).

A program a javasolt lépést - 10 másodpercen belül - a standard kimenetre írja. Ennek egyetlen sorában két, szóközzel elválasztott egész szám szerepeljen: a felderítendő mező X oszlop- és Y sorindexe (1XN, 1YM).

A működőképes megoldások között körmérkőzést rendezünk. A programok 10-20 játékból álló csoportokban mérik össze tudásukat, a csoport győztese az a program, amely a játékok legalább 2/3 részét nyeri. Ha ezt az arányt egyik program sem éri el, a csoport eredménye döntetlen. Mérkőzésenként a győztes 3 pontot kap, döntetlen esetén pedig mindkét játékos 1-1-et. A megoldásokat az így kialakult pontszám alapján rangsoroljuk, az első helyezett (megfelelő dokumentáció esetén) 10 pontot, a második 8-at, a többi megoldás legfeljebb 7 pontot kaphat. Kis különbségek esetén az első, illetve második helyen több megoldás is végezhet.

Feltehetjük, hogy a program bemenetére kizárólag helyes játékállás érkezik, továbbá, hogy N,M100.

Beküldendő a program forráskódja (s27.pas, s27.cpp, ... és dokumentációja).

(10 pont)

A beküldési határidő 2007. június 15-én LEJÁRT.

A megoldás menete

A feladat megoldására sok lehetőség kínálkozott, minden esetben a jó megoldás kulcsa az aknák hatékony megtalálása (támadás), illetve ennek eredménytelensége esetén a megfelelő védekezés volt.

Az aknák megtalálására egy kézenfekvő módszer, hogy sorra megvizsgáljuk a számot tartalmazó mezőket, és ha egy ilyen mezőbe írt számérték mínusz a szomszédos aknák száma megegyezik a szomszédos felfedezetlen mezők számával, úgy azok mind aknát rejtenek. Fordítva, ha a számérték a szomszédos aknák számával egyezik meg, úgy minden szomszédos ismeretlen mező aknamentes. Előbbi esetben találtunk egy aknát, utóbbi esetben az újonnan megszerzett információkkal az eljárást újraindíthatjuk.

A módszer előnye, hogy a mezők számával egyenesen arányos időben elvégezhető, ugyanakkor hátránya, hogy nem mindig vezet eredményre.

A hatékonyabb módszerek a problémát olyan lineáris egyenletrendszernek tekintik, ahol a változók (egy ismeretlen mezőn van-e akna), s együtthatóik csak 0/1 értéket vehetnek fel, és minden 'számos' mezőhöz tartozik egy egyenlet, melynek egyik oldalán a szám, másik oldalán 1-együtthatókkal pedig a környező ismeretlen mezők változói szerepelnek. Ezen egyenletrendszer megoldását keressük, illetve, ha az nem egyértelmű, az összes megoldás alapján az egyes mezőkre akna-valószínűségeket határozhatunk meg.

A védekezés akkor kerül előtérbe, amikor nem tudunk biztos aknát mondani, és a valószínűségek is alacsonyak. Célunk, hogy semmiképp se válasszunk nullás mezőt, hiszen ekkor nagy előnyhöz juthat az ellenfél. Itt az alapgondolat, hogy először megpróbálunk egy akna melletti, viszonylag nagy valószínűségű mezőt találni, ha ilyen nincs, akkor szimplán egy akna melletti mezőt, illetve, ha ilyen sincs, akkor véletlenszerűen választhatunk.

A megoldások értékelése

A programok 20x20, 20x100, ill. 100x100 méretű, 10% és 47,5% közti aknasűrűségű mezőkön mérkőztek meg, minden pályán kétszer, egyszer az egyik, egyszer a másik kezdett. Így két program közt összesen 48 különböző pályán 96 mérkőzés zajlott le. Kezes Balázs és Györök Péter jól megoldották a feladatot. Mindkét program - további kiegészítésekkel - az első aknakereső módszerre épült, és tartalmazott védekező logikát is. Györök Péter programja a védekezésben, Kezes Balázs programja pedig a támadásban volt jobb. A ritkás pályákon rendre előbbi, a sűrűbbeken pedig rendre utóbbi győzedelmeskedett, a két nagy pályaméreten a határ olyan éles volt, hogy 30-32.5% sűrűség alatt, illetve felett rendre az egyik, illetve a másik nyert minden fordulót. A végeredmény 53 : 43 (55% : 45%) lett Györök Péter javára, így a feladatkiírás szerint mindkét versenyző munkáját 10 ponttal jutalmaztuk.

Mintamegoldásként letölthető Györök Péter megoldása: s27.zip

Statisztika:

2 dolgozat érkezett.
10 pontot kapott:	Györök Péter, Kezes Balázs.

A KöMaL 2007. májusi informatika feladatai