תכנות: אלגוריתם - mixmax

[izikon]

ה-mixmax הוא אלגוריתם אפשרי למשחקים כאשר יש רק ניצחון או הספד
כמו שחמט או איקס עיגול
בגדול מדובר באלגוריטם של מקסימום ניחצון במינימום צעדים כאשר כול בחירה של צעד מוגדר ע"י דרגה
אפשר לקרוא כאן על ה mixmax
http://en.wikipedia.org/wiki/Minimax

אני רוצה להסביר ולתת דוגמא על משחק האיקס עיגול

נתחיל בייצירת לוח המשחק

Syntax: [ Download ] [ Hide ]

Syntax: [ Download ] [ Show ]

Using actionscript3 Syntax Highlighting

package
{
        public class Board
        {
                private var _squares:Array;
                public function Board(x:int,y:int,squares:Array=null)
                {
                        if(squares)     {
                                _squares = cloneArray(squares);
                        }else{
                                buildBoard(x,y);
                        }
                }
               
                public function setPlace(place:Place):void      {
                        _squares[place.Y][place.X] = place;
                }
               
                public function get isFull():Boolean    {
                        for each(var cols:Array in _squares)    {
                                for each(var place:Place in cols)       {
                                        if(place.Player==Player.OPEN)   return false;
                                }
                        }
                        return true;
                }
               
                public function get isWinner():int      {
                        var counterX:int = 0;
                        var counterO:int = 0;
                        for each(var cols:Array in _squares)    {
                                for each(var place:Place in cols)       {
                                        if(place.Player == Player.X)    {
                                                counterX++
                                        }
                                        if(place.Player == Player.O)    {
                                                counterO++;
                                        }
                                }
                        }
                       
                        if(counterO==3) {
                                return Player.O;;
                        }
                        if(counterX==3) {
                                return Player.X;
                        }
                        return -1;
                }
               
                public function get openPlaces():Array  {
                        var opens:Array = new Array();
                        for each(var cols:Array in _squares)    {
                                for each(var place:Place in cols)       {
                                        if(place.Player==Player.OPEN)   {
                                                opens.push(place);
                                        }
                                }
                        }
                        return opens;
                }
               
                public function get squares():Array     {
                        return _squares;
                }
               
                public function clone():Board   {
                        return new Board(0,0,_squares);
                }
               
                private function buildBoard(x:int,y:int):void   {
                        var place:Place;
                        _squares = new Array();
                        for(var yy:int=0;yy<y;yy++)     {
                                _squares[yy] = new Array();
                                for(var xx:int=0;xx<x;xx++)     {
                                        place = new Place();
                                        place.X = xx;
                                        place.Y = yy;
                                        place.Player = Player.OPEN;
                                        _squares[yy][xx] = place;
                                }
                        }
                }
               
                private function cloneArray(squ:Array):Array    {
                        var newSeq:Array = new Array();
                        var newPlace:Place
                        for(var y:int=0;y<squ.length;y++)       {
                                newSeq[y] = new Array();
                                for(var x:int=0;x<squ[y].length;x++)    {
                                        newSeq[y][x] = squ[y][x].clone();
                                }
                        }
                        return newSeq;
                }
        }
}
 

Parsed in 0.041 seconds, using GeSHi 1.0.8.4

כפי שניתן לראות מדובר בלוח המחזיר מטריצה של 3 על 3 שבכול אחד קיימת מחלקת PLACE
מחלקת PLACE היא מחלקת מידע שמכילה את המיקום והשחק שיושב בתוכה כמו כן היא מכילה את הדרגה שלה שזה קשור באלגורתם של mixmax

Syntax: [ Download ] [ Hide ]

Syntax: [ Download ] [ Show ]

Using actionscript3 Syntax Highlighting

package
{
        public class Place
        {
                public var Player:int;
                public var Rank:int;
                public var X:int;
                public var Y:int;
                public function clone():Place
                {
                        var newPlace:Place = new Place();
                        newPlace.X                      = this.X;
                        newPlace.Y                      = this.Y;
                        newPlace.Rank           = this.Rank;
                        newPlace.Player         = this.Player;
                        return newPlace;
                }
        }
}
 

Parsed in 0.029 seconds, using GeSHi 1.0.8.4

מחלקת Player היא מחלקה אינומרית של סוג השחקן

Syntax: [ Download ] [ Hide ]

Syntax: [ Download ] [ Show ]

Using actionscript3 Syntax Highlighting

package
{
        public class Player
        {
                static public const X:int = 1;
                static public const O:int = 2;
                static public const OPEN:int = 0;
        }
}
 

Parsed in 0.030 seconds, using GeSHi 1.0.8.4

כעת אנחנו ניבנה את הAI של המחשב שהוא צריך לחשב את הדרך הכי טובה לניצחון במינימום צעדים

Syntax: [ Download ] [ Hide ]

Syntax: [ Download ] [ Show ]

Using actionscript3 Syntax Highlighting

package
{
        public class AI
        {
                public static function getBestMoves(board:Board,player:int):Place               {
                        var bestPlace:Place;
                        var newPlace:Place;
                        var tempPlace:Place
                        var openSpaces:Array = board.openPlaces;
                        var newBoard:Board;
                        for each(var place:Place in openSpaces) {
                                newBoard = board.clone();
                                newPlace = place.clone();
                                newPlace.Player = player;
                                newBoard.setPlace(newPlace);
                                if(newBoard.isWinner==-1 && newBoard.openPlaces.length>0)       {
                                        tempPlace = getBestMoves(newBoard,(player==Player.X) ? Player.O : Player.X);
                                        newPlace.Rank = tempPlace.Rank;
                                }else{
                                        if(newBoard.isWinner==-1)       {
                                                newPlace.Rank = 0;
                                        }else if(newBoard.isWinner==Player.X){
                                                newPlace.Rank = -1;
                                        }else if(newBoard.isWinner==Player.O)   {
                                                newPlace.Rank = 1;
                                        }
                                }
                               
                                if(bestPlace==null ||
                                        (player==Player.X && newPlace.Rank < bestPlace.Rank) ||
                                        (player==Player.O && newPlace.Rank > bestPlace.Rank) )
                                        {
                                                bestPlace = newPlace;
                                        }
                        }
                        return bestPlace;
                }
        }
}
 

Parsed in 0.034 seconds, using GeSHi 1.0.8.4

כפי שניתן לראות האלגוריטם הרקורסיבי מייצר אצת המצב הכי אופטימאלי לניצחון תוך כדי ייצירה של לוחות חדשים עם דימוי של צעדים

כעת אנחנו צריכים לחבר את כול המחלקות שבנינו למחלקה הראשית המטפלת בלוגיקה

Syntax: [ Download ] [ Hide ]

Syntax: [ Download ] [ Show ]

Using actionscript3 Syntax Highlighting

package
{
        import flash.display.Sprite;
       
        public class Algorithm extends Sprite
        {
                public function Algorithm()
                {
                        var place:Place
                        //create the board
                        var board:Board = new Board(3,3);
                        //user move
                        board.squares[1][1].Player = Player.O;
                        //CPU move
                        place = AI.getBestMoves(board,Player.X);
                        board.setPlace(place);
                        //user move
                        board.squares[0][1].Player = Player.O;
                        //CPU move
                        place = AI.getBestMoves(board,Player.X);
                }
        }
}
 

Parsed in 0.032 seconds, using GeSHi 1.0.8.4

עם תרשמו את הקוד הזה ותעשו breakpoint אחרי הplace השני אתם תראו שהוא באמת בוחר מיקום אפטימאלי במחינתו להשמה של המיקום כדי להביא לידי ניצחון

מישהו יכול לרשום אלגוריטים מתאים למשחק שחמט על בסיס האלגוריתם הנוכחי?