API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 24th, 2018
69
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JavaScript 12.66 KB | None | 0 0
raw download clone embed print report
  1. function p10602_08()
  2. {
  3.     /*--------------------------------Step2. 調控變數--------------------------------*/
  4.     var step = 3;           //表示要預測到幾步(>0)後，若為負數(<0)則為預測到底(即有勝負)為止，若為0則為隨便亂下
  5.     var UsePrunning = true; //表示是否要剪枝，若為false，則只是單純的MINMAX演算法
  6.  
  7.     //計算盤面分數
  8.     //chessData:目前的棋盤狀況(15x15)  /  MyColor:AI的顏色(黑1,白-1)  /  lastColor:「上一步」下的人的顏色  /  (lastStepX, lastStepY):「上一步」下的位置
  9.     this.Score = function(chessData, MyColor, lastColor, lastStepX, lastStepY)
  10.     {
  11.         /*--------------------------------Step3. 修改 Score function中的變數--------------------------------*/
  12.         var MyScore = 0, EnemyScore = 0;
  13.         /*============ 加速1. 只從有棋子(即1或-1)的地方嘗試延伸Pattern，也就是空格(0)不能為Pattern起點 e.g., [0,1,1,1,1,0] 應拆開為 [[0],[1,1,1,1,0]] ============*/
  14.         var MyPattern = [[1,1,1,1,1],    [[0],[1,1,1,1,0]],    [[0],[1,1,1,0]],    [[0],[1,1,0]] ];
  15.         var EnemyPattern = [[1,1,1,1,1],    [[0],[1,1,1,1,0]],    [[0],[1,1,1,0]]];
  16.         var MyAdd = [10000, 800, 100, 10];
  17.         var EnemyAdd = [10000, 1000, 100, 10];
  18.         var multiplier = 1;
  19.         var multiflag = 0;
  20.         var MyPositionAdd = [
  21.         [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  22.         [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
  23.         [ 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0 ],
  24.         [ 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0 ],
  25.         [ 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0 ],
  26.         [ 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0 ],
  27.         [ 0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0 ],
  28.         [ 0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0 ],
  29.         [ 0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0 ],
  30.         [ 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0 ],
  31.         [ 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0 ],
  32.         [ 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0 ],
  33.         [ 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0 ],
  34.         [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
  35.         [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ];
  36.         var EnemyPositionAdd = [
  37.         [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  38.         [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
  39.         [ 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0 ],
  40.         [ 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0 ],
  41.         [ 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0 ],
  42.         [ 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0 ],
  43.         [ 0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0 ],
  44.         [ 0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0 ],
  45.         [ 0, 1, 2, 3, 4, 5, 6, 6, 6, 5, 4, 3, 2, 1, 0 ],
  46.         [ 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0 ],
  47.         [ 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 3, 2, 1, 0 ],
  48.         [ 0, 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0 ],
  49.         [ 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0 ],
  50.         [ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
  51.         [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] ];
  52.         /*--------------------------------修改結束--------------------------------*/
  53.        
  54.         for(var x = 0; x < 15; ++x)
  55.         {
  56.             for(var y = 0; y < 15; ++y)
  57.             {
  58.                 if(chessData[x][y] == 0)
  59.                     continue;
  60.                 if(chessData[x][y] == MyColor)
  61.                     MyScore += MyPositionAdd[x][y];
  62.                 for(var i = 0; i < MyPattern.length; ++i)
  63.                 {
  64.                     if(!Array.isArray(MyPattern[i][0])) multiplier
  65.                     {
  66.                         if(this.Match(x, y, 0, -1, MyPattern[i], MyColor))  //往上找
  67.                         {
  68.                             if(i == 3) multiflag = true;
  69.                             MyScore += MyAdd[i];
  70.                         }
  71.                         if(this.Match(x, y, 0, 1, MyPattern[i], MyColor))   //往下找
  72.                         {
  73.                             if(i == 3) multiflag = true;
  74.                             MyScore += MyAdd[i];
  75.                         }
  76.                         if(this.Match(x, y, -1, 0, MyPattern[i], MyColor))    //往左找
  77.                         {
  78.                             if(i == 3) multiflag = true;
  79.                             MyScore += MyAdd[i];
  80.                         }
  81.                         if(this.Match(x, y, 1, 0, MyPattern[i], MyColor)){  //往右找
  82.                             if(i == 3) multiflag = true;
  83.                             MyScore += MyAdd[i];
  84.                         }
  85.                         if(this.Match(x, y, -1, -1, MyPattern[i], MyColor)){    //往左上找
  86.                             if(i == 3) multiflag = true;
  87.                             MyScore += MyAdd[i];
  88.                         }
  89.                         if(this.Match(x, y, -1, 1, MyPattern[i], MyColor)){ //往左下找
  90.                             if(i == 3) multiflag = true;
  91.                             MyScore += MyAdd[i];
  92.                         }
  93.                         if(this.Match(x, y, 1, -1, MyPattern[i], MyColor)){ //往右上找
  94.                             if(i == 3) multiflag = true;
  95.                             MyScore += MyAdd[i];
  96.                         }
  97.                         if(this.Match(x, y, 1, 1, MyPattern[i], MyColor)){  //往右下找
  98.                             if(i == 3) multiflag = true;
  99.                             MyScore += MyAdd[i];
  100.                         }
  101.                     }
  102.                     else //---------------------------------------------------------------
  103.                     {
  104.                         if(this.Match(x, y+1, 0, 1, MyPattern[i][0], MyColor) && this.Match(x, y, 0, -1, MyPattern[i][1], MyColor))     //往上找
  105.                             MyScore += MyAdd[i];
  106.                         if(this.Match(x, y-1, 0, -1, MyPattern[i][0], MyColor) && this.Match(x, y, 0, 1, MyPattern[i][1], MyColor))     //往下找
  107.                             MyScore += MyAdd[i];
  108.                         if(this.Match(x+1, y, 1, 0, MyPattern[i][0], MyColor) && this.Match(x, y, -1, 0, MyPattern[i][1], MyColor))     //往左找
  109.                             MyScore += MyAdd[i];
  110.                         if(this.Match(x-1, y, -1, 0, MyPattern[i][0], MyColor) && this.Match(x, y, 1, 0, MyPattern[i][1], MyColor))     //往右找
  111.                             MyScore += MyAdd[i];
  112.                         if(this.Match(x+1, y+1, 1, 1, MyPattern[i][0], MyColor) && this.Match(x, y, -1, -1, MyPattern[i][1], MyColor))  //往左上找
  113.                             MyScore += MyAdd[i];
  114.                         if(this.Match(x+1, y-1, 1, -1, MyPattern[i][0], MyColor) && this.Match(x, y, -1, 1, MyPattern[i][1], MyColor))  //往左下找
  115.                             MyScore += MyAdd[i];
  116.                         if(this.Match(x-1, y+1, -1, 1, MyPattern[i][0], MyColor) && this.Match(x, y, 1, -1, MyPattern[i][1], MyColor))  //往右上找
  117.                             MyScore += MyAdd[i];
  118.                         if(this.Match(x-1, y-1, -1, -1, MyPattern[i][0], MyColor) && this.Match(x, y, 1, 1, MyPattern[i][1], MyColor))  //往右下找
  119.                             MyScore += MyAdd[i];
  120.                     }
  121.                 }
  122.             if(multiflag){
  123.                 multiplier *= 4;
  124.                 multiflag = false;
  125.             }
  126.             }
  127.         }
  128.        
  129.         for(var x = 0; x < 15; ++x)
  130.         {
  131.             for(var y = 0; y < 15; ++y)
  132.             {
  133.                 if(chessData[x][y] == 0)
  134.                     continue;
  135.                 if(chessData[x][y] == -MyColor)
  136.                     EnemyScore += EnemyPositionAdd[x][y];
  137.                 for(var i = 0; i < EnemyPattern.length; ++i)
  138.                 {
  139.                     if(!Array.isArray(EnemyPattern[i][0]))
  140.                     {
  141.                         if(this.Match(x, y, 0, -1, EnemyPattern[i], -MyColor))  //往上找
  142.                             EnemyScore += EnemyAdd[i];
  143.                         if(this.Match(x, y, 0, 1, EnemyPattern[i], -MyColor))   //往下找
  144.                             EnemyScore += EnemyAdd[i];
  145.                         if(this.Match(x, y, -1, 0, EnemyPattern[i], -MyColor))  //往左找
  146.                             EnemyScore += EnemyAdd[i];
  147.                         if(this.Match(x, y, 1, 0, EnemyPattern[i], -MyColor))   //往右找
  148.                             EnemyScore += EnemyAdd[i];
  149.                         if(this.Match(x, y, -1, -1, EnemyPattern[i], -MyColor)) //往左上找
  150.                             EnemyScore += EnemyAdd[i];
  151.                         if(this.Match(x, y, -1, 1, EnemyPattern[i], -MyColor))  //往左下找
  152.                             EnemyScore += EnemyAdd[i];
  153.                         if(this.Match(x, y, 1, -1, EnemyPattern[i], -MyColor))  //往右上找
  154.                             EnemyScore += EnemyAdd[i];
  155.                         if(this.Match(x, y, 1, 1, EnemyPattern[i], -MyColor))   //往右下找
  156.                             EnemyScore += EnemyAdd[i];
  157.                     }
  158.                     else
  159.                     {
  160.                         if(this.Match(x, y+1, 0, 1, EnemyPattern[i][0], -MyColor) && this.Match(x, y, 0, -1, EnemyPattern[i][1], -MyColor))     //往上找
  161.                             EnemyScore += EnemyAdd[i];
  162.                         if(this.Match(x, y-1, 0, -1, EnemyPattern[i][0], -MyColor) && this.Match(x, y, 0, 1, EnemyPattern[i][1], -MyColor))     //往下找
  163.                             EnemyScore += EnemyAdd[i];
  164.                         if(this.Match(x+1, y, 1, 0, EnemyPattern[i][0], -MyColor) && this.Match(x, y, -1, 0, EnemyPattern[i][1], -MyColor))     //往左找
  165.                             EnemyScore += EnemyAdd[i];
  166.                         if(this.Match(x-1, y, -1, 0, EnemyPattern[i][0], -MyColor) && this.Match(x, y, 1, 0, EnemyPattern[i][1], -MyColor))     //往右找
  167.                             EnemyScore += EnemyAdd[i];
  168.                         if(this.Match(x+1, y+1, 1, 1, EnemyPattern[i][0], -MyColor) && this.Match(x, y, -1, -1, EnemyPattern[i][1], -MyColor))  //往左上找
  169.                             EnemyScore += EnemyAdd[i];
  170.                         if(this.Match(x+1, y-1, 1, -1, EnemyPattern[i][0], -MyColor) && this.Match(x, y, -1, 1, EnemyPattern[i][1], -MyColor))  //往左下找
  171.                             EnemyScore += EnemyAdd[i];
  172.                         if(this.Match(x-1, y+1, -1, 1, EnemyPattern[i][0], -MyColor) && this.Match(x, y, 1, -1, EnemyPattern[i][1], -MyColor))  //往右上找
  173.                             EnemyScore += EnemyAdd[i];
  174.                         if(this.Match(x-1, y-1, -1, -1, EnemyPattern[i][0], -MyColor) && this.Match(x, y, 1, 1, EnemyPattern[i][1], -MyColor))  //往右下找
  175.                             EnemyScore += EnemyAdd[i];
  176.                     }
  177.                 }
  178.             }
  179.         }
  180.  
  181.         return (MyScore*multiplier) - EnemyScore;
  182.     }
  183.  
  184.     //檢查由(x,y)位置往(dirX, dirY)方向延伸，是否可以找到所傳入的Pattern
  185.     this.Match = function(x, y, dirX, dirY, Pattern, MyColor)
  186.     {
  187.         var n = Pattern.length;
  188.         if(x+dirX*(n-1) < 0 || x+dirX*(n-1) > 14 || y+dirY*(n-1) < 0 || y+dirY*(n-1) > 14)
  189.             return false;
  190.         else
  191.         {
  192.             for(var i = 0; i < n; ++i)
  193.             {
  194.                 if(Pattern[i] == 0 && chessData[x][y] != 0)
  195.                     return false;
  196.                 else if(Pattern[i] == 1 && chessData[x][y] != MyColor)
  197.                     return false;
  198.                 else if(Pattern[i] == -1 && chessData[x][y] == MyColor)
  199.                     return false;
  200.                 x += dirX;
  201.                 y += dirY;
  202.             }
  203.             return true;
  204.         }
  205.     }
  206.  
  207.     //執行MINMAX + AlphaBeta剪枝(UsePrunning為true)，或僅執行MINMAX(UsePrunning為false)
  208.     //CurrentColor:「準備」下的顏色  /  (lastStepX, lastStepY):「上一步」下的位置
  209.     this.AlphaBeta = function(chessData, step, alpha, beta, MyColor, CurrentColor, lastStepX, lastStepY)
  210.     {
  211.         //預測到這步就好 或者是 已經有結果(有預測的上一步並且因此分出勝負)，就開始把值回傳
  212.         if(  step == 0 || (lastStepX != -1 && lastStepY != -1 && judge(lastStepX, lastStepY, -CurrentColor))  )
  213.             return [lastStepX, lastStepY, this.Score(chessData, MyColor, -CurrentColor, lastStepX, lastStepY)];
  214.        
  215.         //否則預測所有可能的下一步
  216.         var NotCut = true;      //設定是否已經開始被剪枝
  217.         var BestX, BestY;       //最好那步的(x,y)
  218.         var x = 7, y = 7;
  219.        
  220.         /*============ 加速2. 對於所有分枝，先走好的-->再走壞的，讓壞的有機會被剪掉；若相反，先走壞的-->再走好的，則不會做剪枝 ============*/
  221.         //天元是最好的，嘗試走下在天元的分枝
  222.         if(chessData[x][y] == 0)
  223.         {
  224.             chessData[x][y] = CurrentColor;
  225.             var move = this.AlphaBeta(chessData, step-1, alpha, beta, MyColor, -CurrentColor, x, y)
  226.             chessData[x][y] = 0;
  227.            
  228.             if(MyColor == CurrentColor)    
  229.             {
  230.                 if(alpha < move[2])
  231.                 {
  232.                     alpha = move[2];
  233.                     BestX = x;
  234.                     BestY = y;
  235.                 }
  236.             }
  237.             else                           
  238.             {
  239.                 if(beta > move[2])
  240.                 {
  241.                     beta = move[2];
  242.                     BestX = x;
  243.                     BestY = y;
  244.                 }
  245.             }
  246.             if(UsePrunning && beta <= alpha)
  247.                 NotCut = false;
  248.         }
  249.         //從天元開始，由內而外、順時針尋找空格、走分枝
  250.         var circle = 1, times = 1;
  251.         var dir = [[1,0],[0,1],[-1,0],[0,-1]];
  252.         var choess = 0;
  253.         var temp = circle;
  254.         while(true)
  255.         {
  256.             x += dir[choess][0];
  257.             y += dir[choess][1];
  258.             if(chessData[x][y] == 0)
  259.             {
  260.                 //嘗試在空的位置下準備要下的顏色的棋
  261.                 chessData[x][y] = CurrentColor;
  262.                 //計算下一層的AlphaBeta值
  263.                 var move = this.AlphaBeta(chessData, step-1, alpha, beta, MyColor, -CurrentColor, x, y)
  264.                 //把空的位置復原
  265.                 chessData[x][y] = 0;
  266.                
  267.                 //根據是自己或對方的回合，決定剪枝根據
  268.                 if(MyColor == CurrentColor)    
  269.                 {
  270.                     if(alpha < move[2])
  271.                     {
  272.                         alpha = move[2];
  273.                         BestX = x;
  274.                         BestY = y;
  275.                     }
  276.                 }
  277.                 else                           
  278.                 {
  279.                     if(beta > move[2])
  280.                     {
  281.                         beta = move[2];
  282.                         BestX = x;
  283.                         BestY = y;
  284.                     }
  285.                 }
  286.                 //正式剪枝
  287.                 if(UsePrunning && beta <= alpha)
  288.                     NotCut = false;
  289.             }
  290.             if(!NotCut || (x == 14 && y == 0))
  291.                 break;
  292.            
  293.             temp--;
  294.             if(temp == 0)
  295.             {
  296.                 choess = (choess+1)%4;
  297.                 if(times > 0)
  298.                 {
  299.                     temp = circle;
  300.                     --times;
  301.                 }
  302.                 else
  303.                 {
  304.                     times = 1;
  305.                     ++circle;
  306.                     temp = circle;
  307.                 }
  308.             }
  309.         }
  310.        
  311.         //如果是自己的回合，則回傳最好(MAX)的選擇(alpha)；如果是對方的回合，則回傳最差(MIN)的選擇(beta)
  312.         if(MyColor == CurrentColor)        
  313.             return [BestX, BestY, alpha];
  314.         else                           
  315.             return [BestX, BestY, beta];
  316.     }
  317.  
  318.     //AI主程式
  319.     this.AI = function(chessData, MyColor)
  320.     {
  321.         var move;
  322.         if(step == 0)
  323.             move = Random(chessData);
  324.         else
  325.             move = this.AlphaBeta(chessData, step, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY, MyColor, MyColor, -1, -1);
  326.         drawChess(move[0], move[1]);
  327.     }
  328.  
  329.     //隨機在空格下一子
  330.     this.Random = function(chessData)
  331.     {
  332.         var x, y;
  333.         while(true)
  334.         {
  335.             x = Math.floor(Math.random()*15);
  336.             y = Math.floor(Math.random()*15);
  337.             if(chessData[x][y] == 0)
  338.                 break;
  339.         }
  340.         return [x,y];
  341.     }
  342. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!