Készemélyes játékok (mestint)

// http://hu.wikipedia.org/wiki/Nim
// http://aries.ektf.hu/~gkusper/mesterseges_intelligencia.v.1.0.4.pdf

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace mesintgyak_jatek
{
    // Az AbsztraktÁllpot osztályt ki kellett bővíteni a GetHeurisztika metódussal.
    // Egyébként megegyezik az előző fejezetben tárgyalt változattal.
    abstract class AbsztraktÁllapot : ICloneable
    {
        public abstract bool ÁllapotE();
        public abstract bool CélÁllapotE();
        public abstract int OperátorokSzáma();
        public abstract bool SzuperOperátor(int i);
        public virtual object Clone() { return MemberwiseClone(); }
        public override bool Equals(Object a) { return false; }
        public override int GetHashCode() { return base.GetHashCode(); }
        // Ez a metódus adja vissza, mennyire jó az adott állapot
        // Ez csak egy hook, felül kell írni, ha
        // kétszemélyes játékot vagy best-first algoritmus alkalmazunk,
        // vagy bármilyen más algoritmust, ami heurisztikán alapszik.
        // Más esetben, pl. backtrack esetén, nem kell felülírni.
        public virtual int GetHeurisztika() { return 0; }
    }

    // Az előző fejezetben ismertetett Csúcs osztályt bővítettük
    // egy-két metódussal, amely a két személyes játékok megvalósításához kell.
    class Csúcs
    {
        AbsztraktÁllapot állapot;
        int mélység;
        Csúcs szülő;
        // A szülőkön túl a gyermekeket is tartalmazza a Csúcs osztály.
        List<Csúcs> gyermekek = new List<Csúcs>();
        // Ez a mező tartalmazza, hogy melyik operátor segítségével jutottunk ebbe a csúcsba a szülő csúcsból.
        // Ennek segítségével tudom megmondani, melyik az ajánlott lépés NegaMaxMódszer esetén.
        int melyikOperátorralJutottamIde = -1; // ha -1, akkor még nincs beállítva
        public Csúcs(AbsztraktÁllapot kezdőÁllapot)
        {
            állapot = kezdőÁllapot;
            mélység = 0;
            szülő = null;
        }
        public Csúcs(Csúcs szülő)
        {
            állapot = (AbsztraktÁllapot)szülő.állapot.Clone();
            mélység = szülő.mélység + 1;
            this.szülő = szülő;
        }
        // Erre a metódusra azért van szükség, hogy a kiterjesztés működjön a JátékCsúcsra is.
        protected virtual Csúcs createGyermekCsúcs(Csúcs szülő) { return new Csúcs(szülő); }
        public Csúcs GetSzülő() { return szülő; }
        public int GetMélység() { return mélység; }
        public bool TerminálisCsúcsE() { return állapot.CélÁllapotE(); }
        public int OperátorokSzáma() { return állapot.OperátorokSzáma(); }
        public bool SzuperOperátor(int i)
        {
            // megjegyzem, melyik operátorral jutottam ebbe az állapotba
            melyikOperátorralJutottamIde = i;
            return állapot.SzuperOperátor(i);
        }
        public override bool Equals(Object obj)
        {
            Csúcs cs = (Csúcs)obj;
            return állapot.Equals(cs.állapot);
        }
        public override int GetHashCode() { return állapot.GetHashCode(); }
        public override String ToString() { return állapot.ToString(); }
        // Alkalmazza az összes alkalmazható operátort.
        // Visszaadja az így előálló új csúcsokat.
        public List<Csúcs> Kiterjesztés()
        {
            gyermekek = new List<Csúcs>();
            for (int i = 0; i < OperátorokSzáma(); i++)
            {
                // Új gyermek csúcsot készítek.
                // Ezzel a sorral nem működik a Kiterjesztés a JátékCsúcsban.
                // --- Csúcs újCsúcs = new Csúcs(this); ---
                // Ezért ezt használjuk:
                Csúcs újCsúcs = createGyermekCsúcs(this);
                // Kipróbálom az i.-dik alapoperátort. Alkalmazható?
                if (újCsúcs.SzuperOperátor(i))
                {
                    // Ha igen, hozzáadom az újakhoz.
                    gyermekek.Add(újCsúcs);
                }
            }
            return gyermekek;
        }
        // Visszaadja a csúcs heurisztikáját.
        // Ha saját heurisztikát akarunk írni, akkor azt a saját állapot osztályunkba kell megírni.
        public int GetHeurisztika() { return állapot.GetHeurisztika(); }
        // Visszaadja melyik operátorral jutottunk ide.
        // Ezzel az int értékkel kell majd meghívni a SzuperOperátor-t.
        public int GetMelyikOperátorralJutottamIde() { return melyikOperátorralJutottamIde; }
        // Nyomkövetéshez hasznos.
        public void Kiir()
        {
            Console.WriteLine(this);
            foreach (Csúcs gyermek in gyermekek) { gyermek.Kiir(); }
        }
    }

    // A
    //játék csúcs a
    //csúcs osztály kibővítése egy heurisztika értékkel.
    // Ezt a fajta csúcsot fel lehet használni a best first algoritmushoz is.
    class JátékCsúcs : Csúcs
    {
        int mennyireJó = -1; // mennyire jó, ha -1, akkor még nincs beállítva
        // Konstruktor:
        // A belső állapotot beállítja a start csúcsra.
        // A hívó felelősége, hogy a kezdő állapottal hívja meg.
        // A start csúcs mélysége 0, szülője nincs.
        public JátékCsúcs(AbsztraktÁllapot kezdőÁllapot) :
            base(kezdőÁllapot) { }
        // Egy új gyermek csúcsot készít.
        // Erre még meg kell hívni egy alkalmazható operátor is, csak azután lesz kész.
        public JátékCsúcs(Csúcs szülő) : base(szülő) { }
        // Erre a metódusra azért van szükség, hogy a kiterjesztés
        // működjön a JátékCsúcsra is.
        protected override Csúcs createGyermekCsúcs(Csúcs szülő)
        {
            return new JátékCsúcs(szülő);
        }
        // Visszaadja a csúcshoz tartozó heurisztikát.
        // Ez a csúcsban lévő állapot heurisztikája
        // megszorozva a paraméterben megkapott szor értékkel.
        // NegaMax esetén a szor általában 1, ha az a játékos lép,
        // akinek jó lépést keresünk, -1, ha az ellenfél lép.
        // Mivel minden állapothoz csak egy heurisztika van, ami nem
        // veszi figyelembe, hogy ki lép, ezért a MiniMax-nak is
        // úgy kell használni ezt a metódust, mint a NegaMax-nak.
        public int GetMennyireJó(int szor)
        {
            if (mennyireJó == -1) mennyireJó = GetHeurisztika() * szor;
            return mennyireJó;
        }
    }

    // Ebből kell leszármaztatni a lépés ajánló algoritmusokat, mint a NegaMax módszer.
    abstract class Stratégia
    {
        // Ha a start csúcs zsákutca, akkor null-t ad vissza.
        // Egyébként azt a csúcsot, amibe a stratégia szerint érdemes lépni.
        public abstract JátékCsúcs MitLépjek(JátékCsúcs start);
    }

    // Egy lépést ajánl valamely játékosnak a
    //NegaMax módszer alapján.
    // Ehhez előre tekint és a heurisztika meghatározása után megkeresi a legkedvezőbb utat a játék fában.
    // Ha a játékfa levelei terminális csúcsok, akkor a legkedvezőbb út a nyerő stratégia lesz.
    class NegaMaxMódszer : Stratégia
    {
        int maxMélység; // Ennyi lépésre tekintünk előre.
        // Minél több lépésre tekintünk előre, annál intelligensebbnek tűnik a gép, hiszen jobb lépést választ.
        // Ezt a TicTacToe esetén figyelhetjük meg.
        // Ugyanakkor minél több lépést generálunk, annál lassabb lesz az algoritmus.
        // Ennek egy megoldása az Alfabéta-vágás, de ezt nem programoztuk le.
        public NegaMaxMódszer(int intelligencia) { maxMélység = intelligencia; }
        // Egy játékcsúcsot ad vissza.
        // Ennek a GetMelyikOperátorralJutottamIde() függvénye mondja meg,
        // melyik lépést ajánlja a NegaMax módszer.
        // Ha zsákutcában van, akkor null-t ad vissza.
        public override JátékCsúcs MitLépjek(JátékCsúcs start)
        {
            Csúcs levél = MaxLépés(start, start.GetMélység() + maxMélység);
            if (levél == start) return null;
            while (levél.GetSzülő() != start) { levél = levél.GetSzülő(); }
            //levél.Kiir(); // Nyomkövetés esetén hasznos segítség
            return (JátékCsúcs)levél;
        }
        // Feltételezi, hogy a start csúcsban a kérdező játékos kérdezi, mit lépjen.
        // A kérdező játékos legjobb lépését, tehát a legnagyobb heurisztikájú
        // csúcs felé vezető lépést választja.
        // A gyermek csúcsok heurisztikáját NegaMax módszerrel számoljuk.
        private JátékCsúcs MaxLépés(JátékCsúcs start, int maxMélység)
        {
            JátékCsúcs akt = start;
            if (akt.GetMélység() == maxMélység) { return akt; }
            if (akt.TerminálisCsúcsE()) { return akt; }
            List<Csúcs> gyermekek = null;
            gyermekek = akt.Kiterjesztés();
            if (gyermekek.Count == 0) { return akt; }
            JátékCsúcs elsőGyermek = (JátékCsúcs)gyermekek[0];
            JátékCsúcs leg = MinLépés(elsőGyermek, maxMélység);
            int h = leg.GetMennyireJó(+1);
            for (int i = 1; i < gyermekek.Count; i++)
            {
                JátékCsúcs gyermek = (JátékCsúcs)gyermekek[i];
                JátékCsúcs legE = MinLépés(gyermek, maxMélység);
                int hE = legE.GetMennyireJó(+1);
                if (hE > h) { h = hE; leg = legE; }
            }
            return leg;
        }
        // Felételezi, hogy a start csúcsban a a kérdező játékos ellenfele lép.
        // Az ellenfél játékos legjobb lépését választja, tehát azt,
        // ami a kérdező játékosnak a legrosszabb.
        // Egybe lehetne vonni a MaxLépéssel, hiszen csak 5 helyen más.
        // Ezek a sorokat megjelöltük.
        private JátékCsúcs MinLépés(JátékCsúcs start, int maxMélység)
        {
            JátékCsúcs akt = start;
            if (akt.GetMélység() == maxMélység) { return akt; }
            if (akt.TerminálisCsúcsE()) { return akt; }
            List<Csúcs> gyermekek = null;
            gyermekek = akt.Kiterjesztés();
            if (gyermekek.Count == 0) { return akt; }
            JátékCsúcs elsőGyermek = (JátékCsúcs)gyermekek[0];
            JátékCsúcs leg = MaxLépés(elsőGyermek, maxMélység); //más
            int h = leg.GetMennyireJó(-1); // más
            for (int i = 1; i < gyermekek.Count; i++)
            {
                JátékCsúcs gyermek = (JátékCsúcs)gyermekek[i];
                JátékCsúcs legE = MaxLépés(gyermek, maxMélység); //más
                int hE = legE.GetMennyireJó(-1); //más
                if (hE < h) { h = hE; leg = legE; } //más
            }
            return leg;
        }
    }

    // A Tic Tac Toe játék állapot osztálya.
    class TicTacToeÁllapot : AbsztraktÁllapot
    {
        private static int N = 3; // 3 szor 3-mas tábla
        // NxN-es char mátrix
        // ' ': üres, 'X':első játékos jele, 'O': második játékos jele
        private char[,] tábla;
        private int countX, countO; // X-ek és O-k száma
        private bool nyert; // nyertes állapt-e
        private int üresekSzáma;
        public TicTacToeÁllapot()
        {
            tábla = new char[N, N];
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++) { tábla[i, j] = ' '; }
            }
            countX = 0; // kezdetben egy X sincs
            countO = 0; // kezdetben egy O sincs
            nyert = false;
            üresekSzáma = N * N;
        }
        public override bool ÁllapotE() { return true; }
        public override bool CélÁllapotE() { return nyert || üresekSzáma == 0; }
        private bool preRak(int x, int y)
        {
            return x >= 0 && x < N && y >= 0 && y < N && tábla[x, y] == ' ';
        }
        private bool rak(int x, int y)
        {
            if (!preRak(x, y)) return false;
            char c;
            if (countX > countO) c = 'O'; else c = 'X';
            tábla[x, y] = c;
            bool régiNyert = nyert;
            nyert = // nem elég általános, csak N = 3-ra jó!
            (tábla[0, y] == c && tábla[1, y] == c && tábla[2, y] == c) ||
            (tábla[x, 0] == c && tábla[x, 1] == c && tábla[x, 2] == c);
            nyert = nyert || (x == y &&
            tábla[0, 0] == c && tábla[1, 1] == c && tábla[2, 2] == c);
            nyert = nyert || (x + y == N - 1 &&
            tábla[0, 2] == c && tábla[1, 1] == c && tábla[2, 0] == c);
            üresekSzáma--;
            if (c == 'X') countX++; else countO++;
            if (ÁllapotE()) return true;
            tábla[x, y] = ' '; // visszavonás
            nyert = régiNyert;
            üresekSzáma++;
            if (c == 'X') countX--; else countO--;
            return false;
        }
        public override int OperátorokSzáma() { return 9; }
        public override bool SzuperOperátor(int i)
        {
            switch (i)
            {
                case 0: return rak(0, 0);
                case 1: return rak(0, 1);
                case 2: return rak(0, 2);
                case 3: return rak(1, 0);
                case 4: return rak(1, 1);
                case 5: return rak(1, 2);
                case 6: return rak(2, 0);
                case 7: return rak(2, 1);
                case 8: return rak(2, 2);
                default: return false;
            }
        }
        // Ezt most felül kell írni, mert tömb típusú mezőnk is van.
        // Egy szűk területre kell koncentrálni.
        public override object Clone()
        {
            TicTacToeÁllapot új = new TicTacToeÁllapot();
            új.tábla = (char[,])tábla.Clone();
            új.countX = countX;
            új.countO = countO;
            új.nyert = nyert;
            új.üresekSzáma = üresekSzáma;
            return új;
        }
        public override bool Equals(Object a)
        {
            TicTacToeÁllapot másik = (TicTacToeÁllapot)a;
            return tábla.Equals(másik.tábla);
        }
        public override int GetHashCode() { return tábla.GetHashCode(); }
        // Ez a metódus adja vissza, mennyire jó az adott állapot.
        public override int GetHeurisztika()
        {
            if (nyert) return 100 * (3 * N + 1);
            // szabad sorok, oszlopok, és átlok száma
            // szabad a sor, ha csak egy fajta szimbolum van benne
            return szabad('X');
        }
        // Ez egy kicsit általánosra sikerült, hiszen csak
        // szabad('X') formában fogjuk hívni, habár hívható lenne
        // szabad('0') formában is. Ez akkor lesz hasznos, ha a
        // GetHeurisztika() függvényt át akarjuk írni.
        private int szabad(char c)
        {
            int count = 0;
            for (int i = 0; i < N; i++)
            {
                int sorX = 0, sorO = 0;
                int oszlopX = 0, oszlopO = 0;
                for (int j = 0; j < N; j++)
                {
                    if (tábla[i, j] == 'X') sorX++;
                    if (tábla[i, j] == 'O') sorO++;
                    if (tábla[j, i] == 'X') oszlopX++;
                    if (tábla[j, i] == 'O') oszlopO++;
                }
                if (c == 'X' && sorX > 0 && sorO == 0) count += sorX;
                if (c == 'O' && sorO > 0 && sorX == 0) count += sorO;
                if (c == 'X' && oszlopX > 0 && oszlopO == 0) count += oszlopX;
                if (c == 'O' && oszlopO > 0 && oszlopX == 0) count += oszlopO;
            }
            int átló1X = 0, átló1O = 0;
            int átló2X = 0, átló2O = 0;
            for (int i = 0; i < N; i++)
            {
                if (tábla[i, i] == 'X') átló1X++;
                if (tábla[i, i] == 'O') átló1O++;
                if (tábla[N - 1 - i, i] == 'X') átló2X++;
                if (tábla[N - 1 - i, i] == 'O') átló2O++;
            }
            if (c == 'X' && átló1X > 0 && átló1O == 0) count += átló1X;
            if (c == 'O' && átló1O > 0 && átló1X == 0) count += átló1O;
            if (c == 'X' && átló2X > 0 && átló2O == 0) count += átló2X;
            if (c == 'O' && átló2O > 0 && átló2X == 0) count += átló2O;
            return count;
        }
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++)
            {
                sb.Append('\n');
                for (int j = 0; j < N; j++)
                {
                    sb.Append(tábla[i, j]);
                    sb.Append(',');
                }
                sb.Remove(sb.Length - 1, 1);
            }
            return sb.ToString();
        }
    }

    class Fejben21Állapot : AbsztraktÁllapot
    {
        private static int N = 21; // fejben 21, 21-ig kell menni
        private static int K = 3; // max K-t lehet hozzáadni a számhoz
        private int szám;
        public Fejben21Állapot() { szám = 0; } // az első játékos 0-tól indul
        public override bool ÁllapotE() { return szám <= N; }
        public override bool CélÁllapotE() { return szám == N; }
        // Ennek a játéknak egyszerű nyerő stratégiája van.
        // A kezdő játékos nyer, ha 1-et mond, majd rendre:
        // 5, 9, 13, 17, 21.
        // Ha valaki 1-gyel kezd, akkor az ellenfél mondhat 2, 3, vagy 4-et.
        // Bármelyiket is mondja az ellenfél, a kezdő játékos mondhat 5-öt.
        // Így az 1, 5, 9, 13, 17, 21 sor tartható.
        // Hogy a rendszer megtalálja ezt a sorozatot, ezért a sorozat elemeire
        // 100-at ad a heurisztika, minden más értékre csak 1-et.
        public override int GetHeurisztika() { return szám % (K + 1) == 1 ? 100 : 1; }
        private bool preLép(int i) { return i >= 0 && i < K; }
        private bool lép(int i)
        {
            if (!preLép(i)) return false;
            i++; // ha i=0, akkor 1-et kell hozzáadni, stb..
            szám += i;
            if (ÁllapotE()) return true;
            szám -= i;
            return false;
        }
        // Itt szerencsére nem kellett belső switch-t írni.
        // Ez inkább kivételes eset.
        public override bool SzuperOperátor(int i) { return lép(i); }
        public override int OperátorokSzáma() { return K; }
        public override string ToString() { return szám.ToString(); }
    }

    class NimÁllapot : AbsztraktÁllapot
    {
        int a, b, c;

        public NimÁllapot(int a, int b, int c = 0) // keződállapot
        {
            this.a = a;
            this.b = b;
            this.c = c;
        }
        public override bool ÁllapotE()
        {
            return a >= 0 && b >= 0 && c >= 0;
        }

        public override bool CélÁllapotE()
        {
            return a == 0 && b == 0 && c == 0;
        }

        public override int OperátorokSzáma()
        {
            return a + b + c;
        }

        public override bool SzuperOperátor(int i)
        {
            return Elvesz(i);
        }

        private bool Elvesz(int i)
        {
            if (!preElvesz(i)) return false;
            if (i < a)
            {
                a -= (i + 1);
            }
            else if (i < a + b)
            {
                b -= (i + 1 - a);
            }
            else
            {
                c -= (i + 1 - a - b);
            }

            return ÁllapotE();
        }

        private bool preElvesz(int i)
        {
            return i >= 0 && i < a + b + c;
        }

        public override int GetHeurisztika()
        {
            return a == b ? 100 : 1;
        }
        public override string ToString()
        {
            return string.Format("a: {0}, b: {1}, c: {2}", a, b, c);
        }
    }


    // Egy játékot vezényel le.
    // Ez egybevonható a főprogramból, hiszen abból emeltük ki.
    class Játék
    {
        AbsztraktÁllapot startÁllapot;
        Stratégia start;
        public Játék(AbsztraktÁllapot startÁllapot, Stratégia strat)
        {
            this.startÁllapot = startÁllapot;
            this.start = strat;
        }
        public void Start()
        {
            JátékCsúcs akt = new JátékCsúcs(startÁllapot);
            Console.WriteLine("Játszhat a gép ellen!");
            while (!akt.TerminálisCsúcsE())
            {
                // Saját lépésem.
                bool b = false;
                while (!b)
                {
                    Console.WriteLine("Jelenlegi állás: {0}", akt);
                    Console.WriteLine("Melyik operátort választja? (0,..,{0}): ", akt.OperátorokSzáma() - 1);
                    int k = 0;
                    try
                    {
                        k = int.Parse(Console.ReadLine());
                    }
                    catch (Exception e)
                    {
                        Console.WriteLine("Hiba: {0}", e.ToString());
                        Console.WriteLine("Érvénytelen lépés. Újra!");
                        continue;
                    }
                    b = akt.SzuperOperátor(k);
                    if (!b) Console.WriteLine("Ez az operátor nem alkalmazható. Újra!");
                }
                // Ellenfél lépése.
                Console.WriteLine("Jelenlegi állás: {0}", akt);
                akt = start.MitLépjek(akt);
                int i = akt.GetMelyikOperátorralJutottamIde();
                Console.WriteLine("A gép ezt az operátort választotta: {0}", i);
                // Nyertes állás?
                if (akt.TerminálisCsúcsE()) break;

            }
            Console.WriteLine("Jelenlegi állás: {0}", akt);
            Console.WriteLine("Aki utoljára lépett, az nyert, vagy döntetlen.");
        }
    } // Főprogram.
    class Program
    {
        static void Main(string[] args)
        {
            Stratégia start = new NegaMaxMódszer(5); // 5 mélységbe tekint előre
            //AbsztraktÁllapot startFejben21Állapot = new Fejben21Állapot();
            //Játék fejben21 = new Játék(startFejben21Állapot, start);
            //Console.WriteLine("A Fejben 21 játék kezdetét veszi!");
            //fejben21.start();
            //Console.ReadLine();
            //AbsztraktÁllapot startTTTÁllapot = new TicTacToeÁllapot();
            //Játék tictactoe = new Játék(startTTTÁllapot, start);
            //Console.WriteLine("A Tic Tac Toe játék kezdődik!");
            //tictactoe.Start();
            AbsztraktÁllapot nimstart = new NimÁllapot(7, 7);
            Játék nimjáték = new Játék(nimstart, start);
            Console.WriteLine("Nim játék!");
            nimjáték.Start();
            Console.ReadLine();
        }
    }
}