Žaidimas L figūromis

Taškai: 12

Bebrai Kikis ir Vivis žaidžia žaidimą: dėlioja L formos figūras 4×4 langelių lentoje. Figūros dedamos paeiliui pagal šias taisykles:
•    Kikis deda aukštyn apverstas L figūras (žr. paveikslo kairėje),
•    Vivis deda kairėn pasuktas L figūras (žr. paveikslo dešinėje),
•    dedama figūra turi visa tilpti ant lentos,
•    figūros negali dengti viena kitos.
Padėtų figūrų negalima nuimti. Žaidėjas pralaimi žaidimą, jei yra jo ėjimas, bet jis negali padėti figūros pagal taisykles. Pavyzdyje Kikis pradeda žaidimą ir gali laimėti, padėdamas figūrą apatiniame dešiniajame kampe.


Abu bebriukai žaidžia puikiai, t. y. pasirenka geriausius ėjimus.
Galimi 9 skirtingi Kikio pradiniai ėjimai. Kiek iš jų garantuoja pergalę?

A. 0 B. 1 C. 2 D. 3
Paaiškinimas

Visi galimi žaidimo sprendimo keliai gali būti pavaizduoti panašia, kaip pateikta, schema. Schema atspindi žaidimo medį. Šaknis vaizduoja padinę lentos būseną. Toliau kiekvienas galimas ėjimas vaizduojamas medžio šakomis ir šitaip gaunama nauja žaidimo būsena lentoje. Taip galima sudaryti visą medį. Žaidimo medis yra orientuotas grafas.
Žaidimo medis gali būti sudaromas norint žaisti arba norint perprasti žaidimą.
Priklausomai nuo sprendžiamos problemos, kartais geriau pirma ištirti gretimas viršūnes, negu pereiti į kitą viršūnių lygmenį (vadinamasis paieškos į plotį algoritmas). Tačiau kartais geriau ištirti kiek galima išsamiau kiekvieną šaką ir tik tada grįžti atgal (vadinamasis paieškos į gylį algoritmas). Šios dvi paieškos strategijos remiasi skirtingomis savybėmis ir atminties reikalavimais.

Reikšminiai žodžiai: būsena, žaidimo medis, paieška, paieškos į plotį algoritmas, paieškos į gylį algoritmas.

Atsakymas

Teisingas atsakymas yra B.
Tik padėdamas figūrą lentos centre, Kikis gali užsitikrinti laimėjimą. Įdomiausia, kad šiuo atveju nepriklausomai nuo to, kur figūrą dės Vikis, Kikis antruoju ėjimu savo figūrą turi padėti viršutiniame kairiajame kampe. Tuomet Vikis negali padėti savo figūros nepažeisdamas taisyklių.
Jei Kikio pirmasis ėjimas būtų kitoks, tai visais atvejais Vivis turėtų bent vieną galimybę laimėti.
Pateikta diagrama vaizduoja keletą galimų žaidimo kelių, kitos galimybės gali būti gautos pritaikius simetriją.

 

 
Informacija atnaujinta 2016-10-18 10:55:36
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.