(m,n,k) spel med minmax, alpha-beta pruning och transpositionstabeller

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Timers;

namespace _m_n_k__spel
{
    internal class Program
    {
        //Inställning som väljs utav programmeraren
        static int m = 5;
        static int n = 5;
        static int vinstLängd = 5;
        static int maxDjup = 4;
        static char vemBörjar = 'O';

        static string notation = "";
        static Stopwatch timer = new Stopwatch();
        static Random slump = new Random(Guid.NewGuid().GetHashCode());
        static void visuelltBräde(char[,] bräde)
        {
            for (int i = m - 1; i >= 0; i--)
            {
                Console.Write("   ");
                for (int j = 0; j < n; j++)
                {
                    Console.Write("*---");
                }
                Console.WriteLine("*");

                if (i < 9)
                    Console.Write(i + 1 + ". |");
                else
                    Console.Write(i + 1 + ".|");

                for (int j = 0; j < n; j++)
                {
                    Console.Write(" ");
                    if (bräde[i, j] == 'X')
                        Console.ForegroundColor = ConsoleColor.Red;
                    else if (bräde[i, j] == 'O')
                        Console.ForegroundColor = ConsoleColor.Green;
                    Console.Write(bräde[i, j]);
                    Console.ForegroundColor = ConsoleColor.White;
                    Console.Write(" |");
                }
                Console.WriteLine();
            }

            Console.Write("   ");
            for (int j = 0; j < n; j++)
            {
                Console.Write("*---");
            }
            Console.WriteLine("*");

            Console.Write("     ");
            for (int j = 0; j < n; j++)
            {
                Console.Write((char)('A' + j) + "   ");
            }
            Console.WriteLine();
        }
        static bool vinst(char[,] bräde, char markör)
        {
            // Kontrollera vinst i kolumner
            for (int i = 0; i <= m - vinstLängd; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    bool kolumnVinst = true;
                    int temporärI = i;
                    for (int k = 0; k < vinstLängd; k++)
                    {
                        if (bräde[temporärI, j] != markör)
                            kolumnVinst = false;
                        temporärI++;
                    }
                    if (kolumnVinst == true)
                        return true;
                }
            }
            //Kontrollera vinst i rader
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j <= n - vinstLängd; j++)
                {
                    bool radVinst = true;
                    int temporärJ = j;
                    for (int k = 0; k < vinstLängd; k++)
                    {
                        if (bräde[i, temporärJ] != markör)
                            radVinst = false;
                        temporärJ++;
                    }
                    if (radVinst == true)
                        return true;
                }
            }
            // Kontrollera vinst i positiva diagonaler
            for (int i = 0; i <= m - vinstLängd; i++)
            {
                for (int j = 0; j <= n - vinstLängd; j++)
                {
                    bool diagonalVinst = true;
                    int temporärI = i;
                    int temporärJ = j;
                    for (int k = 0; k < vinstLängd; k++)
                    {
                        if (bräde[temporärI, temporärJ] != markör)
                            diagonalVinst = false;
                        temporärI++;
                        temporärJ++;
                    }
                    if (diagonalVinst == true)
                        return true;
                }
            }
            //Kontrollera vinst i negativa diagonaler
            for (int i = m-1; i >= vinstLängd-1; i--)
            {
                for (int j = 0; j <= n - vinstLängd; j++)
                {
                    bool diagonalVinst = true;
                    int temporärI = i;
                    int temporärJ = j;
                    for (int k = 0; k < vinstLängd; k++)
                    {
                        if (bräde[temporärI, temporärJ] != markör)
                            diagonalVinst = false;
                        temporärI--;
                        temporärJ++;
                    }
                    if (diagonalVinst == true)
                        return true;
                }
            }
            return false;
        }
        static void vinstUtskrift(char[,] bräde, char markör)
        {
            if (vinst(bräde, markör) == true)
            {
                visuelltBräde(bräde);
                Console.WriteLine(markör + " vinner");
                Console.WriteLine(notation + "# (" + m + ", " + n + ", " + vinstLängd + ")");
                Console.ReadLine();
                Environment.Exit(0);
            }
        }
        static bool lika(char[,] bräde)
        {
            bool lika = false;
            bool finnsTomRuta = false;

            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (bräde[i, j] == ' ')
                    {
                        finnsTomRuta = true;
                        break; // Om vi hittar en tom ruta, behöver vi inte fortsätta kolla
                    }
                }

                if (finnsTomRuta)
                    break; // Om vi hittar en tom ruta, behöver vi inte fortsätta kolla
            }

            if (finnsTomRuta == false)
                lika = true;

            return lika;
        }
        static void likaUtskrift(char[,] bräde)
        {
            if (lika(bräde) == true)
            {
                visuelltBräde(bräde);
                Console.WriteLine("Lika");
                Console.WriteLine(notation + "= (" + m + ", " + n + ", " + vinstLängd + ")");
                Console.ReadLine();
                Environment.Exit(0);
            }
        }
        static bool tillåtetDrag(char[,] bräde, string drag)
        {
            bool tillåtetDrag = false;

            if (m < 10)
            {
                if (drag.Length == 2 && Char.IsLetter(drag, 0) == true && Char.IsNumber(drag, 1) == true)
                {
                    int rad = Convert.ToInt32(Convert.ToString(drag[1])) - 1;
                    int kolumn = Convert.ToInt32(drag[0] - 'A');

                    if (rad >= 0 && rad < m && kolumn >= 0 && kolumn < n)
                    {
                        if (bräde[rad, kolumn] == ' ')
                            tillåtetDrag = true;
                    }
                }
            }
            if (m >= 10)
            {
                if (drag.Length == 2)
                {
                    if (Char.IsLetter(drag, 0) == true && Char.IsNumber(drag, 1) == true)
                    {
                        int rad = Convert.ToInt32(Convert.ToString(drag[1])) - 1;
                        int kolumn = Convert.ToInt32(drag[0] - 'A');

                        if (rad >= 0 && rad < m && kolumn >= 0 && kolumn < n)
                        {
                            if (bräde[rad, kolumn] == ' ')
                                tillåtetDrag = true;
                        }
                    }
                }
                if (drag.Length == 3)
                {
                    if (Char.IsLetter(drag, 0) == true && Char.IsNumber(drag, 1) == true && Char.IsNumber(drag, 2))
                    {
                        int rad = 10 * Convert.ToInt32(Convert.ToString(drag[1])) + Convert.ToInt32(Convert.ToString(drag[2])) - 1;
                        int kolumn = Convert.ToInt32(drag[0] - 'A');

                        if (rad >= 0 && rad < m && kolumn >= 0 && kolumn < n)
                        {
                            if (bräde[rad, kolumn] == ' ')
                                tillåtetDrag = true;
                        }
                    }
                }
            }
            return tillåtetDrag;
        }
        static char[,] spelarDrag(char[,] bräde)
        {
            visuelltBräde(bräde);
            string drag;
            for (; ; )
            {
                Console.WriteLine("Spelare O: Ditt drag");
                drag = Console.ReadLine().ToUpper();
                if (tillåtetDrag(bräde, drag) == true)
                {
                    notation = notation + drag + " ";
                    break;
                }
                else
                    Console.WriteLine("Fel input");
            }
            if (m < 10)
                bräde[Convert.ToInt32(Convert.ToString(drag[1])) - 1, Convert.ToInt32(drag[0]) - 65] = 'O';
            else if (drag.Length == 3 && m >= 10)
                bräde[10 * Convert.ToInt32(Convert.ToString(drag[1])) + Convert.ToInt32(Convert.ToString(drag[2])) - 1, Convert.ToInt32(drag[0]) - 65] = 'O';
            else if (drag.Length == 2  && m >= 10)
                bräde[Convert.ToInt32(Convert.ToString(drag[1])) - 1, Convert.ToInt32(drag[0]) - 65] = 'O';
            Console.Clear();
            vinstUtskrift(bräde, 'O');
            likaUtskrift(bräde);
            return bräde;
        }
        static int betyg(char[,] bräde)
        {
            int betyg = 10000;
            if (vinst(bräde, 'X') == true)
            {
                betyg = 1000;
            }
            else if (vinst(bräde, 'O') == true)
            {
                betyg = -1000;
            }
            else if (lika(bräde) == true)
            {
                betyg = 0;
            }
            return betyg;
        }
        static long antalCheckar = 0;
        static int antalTranspositioner = 0;

        static Dictionary<string, int> poängDictionary = new Dictionary<string, int>();
        static Dictionary<string, int> djupDictionary = new Dictionary<string, int>();
        static int minimax(char[,] bräde, bool maximeraresTur, int djup, int alpha, int beta)
        {
            //Här börjar transpositionerna
            string nyckel = nyckelByggare(bräde);

            int hämtaPoäng;
            int hämtaDjup;

            if (poängDictionary.ContainsKey(nyckel))
                hämtaPoäng = poängDictionary[nyckel];
            else
                hämtaPoäng = -1; //Dvs poängen finns ej i tabellen

            if (djupDictionary.ContainsKey(nyckel))
                hämtaDjup = djupDictionary[nyckel];
            else
                hämtaDjup = -1; //Dvs djupet finns ej i tabellen

            if (hämtaDjup >= djup) //Om nyckeln inte finns är djup = -1 och < alla djup => värdet sparas ej
            {
                antalTranspositioner++;
                return hämtaPoäng;
            } //Här slutar transpositioner

            int poäng;
            int bästaPoäng;

            if (betyg(bräde) != 10000 || djup == maxDjup)
            {
                poäng = betyg(bräde);
                return poäng;
            }

            if (maximeraresTur == true) //Datorn
            {
                bästaPoäng = int.MinValue;
                for (int rad = 0; rad < m; rad++)
                {
                    for (int kolumn = 0; kolumn < n; kolumn++)
                    {
                        if (bräde[rad, kolumn] == ' ')
                        {
                            bräde[rad, kolumn] = 'X';
                            antalCheckar++;
                            poäng = minimax(bräde, false, djup + 1, alpha, beta);
                            bräde[rad, kolumn] = ' ';
                            bästaPoäng = Math.Max(poäng, bästaPoäng);

                            alpha = Math.Max(alpha, bästaPoäng);
                            if (beta <= alpha)
                                break; // Beta cut-off
                        }
                    }
                }
            }
            else //Spelaren
            {
                bästaPoäng = int.MaxValue;
                for (int rad = 0; rad < m; rad++)
                {
                    for (int kolumn = 0; kolumn < n; kolumn++)
                    {
                        if (bräde[rad, kolumn] == ' ')
                        {
                            bräde[rad, kolumn] = 'O';
                            antalCheckar++;
                            poäng = minimax(bräde, true, djup + 1, alpha, beta);
                            bräde[rad, kolumn] = ' ';
                            bästaPoäng = Math.Min(poäng, bästaPoäng);

                            beta = Math.Min(beta, bästaPoäng);
                            if (beta <= alpha)
                                break; // Alpha cut-off
                        }
                    }
                }
            }
            poängDictionary[nyckel] = bästaPoäng;
            djupDictionary[nyckel] = djup;

            return bästaPoäng;
        }
        static string nyckelByggare(char[,] bräde)
        {
            string nyckel = "";
            for (int rad = 0; rad < m; rad++)
            {
                for (int kolumn = 0; kolumn < n; kolumn++)
                {
                    nyckel = nyckel + bräde[rad, kolumn];
                }
            }
            return nyckel;
        }
        static void efterDragDator(char[,] bräde, int rad, int kolumn, string med)
        {
            bräde[rad, kolumn] = 'X';
            Console.WriteLine("Datorn spelar: " + Convert.ToString(Convert.ToChar(kolumn + 65)).ToLower() + (rad + 1).ToString() + " " + med);
            notation = notation + Convert.ToString(Convert.ToChar(kolumn + 65)).ToLower() + (rad + 1).ToString() + " ";
            vinstUtskrift(bräde, 'X');
            likaUtskrift(bräde);
        }
        static char[,] datorDrag(char[,] bräde)
        {
            timer.Start(); 
            char[,] brädeKopia = bräde;
            for (int rad = 0; rad < m; rad++) //Vinst
            {
                for (int kolumn = 0; kolumn < n; kolumn++)
                {
                    if (bräde[rad, kolumn] == ' ')
                    {
                        brädeKopia[rad, kolumn] = 'X';
                        if (vinst(brädeKopia, 'X') == true)
                        {
                            efterDragDator(bräde, rad, kolumn, "(vinst)");
                            return bräde;
                        }
                        brädeKopia[rad, kolumn] = ' ';
                    }
                }
            }
            for (int rad = 0; rad < m; rad++) //Blockera
            {
                for (int kolumn = 0; kolumn < n; kolumn++)
                {
                    if (bräde[rad, kolumn] == ' ')
                    {
                        brädeKopia[rad, kolumn] = 'O';
                        if (vinst(brädeKopia, 'O') == true)
                        {
                            efterDragDator(bräde, rad, kolumn, "(blockera)");
                            return bräde;
                        }
                        brädeKopia[rad, kolumn] = ' ';
                    }
                }
            }
            for (int rad1 = 0; rad1 < m; rad1++) //Två vinster
            {
                for (int kolumn1 = 0; kolumn1 < n; kolumn1++)
                {
                    if (bräde[rad1, kolumn1] == ' ')
                    {
                        brädeKopia[rad1, kolumn1] = 'X';
                        int antalVinster = 0;
                        for (int rad2 = 0; rad2 < m; rad2++)
                        {
                            for (int kolumn2 = 0; kolumn2 < n; kolumn2++)
                            {
                                if (brädeKopia[rad2, kolumn2] == ' ')
                                {
                                    brädeKopia[rad2, kolumn2] = 'X';
                                    if (vinst(brädeKopia, 'X') == true)
                                        antalVinster++;
                                    brädeKopia[rad2, kolumn2] = ' ';
                                }
                            }
                        }
                        if (antalVinster >= 2)
                        {
                            efterDragDator(bräde, rad1, kolumn1, "(två vinster)");
                            return bräde;
                        }
                        brädeKopia[rad1, kolumn1] = ' ';
                    }
                }
            }
            for (int rad1 = 0; rad1 < m; rad1++) //Två blockader
            {
                for (int kolumn1 = 0; kolumn1 < n; kolumn1++)
                {
                    if (bräde[rad1, kolumn1] == ' ')
                    {
                        brädeKopia[rad1, kolumn1] = 'O';
                        int antalVinster = 0;
                        for (int rad2 = 0; rad2 < m; rad2++)
                        {
                            for (int kolumn2 = 0; kolumn2 < n; kolumn2++)
                            {
                                if (brädeKopia[rad2, kolumn2] == ' ')
                                {
                                    brädeKopia[rad2, kolumn2] = 'O';
                                    if (vinst(brädeKopia, 'O') == true)
                                        antalVinster++;
                                    brädeKopia[rad2, kolumn2] = ' ';
                                }
                            }
                        }
                        if (antalVinster >= 2)
                        {
                            efterDragDator(bräde, rad1, kolumn1, "(två blockader)");
                            return bräde;
                        }
                        brädeKopia[rad1, kolumn1] = ' ';
                    }
                }
            }
            
            int nuvarandePoäng;
            int bästaPoäng = int.MinValue;
            int bästaRad = 0;
            int bästaKolumn = 0;
            for (int rad = 0; rad < m; rad++)
            {
                for (int kolumn = 0; kolumn < n; kolumn++)
                {
                    if (bräde[rad, kolumn] == ' ')
                    {
                        bräde[rad, kolumn] = 'X';
                        nuvarandePoäng = minimax(bräde, false, 0, int.MinValue, int.MaxValue);
                        bräde[rad, kolumn] = ' ';
                        if (nuvarandePoäng > bästaPoäng)
                        {
                            bästaPoäng = nuvarandePoäng;
                            bästaRad = rad;
                            bästaKolumn = kolumn;
                        }
                    }
                }
            }
            bräde[bästaRad, bästaKolumn] = 'X';

            timer.Stop();
            TimeSpan timerTid = timer.Elapsed;
            double tid = timerTid.TotalSeconds;
            timer.Reset();

            poängDictionary.Clear();
            djupDictionary.Clear();

            Console.WriteLine("Datorn spelar: " + Convert.ToString(Convert.ToChar(bästaKolumn + 65)).ToLower() + (bästaRad + 1).ToString() + " (minmax)");
            Console.WriteLine("Datorn har kollat: " + antalCheckar + " matcher");
            Console.WriteLine("Vilket tog: " + Math.Round(tid, 2) + " s");
            Console.WriteLine("Vilket motsvarar: " + Math.Round(antalCheckar/tid) + " matcher per s");
            Console.WriteLine("Datorn fann: " + antalTranspositioner + " transpositioner");

            antalCheckar = 0;
            antalTranspositioner = 0;   
            tid = 0;
            notation = notation + Convert.ToString(Convert.ToChar(bästaKolumn + 65)).ToLower() + (bästaRad + 1).ToString() + " ";
            maxDjup = maxDjup + 1;
            vinstUtskrift(bräde, 'X');
            likaUtskrift(bräde);
            return bräde;
        }
        static void Main(string[] args)
        {
            char[,] bräde = new char[m, n];
            for (int rad = 0; rad < m; rad++)
                for (int kolumn = 0; kolumn < n; kolumn++)
                    bräde[rad, kolumn] = ' ';
            if (vemBörjar == 'O')
            {
                for (; ; )
                {
                    bräde = spelarDrag(bräde);
                    bräde = datorDrag(bräde);
                }
            }
            else
            {
                for (; ; )
                {
                    bräde = datorDrag(bräde);
                    bräde = spelarDrag(bräde);
                }
            }
        }
    }
}

Hej! Först i koden deklareras m, n och vinstlängd. Det innebär att vi spelar ett tre-i-rad-liknande spel fast på ett m x n-bräde med en speciell vinstlängd. Datordelen i programmet är en minimax-algoritm som använder alpha-beta pruning och en transpositionstabell för att bli snabbare. Allt detta fungerar väldigt bra! Men datorn har ingen tidsuppfattning, det vill säga den bryr sig inte om den förlorar på ett drag eller sex drag. Den spelar också väldigt tråkigt, eftersom den inte är slumpmässig. Om den inte ser en vinst eller förlust spelar den alltid så långt ned till vänster som möjligt. Hur ska dessa saker fixas? Jag har försökt ändra i betyg-metoden så att den får fler poäng om den vinner snabbt och färre poäng om den förlorar snabbt. Dessutom lade jag till en slump-faktor, men detta funkade inte. Har någon en idé?