Ergebnis 1 bis 2 von 2

Snake Spiel, erstellen einer 'KI'

  1. #1 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Crystal Empire
    Beiträge
    11.228
    Ich biete auch mal ne kleine Programmieraufgabe, welche man auf verschiedenste Arten lösen kann.
    Das Spiel Snake, bzw. das erstellen einer Inteligenz, welche dieses Spiel möglichst gut Spielt.

    Die Idee ist, das man verschiedene Implementationen von IMoveStrategie Implementiert und über 10-100 Versuche Prüft welche davon am besten sind.
    Ziel wäre eine Ausbreitung der Schlange auf dem ganzen Spielfeld.
    Möglichkeiten:
    1. Pathfinding
    2. Brute-force
    3. Monte-Carlo
    4. Neuronales Netzwerk
    5. Vorprogrammierter Pfad



    Da die Programmierung des Spieles sehr simpel ist, stelle Ich meinen Code hier hin.
    Basis SourceCode C#:
    Spoiler:(zum lesen bitte Text markieren)

    Spielfeld:
    Code:
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace Snake
    {
        public class SnakeField
        {
            public SnakeField(int inWidth, int inHeight)
            {
                _width = inWidth;
                _height = inHeight;
                Reset(inWidth, inHeight);
            }
    
            private SnakeField() { }
    
            /// <summary>
            /// Wie viele % des Spielfelds deckt die schlange ab?
            /// </summary>
            /// <returns></returns>
            public int Score()
            {
                return _snake.Length() * 100 / _fieldParts.Length;
            }
    
            /// <summary>
            /// Nächster schritt für die Schlange.
            /// </summary>
            /// <returns>False wenn die Schlange ein Hinderniss getroffen hat</returns>
            public bool Next(Direction inDirection)
            {
                if (_gameOver)
                {
                    return false;
                }
    
                _snake.ChangeDirection(inDirection);
    
                var tmpSnakeMovement = _snake.MoveNext();
    
                if (!ValidatePosOutOfBorder(tmpSnakeMovement.NewField))
                {
                    return false;
                }
    
                //Wenn die schlange ein Feld verlässt, ist das Feld danach wieder leer
                if (tmpSnakeMovement.LeftField != null)
                {
                    setFieldPos(tmpSnakeMovement.LeftField.FromLeft, tmpSnakeMovement.LeftField.FromTop, Field.Empty);
                }
    
                var tmpFieldPos = GetFieldValue(tmpSnakeMovement.NewField.FromLeft, tmpSnakeMovement.NewField.FromTop);
                if (tmpFieldPos == Field.Empty)
                {
                    setFieldPos(tmpSnakeMovement.NewField.FromLeft, tmpSnakeMovement.NewField.FromTop, Field.Snake);
                    return true;
                }
                if (tmpFieldPos == Field.Apple)
                {
                    _applesEaten++;
                    setFieldPos(tmpSnakeMovement.NewField.FromLeft, tmpSnakeMovement.NewField.FromTop, Field.Snake);
                    SetNewApple();
                    _snake.AppleEaten();
                    return true;
                }
    
                _gameOver = true;
                return false;
            }
    
            public Direction GetSnakeDirection()
            {
                return _snake.GetDirection();
            }
    
            public FieldPos GetSnakeHeadPosition()
            {
                return _snake.GetCurrentPos();
            }
    
            public int ApplesEaten()
            {
                return _applesEaten;
            }
            private int _applesEaten =0;
    
            /// <summary>
            /// Neuen Apfel setzen.
            /// </summary>
            private void SetNewApple()
            {
                var tmpRnd = new Random();
                while (tmpRnd != null)
                {
                    var tmpValue = tmpRnd.Next(_fieldParts.Length);
                    if (_fieldParts[tmpValue] == Field.Empty)
                    {
                        _fieldParts[tmpValue] = Field.Apple;
                        _applePos = new FieldPos(tmpValue % _width, tmpValue / _width);
                        break;
                    }
                }
            }
    
            public int Width => _width;
            public int Height => _height;
    
            /// <summary>
            /// Feld Validieren
            /// </summary>
            /// <param name="inPos"></param>
            /// <returns></returns>
            private bool ValidatePosOutOfBorder(FieldPos inPos)
            {
                if (inPos.FromLeft < 0
                    || inPos.FromTop < 0)
                {
                    return false;
                }
    
                if (inPos.FromLeft >= _width
                    || inPos.FromTop >= _height)
                {
                    return false;
                }
    
                return true;
            }
    
            /// <summary>
            /// Setzten einer Position
            /// </summary>
            private void setFieldPos(int inFromLeft, int inFromTop, Field inValue)
            {
                _fieldParts[_width * inFromTop + inFromLeft] = inValue;
            }
    
            /// <summary>
            /// Auslesen einer Position
            /// </summary>
            public Field GetFieldValue(int inFromLeft, int inFromTop)
            {
                return _fieldParts[_width * inFromTop + inFromLeft];
            }
    
            public void Reset(int inWidth, int inHeight)
            {
                _fieldParts = new Field[inWidth * inHeight];
                for (var tmpI = _fieldParts.Length-1; tmpI >= 0; tmpI--)
                {
                    _fieldParts[tmpI] = Field.Empty;
                }
    
                //Schlange Positionieren
                _snake = new Snake(new FieldPos(inWidth / 2 - 4, inHeight / 2), Direction.Right, 4);
    
                _gameOver = false;
    
                //Move 4 Steps
                Next(Direction.Right);
                Next(Direction.Right);
                Next(Direction.Right);
                Next(Direction.Right);
                Next(Direction.Right);
    
                SetNewApple();
            }
    
            public SnakeField Clone()
            {
                var tmpField = new SnakeField();
                tmpField._fieldParts = (Field[])_fieldParts.Clone();
                tmpField._width = _width;
                tmpField._height = _height;
                tmpField._applePos = _applePos;
                tmpField._gameOver = _gameOver;
                tmpField._snake = _snake.Clone();
    
                return tmpField;
            }
    
            public FieldPos ApplePos => _applePos;
    
            public Snake GetSnake()
            {
                return _snake;
            }
    
            private Field[] _fieldParts;
            private int _width;
            private int _height;
    
            private FieldPos _applePos;
            private Snake _snake;
            private bool _gameOver = false;
        }
    
        /// <summary>
        /// Position auf dem Feld
        /// </summary>
        public class FieldPos
        {
            public FieldPos(int inFromLeft, int inFromTop)
            {
                FromTop = inFromTop;
                FromLeft = inFromLeft;
            }
    
            public int FromTop;
            public int FromLeft;
    
            public FieldPos Clone() { return new FieldPos(FromLeft, FromTop); }
        }
    
        /// <summary>
        /// Einzelnes Feld auf dem Spielfeld
        /// </summary>
        public enum Field
        {
            Empty = 0,
            Wall = 1,
            Snake = 2,
            Apple = 9
        }
    
        /// <summary>
        /// Move Direction of the Snake
        /// </summary>
        public enum Direction
        {
            Up = 0,
            Right = 1,
            Down = 2,
            Left = 3
        }
    }
    Schlange:
    Code:
    using System;
    using System.Collections.Generic;
    
    namespace Snake
    {
        public class Snake
        {
            public Snake(FieldPos inStartPos, Direction inCurrentDirection, int inStartLength)
            {
                _currentPos = inStartPos;
                _snake = new Queue<FieldPos>(100);
                _shoudLength = inStartLength;
                _currentDirection = inCurrentDirection;
                _oldDirection = inCurrentDirection;
            }
    
            /// <summary>
            /// Schlange bewegt sich
            /// </summary>
            /// <returns></returns>
            public SnakeMovement MoveNext()
            {
                var tmpNewPos = new SnakeMovement {
                    NewField = _currentPos.Clone(),
                };
                switch (_currentDirection)
                {
                    case Direction.Down:
                        tmpNewPos.NewField.FromTop++;
                        break;
                    case Direction.Up:
                        tmpNewPos.NewField.FromTop--;
                        break;
                    case Direction.Left:
                        tmpNewPos.NewField.FromLeft--;
                        break;
                    case Direction.Right:
                        tmpNewPos.NewField.FromLeft++;
                        break;
                }
    
                _oldDirection = _currentDirection;
                if (_snake.Count == _shoudLength)
                {
                    tmpNewPos.LeftField = _snake.Dequeue();
                }
    
                _snake.Enqueue(tmpNewPos.NewField);
                _currentPos = tmpNewPos.NewField;
                return tmpNewPos;
            }
    
            public void AppleEaten()
            {
                _shoudLength += 1;
            }
    
            //Prüfen ob die Richtung nicht 'rückwärts' ist, und sonst die Richtung anpassen
            public bool ChangeDirection(Direction inNewDirection)
            {
                if (Math.Abs((int)inNewDirection - (int)_oldDirection) == 2)
                {
                    return false;
                }
    
                _currentDirection = inNewDirection;
                return true;
            }
    
            public Direction GetDirection()
            {
                return _oldDirection;
            }
    
            public int Length() { 
                return _snake.Count;
            }
    
            /// <summary>
            /// Klonen
            /// </summary>
            /// <returns></returns>
            public Snake Clone()
            {
                var tmpSnake = new Snake(_currentPos, _currentDirection, 4);
                tmpSnake._shoudLength = _shoudLength;
                tmpSnake._currentDirection = _currentDirection;
                tmpSnake._oldDirection = _oldDirection;
                tmpSnake._currentPos = _currentPos;
                tmpSnake._snake = new Queue<FieldPos>(_snake);
                return tmpSnake;
            }
    
            public FieldPos GetCurrentPos()
            {
                return _currentPos;
            }
    
            public Direction GetOldDirection()
            {
                return _oldDirection;
            }
    
            /// <summary>
            /// Soll länge
            /// </summary>
            private int _shoudLength;
    
            /// <summary>
            /// Aktuelle richtung
            /// </summary>
            private Direction _currentDirection;
    
            /// <summary>
            /// Aktuelle richtung
            /// </summary>
            private Direction _oldDirection;
    
            /// <summary>
            /// Aktuelle position
            /// </summary>
            private FieldPos _currentPos;
    
            /// <summary>
            /// Position der Schlangenkörperteile merken
            /// </summary>
            private Queue<FieldPos> _snake;
        }
    
        /// <summary>
        /// Bewegung der Schlange bei einem Taks
        /// </summary>
        public class SnakeMovement
        {
            public FieldPos NewField;
            public FieldPos LeftField;
        }
    }


    Als beispiel für eine solche KI biete Ich eine Basis, welche man schlagen sollte:
    Die Zufallsrichtung:
    Spoiler:(zum lesen bitte Text markieren)
    Code:
    using System;
    
    namespace Snake
    {
        /// <summary>
        /// Strategie für das Bewegen innerhalb des Spielfeldes
        /// </summary>
        public interface IMoveStrategy
        {
            bool SimulateStep();
    
            int StepCount { get;  }
            int Score { get;  }
        }
    
        public class RandomMove:IMoveStrategy
        {
            public RandomMove(SnakeField inField)
            {
                _field = inField;
            }
            private SnakeField _field;
    
            public void Simulate()
            {
                var tmpRunning = true;
                StepCount = 0;
                while (tmpRunning)
                {
                    if (!SimulateStep())
                    {
                        break;
                    }
                }
            }
    
            public bool SimulateStep()
            {
                var tmpPos = new Random().Next(4);
    
                var tmpValue= _field.Next((Direction)tmpPos);
                if (tmpValue)
                {
                    StepCount++;
                    return true;
                }
                return false;
            }
    
            public int StepCount { get; set; }
            public int Score => _field.Score();
        }
    }


    Als weiter Schwierigkeit können später auch Mauern eingefügt werden.
    Das Spielfeld lässt sich als Komma-separierte Liste oder mit COde-generierten mauern recht gut von A nach B bringen.


    EDIT: Habe einen Fehler mit der Position des Apfels behoben und einige Methoden mehr nach Aussen gebracht.
    Für hohe Performance muss man dies so oder so umbauen, weshalb Ich hier einen leichten OOP Ansatz gewählt habe.

    Mit einem einfachen 'Gerade aus auf den Apfel zu' komme Ich auf einen Score von ca. 2,5
    [Bild: AMD_Threadripper.png] Bei Hardware gibt es keine eigene Meinung, bei Hardware zählen nur die Fakten.


    Probleme mit der Haarpracht? Starres Haar ohne Glanz? TressFX schafft Abhilfe. Ja, TressFX verhilft auch Ihnen zu schönem und Geschmeidigen Haar.
    [Bild: i6tfHoa3ooSEraFH63.png]
    Multithread ist offline Geändert von Multithread (12.07.2018 um 21:52 Uhr)

  2. #2 Zitieren
    Pretty Pink Pony Princess  Avatar von Multithread
    Registriert seit
    Jun 2010
    Ort
    Crystal Empire
    Beiträge
    11.228
    Ich scheitere bei meinem KI Ansatz (Genetic Mutation), bereits daran, das mein 'Score', welcher aufzeigt ob die KI gut oder schlecht war, nicht stimmt.

    Ich dachte es wäre klug, die auf folgenden Score anzusetzen:
    Hat die schlange überlebt? +40
    Apfel gegessen? +30
    Felder bewegt: je -1

    Aber das scheint ja kein gutes Snake Game auszumachen.


    Ich arbeite mit einem kleinen Netzwerk (7,25,3)
    Eingaben sind: Feld (geradeaus, rechts, links) Frei?
    Ist die Richtung (geradeaus, rechts, links, rückwärts) näher am Apfel?

    Ausgabe ist eine Richtungsangabe: (geradeaus, rechts, links)

    Irgendwelche Ideen/vorschläge, mit welcher Bewertung ich die AI Tranieren soll?
    [Bild: AMD_Threadripper.png] Bei Hardware gibt es keine eigene Meinung, bei Hardware zählen nur die Fakten.


    Probleme mit der Haarpracht? Starres Haar ohne Glanz? TressFX schafft Abhilfe. Ja, TressFX verhilft auch Ihnen zu schönem und Geschmeidigen Haar.
    [Bild: i6tfHoa3ooSEraFH63.png]
    Multithread ist offline

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •