Bevezető

A népszerű MasterMind játékot két játékos: Rejtő és Fejtő játssza.

Rejtő kigondol egy titkos négyjegyű számot (pl. 0342).
Fejtő célja a szám kitalálása találgatással.
Fejtő tippel egy négyjegyű számot (pl 3245), megmutatja azt Rejtőnek.
Rejtő számjegyenként összehasonlítja a tippet a titkos számmal, és megad két eredményt:
- a helyes pozíciójú és értékű számjegyek száma
- a rossz pozíciójú, de helyes értékű számjegyek száma.
Esetünkben a válasz (1,2), hiszen a 4-es jó helyen van, a 3-as meg a 2-es pedig rossz helyen.
Fejtő addig folytatja a tippelgetést, míg a válasz nem lesz (4,0).

Megjegyzés: A játékot eredeti formájában természetesen nem számjegyekkel, hanem hatféle színű bogyókkal játsszák, de mi átlátunk a szitán: ezek hatos számrendszerbeli számok. Az eredeti játékban a választ fekete és fehér tüskékkel jelzik (fekete,fehér).

Megoldás

Írjuk meg Fejtőt, aki kitalálja a titkos számot!

Megoldáshalmaz szűkítése véletlen tippekkel

Az órán lekódolt algortimusunk az alábbi volt

1. Fejtő előállítja a lehetséges megoldások S halmazát: {0000, 0001, ..., 9999}
2. Fejtő tippje egy véletlen elem S-ből, ezt jelölje g (guess)
3. Rejtő összehasonlítja g-t a titokkal, válaszát jelölje r (response)
4. Fejtő S-ből kitörli azokat az elemeket, melyek g-vel összevetve nem r-t adnak
5. ismétlés 2-től, amíg S egyeleművé nem válik

C-kóddal

/* S legyártása */
for (i = 0; i < N0; ++i)
    S[i] = i;
N = N0;
/* tippelgetés */
do {
    int guess = S[rand() % N];                          /* Fejtő tippel S-ből */
    Response response = common_digits(guess, secret);   /* Rejtő válaszol */
    N = filter(S, N, guess, response);                  /* S szűkítése */
} while (N > 1);

Az algoritmushoz közösen megírt függvényeink az alábbiak:

A common_digits függvény meghatározza, hogy hány közös számjegye van két egész számnak. Ez a függvény egy Response struktúrát ad vissza, mely tartalmazza a fekete és a fehér tüskék számait.
A filter függvény kiszűri a lehetséges megoldáshalmazból azokat a számokat, melyek a legutóbbi tipp-válasz alapján lehetetlenek

További segédfüggvények:

A digits függvény feltölt egy tömböt egy egész szám adott számrendszerbeli számjegyeivel
Az isSameResponse függvény meghatározza, hogy két válasz megegyezik-e (a fekete és fehér tüskék számai külön-külön)

Megoldáshalmaz szűkítése a legjobb tippel

A fenti algoritmus gyenge pontja a (2) véletlen tippválasztás; okosabb, ha kikeressük a lehető legjobb tippet az S halmazból.

Minden tipphez hozzárendelünk egy súlyt, ami azt mutatja meg, hogy azzal a tippel mekkorára csökkenthető az S megoldáshalmaz mérete. Értelemszerűen a legkisebb súlyú tippet választjuk.

Meg kell gondolnunk viszont, hogy egy tipphez nem tudunk egyértelműen súlyt rendelni, amíg nem ismerjük a tippre adott választ is. Ha ugyanis pl. kezdőtippünkre a (4,0) választ kapjuk, akkor azonnal 1 méretűre szűkíthetjük S-t. Ha ellenben a válasz (0,0), akkor S méretét sokkal kisebb mértékben csökkenthetjük csak. Ezért úgy rendelünk tipphez súlyt, hogy elképzeljük az összes lehetséges r választ, mindegyikkel meghatározzuk a tipp súlyát, és ezek közül a legnagyobbat (worst case) képezzük.

Végeredményben egy minimax módszerrel dolgozunk, melyben

minden lehetséges S-beli g tippre
    minden lehetséges r válaszra
        számítjuk a (g, r) páros w(g, r) súlyát
    képezzük ezek maximumát r-ben
képezzük ezek minimumát g-ben

Az implementációban az algoritmust az alábbi függvények valósítják meg:

A weight függvény w(g,r) súlyt számítja. A filter függvény algoritmusát valósítja meg, de nem töröl az S halmazból, hanem csak megszámolja a megfelelő elemeket
A különböző válaszkohoz tartozó maximumokat adja meg a worstWeightOfGuess függvény,
ezek minimumát pedig a findBestGuess.

A módosított főprogram pedig:

for (i = 0; i < N0; ++i)
    S[i] = i;
N = N0;
do {
    int guess = findBestGuess(S, N);                    /* Fejtő optimális tippet keres */
    Response response = common_digits(guess, secret);   /* Rejtő válaszol */
    N = filter(S, N, guess, response);                  /* S szűkítése */
} while (N > 1);

Az új algoritmus tízes számrendszerben (tíz színnel) és négy számjeggyel az alábbihoz hasonló kimenetet produkál.

     9349
     ------------
     guess  res      N  t[s]
  1: 0123 | (0,1) 3048 29.00
  2: 1445 | (1,0)  542  3.00
  3: 3646 | (1,1)   59  0.00
  4: 7348 | (2,0)    3  0.00
  5: 6048 | (1,0)    1  0.00

    I won: 9349

Érdekes, hogy a legtöbb időt (29 másodperc!) az első tipp kikeresése igényli. Ez természetesen mindig ugyanaz, a 0123 értéket el is lehet tárolni, mint optimális kezdő tipp tízes számrendszerben. Az erre adott válasz (0,1) természetesen már függ a véletlen titkos számtól is. A nem túl szerencsés titkos szám mellett a kezdőtipp a 10000 lehetőséget 3048-ra csökkenti. A második legjobb tipp kiválasztása már csak 3 mp, a továbbiak századmásodperc alatt megvannak. Az ötödik iterációra jut el a program az N=1 értékhez, vagyis öt rákérdezéssel meghatározta a megoldást.

További javítás:

A fenti algoritmusban triviálisnak vettük, hogy a következő tippet mindig S-ből vesszük, vagyis csak olyat tippelünk, ami megoldás is lehet. Ez nem feltétlenül a legjobb hozzáállás. Ha nem az a célunk, hogy véletlenül beletrafáljunk a megoldásba, hanem az, hogy minél jobban csökkentsük az S halmaz méretét, a következő tippet az összes olyan érték közül kell választanunk, melyekre korábban még nem tippeltünk.

Ez már házi feladat...

Fordítás és futtatás

A program innen letölthető.

Fordításnál itt már fontos, hogy bekapcsoljuk a kódoptimalizálást (optimalizálás nélkül a fenti eset első tippje nem 29, hanem 190 másodperc alatt készül el, a második tipp 3 helyett 18 másodperc alatt).

gcc mastermind.c -o mastermind.exe -O3

cl mastermind.c /Femastermind.exe /Ox