TicTacToe - Varianten der NegaAlphaBeta Zugsuche und notwendige Klassen

using System;
using System.Threading;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Controls.Ribbon;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Shapes;
using System.Windows.Threading;

namespace PlasticineTicTacToe
{
    public partial class MainWindow : RibbonWindow
    {
        delegate void DelegateGameFinished(GameState gamesState);
        DelegateGameFinished delegateGameFinished;
        delegate void DelegateWriteInfo(bool playerMaxHasToMove);
        DelegateWriteInfo delegateWriteInfo;

        const int BOARDCOLUMNS = 3;
        const int BOARDROWS = 3;
        Board board;
        Game game;

        public MainWindow()
        {
            InitializeComponent();
        }

        private void OnNewGame(object sender, RoutedEventArgs e)
        {
            EnableUI(true);
            Player PlayerMax = (Player)((ComboBoxItem)galPlayerMax.SelectedItem).DataContext;
            Player PlayerMin = (Player)((ComboBoxItem)galPlayerMin.SelectedItem).DataContext;
            if (PlayerMax.behaviorSearch is SearchHuman)
            {
                ((SearchHuman)PlayerMax.behaviorSearch).SendCursor += new SearchHuman.OnSetCursor(OnSetCursor);
                canvasBoard.MouseLeftButtonUp += ((SearchHuman)PlayerMax.behaviorSearch).OnMouseLeftButtonUp;
            }
            if (PlayerMin.behaviorSearch is SearchHuman)
            {
                ((SearchHuman)PlayerMin.behaviorSearch).SendCursor += new SearchHuman.OnSetCursor(OnSetCursor);
                canvasBoard.MouseLeftButtonUp += ((SearchHuman)PlayerMin.behaviorSearch).OnMouseLeftButtonUp;
            }
            RemovePieces(); 
            game.Start(PlayerMax, PlayerMin);
        }

        private void OnQuitGame(object sender, RoutedEventArgs e)
        {
            game.Abort();
            canvasBoard.Cursor = Cursors.No;
            EnableUI(false);
        }

        private void OnHelp(object sender, RoutedEventArgs e)
        {

        }

        private void OnInitialized(object sender, EventArgs e)
        {
            Thread.Sleep(1000);
        }

        private void OnLoaded(object sender, RoutedEventArgs e)
        {
            board = new Board(BOARDCOLUMNS, BOARDROWS);
            FillUIElements(board);
            game = new Game(board);
            game.SendWriteProtokoll += new Game.OnWriteProtokoll(OnWriteProtokoll);
            game.SendWriteInfo += new Game.OnWriteInfo(OnWriteInfo);
            game.SendGameFinished += new Game.OnGameFinished(OnGameFinished);
            game.SendSetPiece += new Game.OnSetPiece(OnSetPiece);
            delegateWriteInfo = WriteInfo;
            delegateGameFinished = GameFinished;
        }

        private void OnClosed(object sender, EventArgs e)
        {
            game.Abort();
        }

        private void FillUIElements(Board board)
        {
            FillPlayerComboBox(rgcPlayerMax, board);
            FillPlayerComboBox(rgcPlayerMin, board);
            galPlayerMax.SelectedItem = rgcPlayerMax.Items[0];
            galPlayerMin.SelectedItem = rgcPlayerMin.Items[1];

            DrawCellGridLines();
            DrawCellIndex();
        }

        private void FillPlayerComboBox(RibbonGalleryCategory rgc, Board board)
        {
            EvaluateBase bahaviorMinMax = new EvaluateMinMax(board);
            EvaluateBase bahaviorNega = new EvaluateNega(board);

            ComboBoxItem cbi = new ComboBoxItem();
            cbi.Content = "Mensch";
            cbi.DataContext = new Player(new SearchHuman(board, bahaviorMinMax, new MoveGenerator(board, bahaviorMinMax)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "Computer Zufall";
            cbi.DataContext = new Player(new SearchRandom(board, bahaviorMinMax, new MoveGenerator(board, bahaviorMinMax)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "MiniMax";
            cbi.DataContext = new Player(new SearchMiniMax(board, bahaviorMinMax, new MoveGenerator(board, bahaviorMinMax)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "Nega MiniMax";
            cbi.DataContext = new Player(new SearchNegaMax(board, bahaviorNega, new MoveGenerator(board, bahaviorNega)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "AlphaBeta";
            cbi.DataContext = new Player(new SearchAlphaBeta(board, bahaviorMinMax, new MoveGenerator(board, bahaviorMinMax)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "NegaAlphaBeta";
            cbi.DataContext = new Player(new SearchNegaAlphaBeta(board, bahaviorNega, new MoveGenerator(board, bahaviorNega)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "NegaAlphaBetaSort";
            cbi.DataContext = new Player(new SearchNegaAlphaBetaSort(board, bahaviorNega, new MoveGenerator(board, bahaviorNega)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);

            cbi = new ComboBoxItem();
            cbi.Content = "NegaAlphaBetaSortTrans";
            cbi.DataContext = new Player(new SearchNegaAlphaBetaSortTrans(board, bahaviorNega, new MoveGenerator(board, bahaviorNega)));
            cbi.IsHitTestVisible = false;
            rgc.Items.Add(cbi);
        }

        private void EnableUI(bool runningGame)
        {
            btnNewGame.IsEnabled = !runningGame;
            btnQuitGame.IsEnabled = runningGame;
            rcbPlayerMax.IsEnabled = !runningGame;
            rcbPlayerMin.IsEnabled = !runningGame;
            if (!runningGame)
            {
                // Workaround für RibbonCombobox Problem
                // Items bleiben disabled, wenn die RibbonCombobox
                // wieder enabled wird. Durch die Commandzuweisung
                // und Entfernung wird ein internes reinit erzwungen 
                // und der enabled Status korekt gesetzt.
                galPlayerMax.Command = ApplicationCommands.Print;
                galPlayerMax.Command = null;
                galPlayerMin.Command = ApplicationCommands.Print;
                galPlayerMin.Command = null;
            }
        }

        private void OnWriteProtokoll(Object obj, ProtokollEventArgs e)
        {
            string strSec = String.Format("{0:0.000}", e.seconds);
            lvProtokoll.Dispatcher.Invoke(
                DispatcherPriority.Normal,
                new Action(delegate()
                {
                    lvProtokoll.Items.Insert(0, new
                    {
                        MoveNr = e.moveNumber,
                        Move = e.idxCell,
                        Nodes = e.nodes,
                        Sec = strSec,
                        NPerSec = e.nodesPerSec,
                        Leaf = e.evaluateLeaf
                    });
                })
            );
        }

        private void OnWriteInfo(Object obj, InfoEventArgs e)
        {
            this.Dispatcher.Invoke(DispatcherPriority.Normal,
                    delegateWriteInfo, e.playerMaxHasToMove);
        }

        private void WriteInfo(bool playerMaxHasToMove)
        {
            imgToDo.Source = playerMaxHasToMove ? rcbPlayerMax.SmallImageSource : rcbPlayerMin.SmallImageSource;
            lblToDo.Content = "Ist am Zug.";
        }

        private void OnGameFinished(Object obj, GameFinishedEventArgs e)
        {
            this.Dispatcher.Invoke(DispatcherPriority.Normal,
                    delegateGameFinished, e.gameState);
        }

        private void GameFinished(GameState gameState)
        {
            lblToDo.Content = "hat gewonnen.";
            switch (gameState)
            {
                case GameState.playerMaxWins: imgToDo.Source = rcbPlayerMax.SmallImageSource; break;
                case GameState.playerMinWins: imgToDo.Source = rcbPlayerMin.SmallImageSource; break;
                case GameState.drawGame:
                    {
                        lblToDo.Content = "unentschieden.";
                        imgToDo.Source = new BitmapImage(new Uri(@"pack://application:,,/pics/Both.png", UriKind.RelativeOrAbsolute));
                    }
                    break;
            }
            lvProtokoll.Items.Insert(0, new
            {
                Move = new String('\u2550', 8),
                Cell = new String('\u2550', 8),
                Nodes = new String('\u2550', 8),
                Sec = new String('\u2550', 8),
                kNPerSec = new String('\u2550', 8),
                Leaf = new String('\u2550', 8)
            });
            EnableUI(false);
            canvasBoard.Cursor = Cursors.No;
        }

        private void OnSetCursor(Object obj, CursorEventArgs e)
        {
            canvasBoard.Dispatcher.Invoke(
                DispatcherPriority.Normal,
                new Action(delegate()
                {
                    canvasBoard.Cursor = e.cursor;
                })
            );
        }

        private void OnSizeChanged(object sender, SizeChangedEventArgs e)
        {
            if (board == null) return;
            double cellWidth = canvasBoard.ActualWidth / board.MaxCols;
            double cellHeight = canvasBoard.ActualHeight / board.MaxRows;
            for (int idx = 0; idx < canvasBoard.Children.Count; idx++)
            {
                int cellIdx;
                var obj = canvasBoard.Children[idx];
                if (obj.GetType() == typeof(Line))
                {
                    Line child = obj as Line;
                    int.TryParse(child.Name.Remove(0, 4), out cellIdx);
                    if (child.X1 == child.X2)
                    {
                        child.X1 = child.X2 = cellIdx * cellWidth;
                        child.Y1 = 0;
                        child.Y2 = canvasBoard.ActualHeight;
                    }
                    else
                    {
                        child.Y1 = child.Y2 = cellIdx * cellHeight;
                        child.X1 = 0;
                        child.X2 = canvasBoard.ActualWidth;
                    }
                }
                else if (obj.GetType() == typeof(TextBlock))
                {
                    TextBlock child = obj as TextBlock;
                    int.TryParse(child.Name.Remove(0, 4), out cellIdx);
                    int colNumber = board.MaxCols - 1 - cellIdx % board.MaxCols;
                    int rowNumber = board.MaxRows - 1 - cellIdx / board.MaxCols;

                    Canvas.SetLeft(child, colNumber * cellWidth + cellWidth / 10);
                    Canvas.SetTop(child, rowNumber * cellHeight + cellHeight / 10);
                }
                else if (obj.GetType() == typeof(Ellipse))
                {
                    double vertSymBorderDist = cellHeight / 5.0;
                    double horiSymBorderDist = cellWidth / 5.0;

                    Ellipse child = obj as Ellipse;
                    int.TryParse(child.Name.Remove(0, 9), out cellIdx);
                    child.Width = cellWidth - 2 * horiSymBorderDist;
                    child.Height = cellHeight - 2 * vertSymBorderDist;

                    Canvas.SetTop(child, (board.MaxRows - 1 - cellIdx / board.MaxCols) * cellHeight + vertSymBorderDist);
                    Canvas.SetLeft(child, (board.MaxCols - 1 - cellIdx % board.MaxCols) * cellWidth + horiSymBorderDist);
                }
            }
        }

        private void DrawCellIndex()
        {
            TextBlock tbCellIndex;
            int colNumber, rowNumber;
            double cellWidth = canvasBoard.ActualWidth / board.MaxCols;
            double cellHeight = canvasBoard.ActualHeight / board.MaxRows;
            for (int cellIndex = board.CellCount - 1; cellIndex >= 0; cellIndex--)
            {
                colNumber = board.MaxCols - 1 - cellIndex % board.MaxCols;
                rowNumber = board.MaxRows - 1 - cellIndex / board.MaxCols;
                tbCellIndex = new TextBlock();
                tbCellIndex.Name = "Text" + cellIndex.ToString();
                tbCellIndex.FontSize = 10;
                tbCellIndex.Foreground = Brushes.Black;
                tbCellIndex.Text = (cellIndex).ToString();
                canvasBoard.Children.Add(tbCellIndex);
                Canvas.SetTop(tbCellIndex, rowNumber * cellHeight + cellHeight / 10);
                Canvas.SetLeft(tbCellIndex, colNumber * cellWidth + cellWidth / 10);
            }
        }

        private void DrawCellGridLines()
        {
            int colNumber, rowNumber;
            double cellWidth = canvasBoard.ActualWidth / board.MaxCols;
            double cellHeight = canvasBoard.ActualHeight / board.MaxRows;

            Line line;
            double cellStrokeThickness = 2.0;
            for (colNumber = 0; colNumber <= board.MaxCols; colNumber++)
            {
                line = new Line();
                line.StrokeThickness = cellStrokeThickness;
                line.Stroke = Brushes.Black;
                line.Name = "Hori" + colNumber.ToString();
                line.X1 = line.X2 = colNumber * cellWidth;
                line.Y1 = 0;
                line.Y2 = canvasBoard.ActualHeight;
                canvasBoard.Children.Add(line);
            }

            for (rowNumber = 0; rowNumber <= board.MaxRows; rowNumber++)
            {
                line = new Line();
                line.StrokeThickness = cellStrokeThickness;
                line.Stroke = Brushes.Black;
                line.Name = "Vert" + rowNumber.ToString();
                line.Y1 = line.Y2 = rowNumber * cellHeight;
                line.X1 = 0;
                line.X2 = canvasBoard.ActualWidth;
                canvasBoard.Children.Add(line);
            }
        }

        private void RemovePieces()
        {
            for (int idx = canvasBoard.Children.Count - 1; idx > 0; idx--)
            {
                if (canvasBoard.Children[idx].GetType() == typeof(Ellipse))
                {
                    canvasBoard.Children.RemoveAt(idx);
                }
            }
        }

        private void OnSetPiece(object sender, SetPieceEventArgs e)
        {
            double cellWidth = canvasBoard.ActualWidth / board.MaxCols;
            double cellHeight = canvasBoard.ActualHeight / board.MaxRows;
            canvasBoard.Dispatcher.Invoke(
                DispatcherPriority.Normal,
                new Action(delegate()
                {
                    double symbolStrokeThickness = 4.0;
                    double vertSymBorderDist = cellHeight / 5.0;
                    double horiSymBorderDist = cellWidth / 5.0;

                    Ellipse ellipse = new Ellipse();
                    ellipse.StrokeThickness = symbolStrokeThickness;
                    ellipse.Stroke = e.playerMaxHasToMove ?
                        new SolidColorBrush(Colors.Orange) : new SolidColorBrush(Colors.DarkRed);
                    ellipse.Fill = e.playerMaxHasToMove ?
                        new SolidColorBrush(Colors.Yellow) : new SolidColorBrush(Colors.Red);
                    ellipse.Width = cellWidth - 2 * horiSymBorderDist;
                    ellipse.Height = cellHeight - 2 * vertSymBorderDist;
                    ellipse.Name = "CellIndex" + e.cellIdx.ToString();
                    canvasBoard.Children.Add(ellipse);

                    Canvas.SetTop(ellipse, (board.MaxRows - 1 - e.cellIdx / board.MaxCols) * cellHeight + vertSymBorderDist);
                    Canvas.SetLeft(ellipse, (board.MaxCols - 1 - e.cellIdx % board.MaxCols) * cellWidth + horiSymBorderDist);
                })
            );
        }
    }
}

using System.Diagnostics;
using System.Threading;

namespace PlasticineTicTacToe
{
    public enum GameState
    {
        running,
        playerMaxWins,
        playerMinWins,
        drawGame,
        abort
    }

    public class Game
    {
        GameState gameState;
        Thread threadGame;

        Player PlayerMin;
        Player PlayerMax;

        Board board = null;
        public delegate void OnSetPiece(object sender, SetPieceEventArgs e);
        public delegate void OnWriteProtokoll(object sender, ProtokollEventArgs e);
        public delegate void OnWriteInfo(object sender, InfoEventArgs e);
        public delegate void OnGameFinished(object sender, GameFinishedEventArgs e);
        public event OnSetPiece SendSetPiece;
        public event OnWriteProtokoll SendWriteProtokoll;
        public event OnWriteInfo SendWriteInfo;
        public event OnGameFinished SendGameFinished;

        public Game(Board board)
        {
            this.board = board;
            gameState = GameState.abort;
        }

        public void Start(Player Max, Player Min)
        {
            PlayerMax = Max;
            PlayerMin = Min;
            board.Init();
            SendWriteInfo(this, new InfoEventArgs(board.PlayerMaxHasToMove));
            threadGame = new Thread(GameLoop);
            threadGame.Start();
        }

        private void GameLoop()
        {
            int moveNumber = 1;
            Move move;
            int nodes;
            int nodesPerSec = 0;
            double seconds = 0.0;
            int evaluateLeaf = 0;

            gameState = GameState.running;
            Stopwatch stopWatch = new Stopwatch();
            do
            {
                stopWatch.Restart();
                if (board.PlayerMaxHasToMove)
                {
                    evaluateLeaf = PlayerMax.SearchMove(board.PlayerMaxHasToMove);
                    stopWatch.Stop();
                    move = PlayerMax.behaviorSearch.BestMove;
                    nodes = PlayerMax.behaviorSearch.Nodes;
                }
                else
                {
                    evaluateLeaf = PlayerMin.SearchMove(board.PlayerMaxHasToMove);
                    stopWatch.Stop();
                    move = PlayerMin.behaviorSearch.BestMove;
                    nodes = PlayerMin.behaviorSearch.Nodes;
                }
                seconds = stopWatch.ElapsedTicks / (double)Stopwatch.Frequency;
                nodesPerSec = (int)((nodes * (double)Stopwatch.Frequency) /
                    stopWatch.ElapsedTicks);

                DoMove(board.PlayerMaxHasToMove, move);
                board.OpponentTurn();
                SendWriteProtokoll(this, new ProtokollEventArgs(moveNumber, move.boardMoveIdxCell,
                    nodes, seconds, nodesPerSec, evaluateLeaf));
                SendWriteInfo(this, new InfoEventArgs(board.PlayerMaxHasToMove));

                moveNumber++;
            } 
            while ((gameState = IsGameFinished()) == GameState.running);
            SendGameFinished(this, new GameFinishedEventArgs(gameState));
        }

        private void DoMove(bool maxHasToMove, Move move)
        {
            board.Do(move, maxHasToMove);
            SendSetPiece(this, new SetPieceEventArgs(maxHasToMove, move.boardMoveIdxCell));
        }

        private GameState IsGameFinished()
        {
            if (board.PlayerMaxHasRow())
                gameState = GameState.playerMaxWins;
            else if (board.PlayerMinHasRow())
                gameState = GameState.playerMinWins;
            else if (board.IsBoardFilled())
                gameState = GameState.drawGame;
            else
                gameState = GameState.running;
            return gameState;
        }

        public void Abort()
        {
            if (threadGame != null)
                threadGame.Abort();
        }
    }
}

public class PlayerHuman : PlayerBase
{
	override public int SearchMove(bool playerMaxHasToMove)
	{
		IdxLastCell = -1;
		bool done = false;
		Move move = new Move();
		nodes = 0;
		do
		{
			while (IdxLastCell < 0) { }
			nodes++;
			move.boardPieceMask = 1UL << IdxLastCell;
			move.boardMoveIdxCell = IdxLastCell;
			done = board.IsAllowedCell(move.boardPieceMask);
		} while (!done);
		board.Do(move, playerMaxHasToMove);
		return 0;
	}
	public void SetInputCell(Point pt)
	{
		IdxLastCell = board.GetCellIdxFrom(pt);
	}
	override protected int Evaluate(bool dummy)
	{
		return 0;
	}
}

class PlayerNegaAlphaBeta : PlayerBase
{
	override public int SearchMove(bool playerMaxHasToMove)
	{
		nodes = 0;
		evalLeaf = NegaAlphaBeta(playerMaxHasToMove, maxSearchDepth,
			int.MinValue / 2, int.MaxValue / 2);
		board.Do(bestMove, playerMaxHasToMove);
		IdxLastCell = bestMove.boardMoveIdxCell;
		return evalLeaf;
	}
	int NegaAlphaBeta(bool playerMaxHasToMove, int searchDepth,
		int alpha, int beta)
	{
		int score;
		if (searchDepth == 0 || board.NoMoveLeft())
		{
			return Evaluate(playerMaxHasToMove);
		}
		foreach (var nextMove in GenerateMoves(playerMaxHasToMove))
		{
			nodes++;
			board.Do(nextMove, playerMaxHasToMove);
			score = -NegaAlphaBeta(!playerMaxHasToMove,
				searchDepth - 1, -beta, -alpha);
			board.delegateUnDo(nextMove, playerMaxHasToMove);
			if (score >= beta)
			{
				return beta;
			}
			if (score > alpha)
			{
				alpha = score;
				if (searchDepth == maxSearchDepth)
					bestMove = nextMove;
			}
		}
		return alpha;
	}
	override protected int Evaluate(bool playerMaxHasToMove)
	{
		int score = 0;
		if (board.PlayerMaxHasRow())
		{
			score += 1;
		}
		if (board.PlayerMinHasRow())
		{
			score -= 1;
		}
		return playerMaxHasToMove ? score : -score;
	}
}

Ihr Name:


Kommentar:


Der Kommentar wurde von einem Menschen verfasst.
Bitte um Antwort. Email: