fengartai.cs

本代码是为了应付人工智能的实验而编写的

/*----------------------------------------------------------------
          // Copyright (C) 2007 Fengart
          // 版权所有。 
          // 开发者：Fengart
          // 文件名：FengartAI.cs
          // 文件功能描述：这是一个能够解决八数码问题的高效方法，主要体现在对状态编码上。
 /*----------------------------------------------------------------
    //主页：http://fengart.9126.com
    //blog: http://blog.csdn.net/fengart
    //Emial: [e-mail]
//----------------------------------------------------------------*/
using System;
using System.Collections.Generic;

namespace Eight_Num_Fengart
{
    /// <summary>
    /// 棋盘结构
    /// </summary>
    class FengartAI
    {
        #region 代码说明

        /*编码规则： 
         * 每一个状态及每一次操作的表示方法？
         * 有许多表示方法，比如一个3*3的八数码盘可以压缩成一个int值表示，但不适用于15 puzzle或大于8 的
         * puzzle问题。如果对空间要求很高，应该还可以再压缩。本文采用一个int表示的方法。
         * 表示方法如下：由于int的表示范围大于1e9，所以我们取一个int的低9位，为了方便寻找空格的位置，int
         * 的个位我们用来放空格的位置（1-9）。而前8位，按照行从上到下，列从左到右的顺序依次记录对应位置上
         * 的数字。例如：        
         * 可以表示成 2 3 1 5 8 4 6 7 5 ，个位的5表示空格在第5位，前八位数按顺序记录。坐标转换公式为：
    num（压缩后的int） x y（求x行y列,1记起）1e(n)为 1乘10的n次
    int temp=(x-1)*3+y
    if  temp > num%10 then return (num / 1e(9-temp+1)) %10
    else return (num / 1e(9-temp) )%10

    为了方便本文介绍，取目标状态为：1 2 3 4 5 6 7 8 9 即-->

        操作本文用 u r d l 分别表示 空格的向上 向右 向下 向左 四个操作。比如，在简介中的图包括两步操作 l d ，可能与平时玩这类游戏的习惯不符合，但这是为了和ACM例题相统一。

    对应地，每种操作引起的状态变化如下：
    r ：num值++             l ：num值--
    u ：有点复杂 
    int t0 = 9-num%10 + 1
    int t1 = num / 1e(t0)
    int t2 = t1%1000
    t1= t1- t2 + (t2 % 100) * 10 + t2 / 100
    t1*= 1e(t0)
    return (t1 + ( (num % t0) - 3))
    d ：见代码的change方法。
         * 
         * 以上编码规则是参考了网上一位朋友的文章，我在此编码的基础上加了估值，例如num=2 3 1 5 8 4 6 7 5,
         * 估值假设为5，那么编码成code=5 2 3 1 5 8 4 6 7 5,估值写在最前面,那么调用SortedList时就可以直接
         * 让SortedList自己进行排序(当然,如果你想自己编写一个delegate来交给SortedList实现也是没问题的,但
         * 我没测试过,不知道效率如何),那么现在的code就是由一个10位十进制的数组成,code已经不能再用int表示
         * 了,因此我用了long (很不情愿,但想了很久还是用上了)。
         * 
         * 另外我之前编了个也是解决八数码问题的深度优先递归算法，棋盘采用一维结构，却比这个搜索的时间短，
         * 但不及“最好优先搜索”，主要是“最好优先搜索”所搜索的结点数实在是太少了，尽管排序浪费的时间
         * 比较多，但测试过N次，性能最好的就是它。
         * 
         * 本代码是为了应付人工智能的实验而编写的，写的潦草请不要介意。我又是通过这代码来“引玉”，相信
         * 看过我编写的黑白棋源代码的人应该知道“引玉”是什么意思。如果你有“玉”（什么更高效的算法能在
         * 更短的时间内求得结果，或者博弈方面的），就欢迎“砸”过来[e-mail]，我会很感激！
         * （A 星算法解决八数码问题我已经研究过了，不要砸这个来）
         *                                                                          Fengart 
         *                                                                        2007.6.16
         * 
         */

        #endregion 

