拼图的人工智能算法的分析,等待的是思考

类别:Java 点击:0 评论:0 推荐:

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.io.*;

/**************************************************
* 类功能简介:游戏场景的实现 2004-03-05
* @author [email protected]
* @version 1.01
**************************************************/

public class GamePlat extends Canvas //implements KeyListener
{
  public static final int BOARDNUM = 3;         //可以活动的元素
  public static final int WIDACTION = 201;      //设置拼图游戏活动场景图片的宽度
  public static final int HEIACTION = 201;      //设置拼图游戏活动场景图片的高度
  public static final int WID = 281;            //设置整个GamePlat的宽度
  public static final int HEI = 281;            //设置整个GamePlat的高度

  private int [][] boardArray;                  //游戏里面的可以变换的数组

  private final int [][] WINARRAY = {{0,1,2},   //设定游戏成功的条件
                                     {3,4,5},
                                     {6,7,8}};
  private int stepNum = 0;                      //记录玩家走走过的步骤

  private Random rand = null;
  private Toolkit tk = null;
  private Image spiriteImage = null;
  private int x8 = BOARDNUM-1,y8 = x8;

  /**************************************************
  * 构造方法:构造整个游戏最重要的数据
  ***************************************************/

  public GamePlat()
  {
    tk = getToolkit();
    rand = new Random();
    boardArray = new int[BOARDNUM][BOARDNUM];
    try
    {
      spiriteImage = tk.createImage("photo.jpg");
    }
    catch (Exception ex)
    {
      System.out.println(ex.getMessage());
    }
    init();
  }

  /**************************************************
  * 方法介绍:初始化记录步骤和并随机生成每个数组里面的值
  * 输入参数:无
  * 返回类型:无
  ****************************************************/

  public void init()
  {
    stepNum = 0;
    generateBoardNum();
  }

  /**************************************************
  * 方法介绍:随机生成每个数组里面的值
  * 输入参数:无
  * 返回类型:无
  ****************************************************/

  private void generateBoardNum()
  {
    int k=0;
    for (int i = 0 ; i < 3 ; i++)
      for (int j = 0 ; j < 3 ; j++)
      {
        boardArray[i][j] = k++;
      }
      for (int i = 0 ; i < 100 ; i++)
      {
        int x1,y2,x2,y1,temp;
        x1=Math.abs(rand.nextInt()%3);
        x2=Math.abs(rand.nextInt()%3);
        y1=Math.abs(rand.nextInt()%3);
        y2=Math.abs(rand.nextInt()%3);
        temp = boardArray[x1][y1];
        boardArray[x1][y1]=boardArray[x2][y2];
        boardArray[x2][y2]=temp;
      }
      int x=0,y=0,temp;
      for (int i = 0 ; i < 3 ; i++)
        for(int j = 0 ; j < 3 ; j++)
        {
          if(boardArray[i][j]==8)
          {
            x=i;
            y=j;
            System.out.println("Now the X"+i+" & Y"+j+" & boardArrayVALUE is : X : "+x+" Y : "+y+" BV : "+boardArray[i][j]);
            break;
          }
        }
      System.out.println("Now the X2 & Y2 & boardArrayVALUE is : X : 2 Y : 2 BV : "+boardArray[2][2]);
      if(x == 2 && y == 2)
        return;
      else
      {
        temp = boardArray[2][2];
        boardArray[2][2]=8;
        boardArray[x][y]=temp;
      }
      //cheat();
      testArray(boardArray);
    }

    /**************************************************
     * 方法介绍:作弊,用来测试人工智能
     * 输入参数:无
     * 返回类型:无
     ****************************************************/
    public void cheat()
    {
      System.out.println("CHEAT:)");
      int k = 0;
      for (int i = 0 ; i < BOARDNUM ; i++)
      {
        for (int j = 0; j < BOARDNUM; j++)
        {
          boardArray[i][j] = k++;
        }
      }

      boardArray [0][2]=2;
      boardArray [1][2]=8;
      boardArray [2][2]=5;
      for (int i = 0 ; i < BOARDNUM ; i++)
      {
        for (int j = 0; j < BOARDNUM; j++)
        {
          System.out.print(boardArray[i][j] + " ");
        }
        System.out.println();
      }


    }

    /**************************************************
    * 方法介绍:int [][]引用的数组中的值按一定格式输出
    * 输入参数:int [][]
    * 返回类型:无
    ****************************************************/

   private void testArray(int [][] args)
   {
     System.out.println("TEST THE ARRAY");
     for (int i = 0; i < BOARDNUM; i++)
     {
       for (int j = 0; j < BOARDNUM; j++)
       {
         System.out.print( args[i][j] +" ");
       }
       System.out.println();
     }
   }
   /**************************************************
    * 方法介绍:让存储8的元素和它下面的元素交换,这种方法完
    * 成得方法效率可能稍差,但这是为了能够扩展人工智能而不
    * 得不采取得方法,因为如果不知道8的位置,人工智能就不
    * 能实现
    * 输入参数:int [][]
    * 返回类型:int [][]
    ****************************************************/

   private int [][] updateDown(int [][] args)
   {
     int [][] tempArr = new int [BOARDNUM][BOARDNUM];
     for (int i = 0 ; i < BOARDNUM ; i++)
       for (int j = 0 ; j < BOARDNUM ; j++)
       {
         tempArr [i][j] = args[i][j];
       }
     int x8 =0,y8=0;
     for (int i = 0 ; i < 3 ; i++)
        for(int j = 0 ; j < 3 ; j++)
        {
          if(tempArr[i][j]==8)
          {
            x8=i;
            y8=j;
            //System.out.println("Now the X"+i+" & Y"+j+" & boardArrayVALUE is : X : "+x8+" Y : "+y8+" BV : "+tempArr[i][j]);
            break;
          }
        }

     if (x8 != 2)
     {
       int temp = tempArr[x8+1][y8];
       tempArr[x8+1][y8] = tempArr[x8][y8];
       tempArr[x8][y8] = temp;
     }
     return tempArr;
   }

   /**************************************************
    * 方法介绍:让存储8的元素和它上面的元素交换,这种方法完
    * 成得方法效率可能稍差,但这是为了能够扩展人工智能而不
    * 得不采取得方法,因为如果不知道8的位置,人工智能就不
    * 能实现
    * 输入参数:int [][]
    * 返回类型:int [][]
    ****************************************************/


   private int [][] updateUp(int [][] args)
   {
     int [][] tempArr = new int [BOARDNUM][BOARDNUM];
     for (int i = 0 ; i < BOARDNUM ; i++)
       for (int j = 0 ; j < BOARDNUM ; j++)
       {
         tempArr [i][j] = args[i][j];
       }
     int x8 =0,y8=0;
     for (int i = 0 ; i < 3 ; i++)
        for(int j = 0 ; j < 3 ; j++)
        {
          if(tempArr[i][j]==8)
          {
            x8=i;
            y8=j;
           // System.out.println("Now the X"+i+" & Y"+j+" & boardArrayVALUE is : X : "+x8+" Y : "+y8+" BV : "+tempArr[i][j]);
            break;
          }
        }

      if (x8 != 0)
      {
        int temp = tempArr[x8-1][y8];
        tempArr [x8-1][y8] = tempArr[x8][y8];
        tempArr [x8][y8] = temp;
      }
      return tempArr;

   }

   /**************************************************
    * 方法介绍:让存储8的元素和它右面的元素交换,这种方法完
    * 成得方法效率可能稍差,但这是为了能够扩展人工智能而不
    * 得不采取得方法,因为如果不知道8的位置,人工智能就不
    * 能实现
    * 输入参数:int [][]
    * 返回类型:int [][]
    ****************************************************/

   private int [][] updateRight(int [][] args)
   {
     int [][] tempArr = new int [BOARDNUM][BOARDNUM];
     for (int i = 0 ; i < BOARDNUM ; i++)
       for (int j = 0 ; j < BOARDNUM ; j++)
       {
         tempArr [i][j] = args[i][j];
       }
     int x8 =0,y8=0;
     for (int i = 0 ; i < 3 ; i++)
        for(int j = 0 ; j < 3 ; j++)
        {
          if(tempArr[i][j]==8)
          {
            x8=i;
            y8=j;
           // System.out.println("Now the X"+i+" & Y"+j+" & boardArrayVALUE is : X : "+x8+" Y : "+y8+" BV : "+tempArr[i][j]);
            break;
          }
        }

     if (y8 != 2)
     {
       int temp = tempArr [x8][y8+1];
       tempArr [x8][y8+1] = tempArr [x8][y8];
       tempArr [x8][y8] = temp;
     }
     return tempArr;
   }

   /**************************************************
    * 方法介绍:让存储8的元素和它左面的元素交换,这种方法完
    * 成得方法效率可能稍差,但这是为了能够扩展人工智能而不
    * 得不采取得方法,因为如果不知道8的位置,人工智能就不
    * 能实现
    * 输入参数:int [][]
    * 返回类型:int [][]
    ****************************************************/

 

   private int [][] updateLeft(int [][] args)
   {
     int [][] tempArr = new int [BOARDNUM][BOARDNUM];
     for (int i = 0 ; i < BOARDNUM ; i++)
       for (int j = 0 ; j < BOARDNUM ; j++)
       {
         tempArr [i][j] = args[i][j];
       }
     int x8 =0,y8=0;
     for (int i = 0 ; i < 3 ; i++)
        for(int j = 0 ; j < 3 ; j++)
        {
          if(tempArr[i][j]==8)
          {
            x8=i;
            y8=j;
            //System.out.println("Now the X"+i+" & Y"+j+" & boardArrayVALUE is : X : "+x8+" Y : "+y8+" BV : "+tempArr[i][j]);
            break;
          }
        }

     if (y8 != 0)
     {
       int temp = tempArr [x8][y8-1];
       tempArr [x8][y8-1] = tempArr [x8][y8];
       tempArr [x8][y8] = temp;
     }
     return tempArr;
   }

   /**************************************************
    * 方法介绍:程序调试时使用的接口,实现了数组的变换
    * 输入参数:无
    * 返回类型:无
    **************************************************/

   public void mainCallLeft()
   {
     boardArray = updateLeft(boardArray);
     testArray(boardArray);
   }

   /**************************************************
    * 方法介绍:程序调试时使用的接口,实现了数组的变换
    * 输入参数:无
    * 返回类型:无
    **************************************************/

   public void mainCallRight()
   {
     boardArray = updateRight(boardArray);
     testArray(boardArray);
   }
   /**************************************************
    * 方法介绍:程序调试时使用的接口,实现了数组的变换
    * 输入参数:无
    * 返回类型:无
    **************************************************/

   public void mainCallUp()
   {
     boardArray = updateUp(boardArray);
     testArray(boardArray);
   }

   /**************************************************
    * 方法介绍:程序调试时使用的接口,实现了数组的变换
    * 输入参数:无
    * 返回类型:无
    **************************************************/

   public void mainCallDown()
   {
     boardArray = updateDown(boardArray);
     testArray(boardArray);
   }
   /**************************************************
    * 方法介绍:判断是否已经排列正确
    * 输入参数:int [][]
    * 返回类型:boolean
    **************************************************/

   private boolean isOrder(int [][] args)
   {
     for (int i = 0 ; i < BOARDNUM ; i++)
         for (int j = 0 ; j < BOARDNUM ; j++)
         {
           if (args [i][j] != WINARRAY[i][j])
             return false;
         }
      return true;
   }
   /**************************************************
    * 方法介绍:程序调试时使用的接口,实现了人工智能变换
    * 输入参数:无
    * 返回类型:无
    **************************************************/