        /// <summary>
        /// ten[i]代表10的i次方
        /// </summary>
        private static readonly long[] tens ={ 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

        /// <summary>
        /// 不是合理的编码
        /// </summary>
        private const int OutOfCode = -1;

        /// <summary>
        /// 标志是否找到目标状态的编码
        /// </summary>
        public const int WinnerCode = 1;

        private Direction[][] dirs;

        private int startBoard;
        private static int endBoard;
        private static int[] endBoardArray;

        private int MaxDepth;

        private SortedList<long,StateMsg> openList;
        private Stack<State> openStack;
        private Queue<State> openQueue;
        private Dictionary<long,StateMsg> boardtable;

        private const int maxNodes = 362880; //至多搜索的结点数＝最大局面状态数量：（9!）=362880；

        private int nodes;
        private int same;
        private float time;
        private Direction[] result;

        /// <summary>
        /// 已经访问的结点数量
        /// </summary>
        public int Nodes
        {
            get { return nodes; }
        }

        /// <summary>
        /// 重复访问相同结点的数量
        /// </summary>
        public int Same
        {
            get { return same; }
        }

        public float Time
        {
            get { return time; }
        }

        /// <summary>
        /// 最终结果
        /// </summary>
        public Direction[] Result
        {
            get { return result; }
        }

        public FengartAI()
        {
            dirs = new Direction[9][];
            dirs[0] = new Direction[] { Direction.Right, Direction.Down };
            dirs[1] = new Direction[] { Direction.Left, Direction.Right, Direction.Down };
            dirs[2] = new Direction[] { Direction.Left, Direction.Down };
            dirs[3] = new Direction[] { Direction.Up, Direction.Right, Direction.Down };
            dirs[4] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
            dirs[5] = new Direction[] { Direction.Up, Direction.Left, Direction.Down };
            dirs[6] = new Direction[] { Direction.Up, Direction.Right };
            dirs[7] = new Direction[] { Direction.Left, Direction.Right, Direction.Up };
            dirs[8] = new Direction[] { Direction.Up, Direction.Left };

        }

        /// <summary>
        /// 求与目标位置不同的个数（不计空格，因此返回值0～8）
        /// </summary>
        /// <param name="curboard"></param>
        /// <returns></returns>
        public static int Different(int curboard)
        {
            int t_start = curboard;
            int emp_start = curboard % 10;
            int ev = 0;
            //写2个for是为了减少9个if
            for (int i = 9; i > emp_start; i--)
            {
                t_start /= 10;
                if (t_start % 10 != endBoardArray[i])
                    ev++;
            }
            for (int i = emp_start - 1; i >= 1; i--)
            {
                t_start /= 10;
                if (t_start % 10 != endBoardArray[i])
                    ev++;
            }
            return ev;
        }

        public static int getBoard(long code)
        {
            return (int)(code % tens[9]);
        }

        private static int getEval(long code)
        {
            return (int)(code / tens[9]);
        }

        private static int getEmpIndex(long code)
        {
            return (int)(code % 10);
        }

        private static long combinCode(int board, int eval)
        {
            long codehead = eval * tens[9];
            return codehead + board;
        }

        /// <summary>
        /// 改变局面(移动空格)
        /// </summary>
        /// <param name="code"></param>
        /// <param name="dir"></param>
        public static long change(long code, Direction dir)
        {
            int newboard;
            int eval;
            int num;
            int t0;
            long t1;
            long t2;
            switch (dir)
            {
                case Direction.Left:
                    newboard = getBoard(code) - 1;
                    if (newboard == endBoard)
                        return WinnerCode;
                    eval = Different(newboard);
                    return combinCode(newboard, eval);
                case Direction.Right:
                    newboard = getBoard(code) + 1;
                    if (newboard == endBoard)
                        return WinnerCode;
                    eval = Different(newboard);
                    return combinCode(newboard, eval);
                case Direction.Up:
                    num = getBoard(code);
                    t0 = 9 - num % 10 + 1;
                    t1 = num / tens[t0];
                    t2 = t1 % 1000;
                    t1 = t1 - t2 + (t2 % 100) * 10 + t2 / 100;
                    t1 *= tens[t0];
                    newboard = (int)(t1 + ((num % tens[t0]) - 3));
                    if (newboard == endBoard)
                        return WinnerCode;
                    eval = Different(newboard);
                    return combinCode(newboard, eval);
                case Direction.Down:
                    num = getBoard(code);
                    t0 = 9 - num % 10 + 1 - 3;//跟Up不同的地方
                    t1 = num / tens[t0];
                    t2 = t1 % 1000;
                    t1 = t1 - t2 + (t2 % 10) * 100 + t2 / 10;//跟Up不同的地方
                    t1 *= tens[t0];
                    newboard = (int)(t1 + ((num % tens[t0]) + 3));//跟Up不同的地方
                    if (newboard == endBoard)
                        return WinnerCode;
                    eval = Different(newboard);
                    return combinCode(newboard, eval);
            }
            return OutOfCode;
        }

        /// <summary>
        /// 恢复上一步的局面
        /// </summary>
        /// <param name="code"></param>
        /// <param name="dir"></param>
        public long unchange(long code, Direction dir)
        {
            return change(code, (Direction)(5 - dir));
        }

        /// <summary>
        /// 当找到目标时，从哈希表里找原来的路径
        /// </summary>
        /// <param name="endCode"></param>
        /// <param name="depth"></param>
        private void setResult(long endCode, Direction curDir, Direction lastDir, int depth)
        {
            long lastCode = endCode;
            result = new Direction[depth];
            result[depth - 1] = curDir;
            for (int i = depth - 2; i >= 0; i--)
            {
                if (boardtable.ContainsKey(lastCode))
                {
                    result[i] = boardtable[lastCode].Dir;
                    lastCode = unchange(lastCode, result[i]);
                }
                else
                    return;
            }
        }

        //本算法的核心部分

        #region 带Open表和HashTable的最好优先搜索(每次扩展Open表后都对Open表排序）

        /// <summary>
        ///  扩展Open表
        /// </summary>
        /// <param name="board"></param>
        /// <param name="depth"></param>
        private bool extentOpenList(long code, Direction lastDir, int depth)
        {
            int empIndex = (int)(code % 10 - 1);
            int len_moves = dirs[empIndex].Length;
            long newcode;
            Direction dir = 5 - lastDir;
            for (int i = 0; i < len_moves; i++)
                if (dirs[empIndex][i] != dir)
                {
                    newcode = change(code, dirs[empIndex][i]);

                    //跟目标匹配,结束
                    if (newcode == WinnerCode)
                    {
                        setResult(code, dirs[empIndex][i], lastDir, depth);
                        return true;
                    }
                    if (newcode <= tens[8])
                        throw new Exception("棋盘码修改错误！ ");
                    if (newcode != OutOfCode)
                    {
                        if (!openList.ContainsKey(newcode))
                        {
                            if (!boardtable.ContainsKey(newcode))
                                openList.Add(newcode, new StateMsg(depth, dirs[empIndex][i]));
                            else
                            {
                                same++;
                                if (depth < boardtable[newcode].Depth)
                                {
                                    boardtable.Remove(newcode);
                                    openList.Add(newcode, new StateMsg(depth, dirs[empIndex][i]));
                                }
                            }
                        }
                        else
                        {
                            same++;
                            if (depth < openList[newcode].Depth)
                                openList[newcode] = new StateMsg(depth, dirs[empIndex][i]);
                        }
                    }
                }
            return false;
        }

        /// <summary>
        /// 带Open表和HashTable的最好优先搜索(每次扩展Open表后都对Open表排序）
        /// </summary>
        /// <returns></returns>
        private int BestFirstSearch()
        {
            int depth = 1;
            Direction[] moves;
            int board;
            long newCode = combinCode(this.startBoard, 0);
            int empIndex = getEmpIndex(newCode);

            moves = dirs[empIndex - 1];
            StateMsg data;
            if (extentOpenList(newCode, Direction.None, depth))
                return WinnerCode;
            while (openList.Count > 0)
            {
                lock (this)
                {
                    nodes++;
                    if (nodes >= maxNodes)
                        return -1;
                    newCode = openList.Keys[0];
                    board = getBoard(newCode);
                    data = openList[newCode];
                    if (data.Depth != 0)
                    {