   public void aI()
   {
     Vector [] binTree = new Vector [2];              //建立两颗二叉树存储数组状态
     StringBuffer [] strDir = new StringBuffer [2];   //建立两颗二叉树存储搜索方向
     for ( int i = 0 ; i < 2 ; i++)
       for (int j = 0 ; j < 2 ; j++)
       {
         binTree [i] = new Vector(0,1);
         strDir [i] =  new StringBuffer("");
       }
     if (isOrder(boardArray))
     {
       System.out.println("The Tree Not Construct , and the answer is OK");
       return;
     }
     else
     {
       int [][] tempArr;

       strDir [0].append("U");                         //方向树的根结点
       tempArr = updateUp(boardArray);
       //testArray(tempArr);
       if(isOrder(tempArr))
       {
         System.out.println("The answer found at the first time use the direction tree");
         System.out.println(strDir [0].toString());
         return;
       }
       binTree [0].addElement(tempArr);


       strDir[1].append("L");
       tempArr = updateLeft(boardArray);
       //testArray(tempArr);
       if(isOrder(tempArr))
       {
         System.out.println("The answer found at the first time use the direction tree");
         System.out.println(strDir [1].toString());
         return;
       }
       binTree[1] . addElement(tempArr);
       System.out.println("The tree become useful in searching the answer for every successful condidtion");
       int stepRecord = 0;
       for ( stepRecord = 0 ; ; stepRecord++)
       {
         System.out.println(stepRecord);
         for (int i = 0 ; i < 2 ; i++)
         {
           int less = (int)(Math.pow(2,stepRecord)) - 1;
           int large = (int)(Math.pow(2,stepRecord+1)) - 1;
           for (int k = less ; k < large ; k++)
           {
             int [][] theCurrentState = (int [][])binTree [i].elementAt(k);
             if (strDir [i].charAt(k) == 'L' || strDir [i].charAt(k) == 'R')
             {
               strDir[i].append("U");
               tempArr = updateUp(theCurrentState);
               //testArray(tempArr);
               if(isOrder(tempArr))
               {
                 System.out.println("The answer found when constructing tree");
                 System.out.println(strDir [i].toString());
                 return;
               }
               binTree [i].addElement(tempArr);
               strDir[i].append("D");
               tempArr = updateDown(theCurrentState);
               //testArray(tempArr);
               if(isOrder(tempArr))
               {
                 System.out.println("The answer found when constructing tree");
                 System.out.println(strDir [i].toString());
                 return;
               }
               binTree [i].addElement(tempArr);


             }
             else
             {
               strDir[i].append("L");
               tempArr = updateLeft(theCurrentState);
               //testArray(tempArr);
               if(isOrder(tempArr))
               {
                 System.out.println("The answer found when constructing tree");
                 System.out.println(strDir [i].toString());
                 return;
               }
               binTree [i].addElement(tempArr);
               strDir[i].append("R");
               tempArr = updateRight(theCurrentState);
               //testArray(tempArr);
               if(isOrder(tempArr))
               {
                 System.out.println("The answer found when constructing tree");
                 System.out.println(strDir [i].toString());
                 return;
               }
               binTree [i].addElement(tempArr);

             }
           }
         }
       }
     }
     //The AI has work well , but you will can't get the answer except:
     //First you know have to make up a tree & how the use the last leave
     //to find the root . The way like this : the N --->the least leave
     //the step is : (N+1)/2 - 1 -> N
     ///             (N+1)/2 - 1 -> N
     ///               ...............
     ///                        0 ->      and you will found the answer is
     //correct may be not optimisted! copyright : [email protected]
     //modified for the www.csdn.net         .    regards......
     //The most importand method in this file .  2004-03-06.
   }

 

    /**************************************************
    * 方法介绍:测试数据的正确与否
    * 输入参数:String []
    * 返回类型:无
    ****************************************************/
    public static void  main(String [] args) throws Exception
    {
      GamePlat gp = new GamePlat();
      InputStreamReader reader = new InputStreamReader(System.in);
      BufferedReader input = new BufferedReader(reader);
      System.out.println("Now you can play the Game in console!");
      System.out.println("Following are commands");
      System.out.println("up");
      System.out.println("down");
      System.out.println("left");
      System.out.println("right");
      System.out.println("demoai");
      System.out.println("restart");
      System.out.println("exit");
      while(true){
        System.out.print("->");
        String command = input.readLine();
        if(command.equals("exit"))
        {
          break;
        }
        else if (command.equals("left"))
        {
           gp.mainCallLeft();
        }
        else if (command.equals("right"))
        {
           gp.mainCallRight();
        }
        else if (command.equals("up"))
        {
           gp.mainCallUp();
        }
        else if (command.equals("down"))
        {
          gp.mainCallDown();
        }
        else if (command.equals("demoai"))
        {
          gp.aI();
        }
        else if (command.equals("cheat"))
        {
          gp.cheat();
        }
        else if (command.equals("restart"))
        {
          gp.init();
        }

        else
        {
          System.out.println(command+" is not support ~Z");
        }

      }
    }
}

寒假时候为了给同学演示怎样做个游戏,而做了一个最简单的拼图游戏。规则,如下,生成 0 1 2 3 4 5 6 7 8 个数列,然后随机的放到一个二维数组里面:
比如:
1 3 2
4 6 5
0 7 8
8总是在最右脚,智能用8和他临近的值交换。直到得到如下序列游戏成功?;
0 1 2
3 4 5
6 7 8
。现在我想让游戏具有人工智能,用自己的思考建造一棵搜索树,找到一个路径,自己排列数组:
于是我编了一个简单的控制台程序,建了一些命令和程序交互,当输入demoai的时候,人工智能启动,计算了超过3个小时也没有得到结果!后来,我加入了一条cheat的命令,把初始值定义为:
0 1 8
3 4 2
6 7 5
:其实,人一眼就看出只需走两步:
然后我运行demoai,
可以看到计算机是如此思考的:
G:\PTGAI>java GamePlat
Now the X2 & Y1 & boardArrayVALUE is : X : 2 Y : 1 BV : 8
Now the X2 & Y2 & boardArrayVALUE is : X : 2 Y : 2 BV : 6
Now you can play the Game in console!
Following are commands
up
down
left
right
demoai
restart
exit
->cheat
CHEAT:)
0 1 2
3 4 8
6 7 5
->demoai
The tree become useful in searching the answer for every successful condidtion
0
1
2
3
The answer found when constructing tree
ULRUDUDLRLRLRLRUDUDUDUDUDUDUDUD
->
结果分析:
U L R U D U D L R L R L R L R U D U D U D U D U D U D U D U D
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
0 0U

 


1 1L 2R


2 3U 4D 5U 6D


3 7L 8R 9L 10R 11L 12R 13L 14R


4 15U 16D U17 18D U19 20D U21 22D U23 24D U25 26D U27 28D U29 30D

G:\PTGAI>java GamePlat
Now the X0 & Y1 & boardArrayVALUE is : X : 0 Y : 1 BV : 8
Now the X2 & Y2 & boardArrayVALUE is : X : 2 Y : 2 BV : 2
TEST THE ARRAY
5 2 7
3 1 6
4 0 8
Now you can play the Game in console!
Following are commands
up
down
left
right
demoai
restart
exit
->cheat
CHEAT:)
0 1 2
3 4 8
6 7 5
->up
TEST THE ARRAY
0 1 8
3 4 2
6 7 5
->right
TEST THE ARRAY
0 1 8
3 4 2
6 7 5
->down
TEST THE ARRAY
0 1 2
3 4 8
6 7 5
->right
TEST THE ARRAY
0 1 2
3 4 8
6 7 5
->down
TEST THE ARRAY
0 1 2
3 4 5
6 7 8
->exit

G:\PTGAI>
够恐怖吧?

欢迎批评指正,

希望有人找到更好的智能方法告诉我!

本文地址:http://com.8s8s.com/it/it16779.htm