Robin Chiu: TicTacToe 井字遊戲

由來

最近看到小朋友在玩 OOXX 也就是井字遊戲，很簡單，很耐玩的小小遊戲，就想說來implement一下這個東西。

井字遊戲

規則很簡單，九宮格，一人畫一個輪流，三個連成線就贏了！誰先手的話，贏面比較大。

AI

在AI的書中，OOXX幾乎是標準的教材，在wikipedia上面查詢TicTacToe 也有分析的步驟 http://en.wikipedia.org/wiki/Tic-tac-toe ，所以就加上AI 的功能，這個 AI 很容易就可以走完所有的走法，從中選出最好的，所以 AI 是不敗的，反而人類一不小心就會犯錯！
AI 的方法就是標準的Game tree search 進化成 Minmax ( http://en.wikipedia.org/wiki/Minmax )
，再簡化成 Negamax ( http://en.wikipedia.org/wiki/Negamax )，後面還有 Alpha Beta Pruning 的方式來加快運算的速度，不過因為只有九宮格，很容易就運算完畢，這部分就省下了！實際上implement 時第一步需要記下來走法和分數，用來決定下一步怎麼走，也是就 rootsearch function。
後面有加上random 來選出相同分數的走法，以免AI 都是走同一步，但是因為都是選最高分，所以 AI 還是不敗的，呵呵！


package com.robin.tictactoe;

import java.util.ArrayList;
import java.util.Date;


public class AI {
 char marker;
 char opponentmarker;
 long initTime = 0;
 long nowTime = 0;
 int number = 0;
 char type = 'C';
 
 
 public AI(char marker) {
  this.marker = marker;
  if(marker == 'X')
   opponentmarker = 'O';
  else
   opponentmarker = 'X';
 }
 
 void move(Game game) {
  initTime = new Date().getTime();
  number = 0;
  int move = rootsearch(game, 1);
  game.move(marker, move);
 }
 
 int get_score(Game game) {
  number++;
  if(game.is_gameover()) {
   if(game.winner==marker)
    return 1;
   else if(game.winner==opponentmarker)
    return -1;
  }
  return 0;
 }
 
 int rootsearch(Game game, int color) {
    int bestmove = -999;
    int bestscore = -999;

    // get the possible move
    ArrayList moves = game.get_move();
    ArrayList candidate = new ArrayList();
    
    for(int i=0; i bestscore) {
        bestscore = score;
        bestmove = moves.get(i);
        candidate.clear();        
        candidate.add(moves.get(i));
      } else if(score == bestscore) {
        candidate.add(moves.get(i));
      }
    }
    bestmove = candidate.get((int)Math.floor(Math.random()*candidate.size()));
    return bestmove;
 }
 
 int negamax(Game game, int color) {
  int bestscore = -999;
  // get the score
  if(game.is_gameover()) {
   bestscore = color * get_score(game);
  } else {
   //get the possible moves
   ArrayList moves = game.get_move();
   for(int i=0; i bestscore) {
     bestscore = score;
    }
   }
  }
  return bestscore;
 }
}

Html5

最近 html5 滿紅的，抓來的code原本是 python 寫的，想來改寫成 javascript，順便熟悉一下html5的新功能！



// Robin Chiu : hcchiu63@gmail.com
// 2014/06/20 the first version

var context;
var width, height;

var output = output || {};

output.paintBoard = function(){
   var board = document.getElementById('board');
  
   width = board.width;
   height = board.height;
   context = board.getContext('2d');
   context.clearRect (0, 0, width , height);

   context.beginPath();
   context.strokeStyle = '#000'; 
   context.lineWidth   = 4;

   context.moveTo((width / 3), 0);
   context.lineTo((width / 3), height);

   context.moveTo((width / 3) * 2, 0);
   context.lineTo((width / 3) * 2, height);

   context.moveTo(0, (height / 3));
   context.lineTo(width, (height / 3));

   context.moveTo(0, (height / 3) * 2);
   context.lineTo(width, (height / 3) * 2);

   context.stroke();
   context.closePath();
}

output.paintAIinfo = function() {
  var moveInfo = document.getElementById('moveInfo');
  moveInfo.innerHTML = '<h3> AI result:</h3>' +
                       '<br />Time:' + (AI.nowTime-AI.initTime) + 'ms' +
                       '<br />Calculate number:' + AI.number;

}

output.paintX = function(x, y) {

   context.beginPath();

   context.strokeStyle = '#ff0000'; 
   context.lineWidth   = 4;

   var offsetX = (width / 3) * 0.1;
   var offsetY = (height / 3) * 0.1;

   var beginX = x * (width / 3) + offsetX;
   var beginY = y * (height / 3) + offsetY;

   var endX = (x + 1) * (width / 3) - offsetX * 2;
   var endY = (y + 1) * (height / 3) - offsetY * 2;

   context.moveTo(beginX, beginY);
   context.lineTo(endX, endY); 

   context.moveTo(beginX, endY);
   context.lineTo(endX, beginY);  

   context.stroke();
   context.closePath(); 
}

output.paintO = function(x, y) {
  
   context.beginPath();

   context.strokeStyle = '#0000ff'; 
   context.lineWidth   = 4;

   var offsetX = (width / 3) * 0.1;
   var offsetY = (height / 3) * 0.1;

   var beginX = x * (width / 3) + offsetX;
   var beginY = y * (height / 3) + offsetY;

   var endX = (x + 1) * (width / 3) - offsetX * 2;
   var endY = (y + 1) * (height / 3) - offsetY * 2;

   context.arc(beginX + ((endX - beginX) / 2), beginY + ((endY - beginY) / 2), (endX - beginX) / 2 , 0, Math.PI * 2, true);

   context.stroke();
   context.closePath();
}


var game = game || {};

// game init function
game.init = function() {
  game.board = ['-','-','-','-','-','-','-','-','-'];
  game.moves = [];
  game.winner = "-";
}

// print the current status of game
game.print = function() {
  // print the board
  output.paintBoard();
  // print the O and X
  for(var i=0; i<9; i++) {
    var x = i%3;
    var y = Math.floor(i/3);
    if(game.board[i]=="O")
      output.paintO(x, y);
    else if(game.board[i]=="X")
      output.paintX(x, y);
  }

  // AI information 
  output.paintAIinfo();

  // console debug
  for(var i=0; i<9; i=i+3) {
    console.info(game.board[i] + ", " + game.board[i+1] + ", " + game.board[i+2]);
  }
}

// get the next move array
game.get_move = function() {
  var empty = [];
  for(var i=0; i<game.board.length; i++) {
    if(game.board[i] == "-")
      empty.push(i);
  }
  return empty;
}

// put some item to the position
game.move = function(marker, pos) {
  game.board[pos] = marker;
  game.moves.push(pos);
}

game.is_gameover = function() {
  var win_position = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]];
  // check the patten
  for(var i=0; i<win_position.length; i++) {
    var p = win_position[i];
    if(game.board[p[0]]==game.board[p[1]] && game.board[p[0]]==game.board[p[2]] && game.board[p[0]] != '-') {
      game.winner = game.board[p[0]];
      return true;
    }
  }
  
  // check the if it's full
  for(var i=0; i<game.board.length; i++) {
    if(game.board[i] == "-") {
      game.winner = "-";
      return false;
    }
  }

  return true;
}

// revert last move
game.revert = function() {
  var pos = game.moves.pop();
  game.board[pos] = '-';
  game.winner = "-";
}


var AI = AI || {};

AI.init = function(marker) {
  AI.marker = marker;
  AI.initTime = 0;
  AI.nowTime = 0;
  AI.number = 0;
  AI.type = "C";
  if(AI.marker == "X") 
    AI.opponentmarker = "O";
  else
    AI.opponentmarker = "X";
}

AI.move = function(gameinstance) {
  AI.initTime = new Date().getTime();
  AI.number = 0;
  var move = AI.rootsearch(gameinstance, 1);
  AI.nowTime = new Date().getTime();
  //var move_position = 4;
  gameinstance.move(AI.marker, move);
}

AI.get_score = function(gameinstance) {
  AI.number++;
  if(gameinstance.is_gameover()) {
    if(gameinstance.winner == AI.marker)
      return 1;
    else if(gameinstance.winner == AI.opponentmarker)
      return -1;
  }
  return 0;
}

AI.rootsearch = function(gameinstance, color) {
  var bestmove = -999;
  var bestscore = -999;

  // get the possiable move
  var moves = gameinstance.get_move();
  var candidate = [];

  for(var i=0; i<moves.length; i++) {
    // set the move
    if(color == 1)
      gameinstance.move(AI.marker, moves[i]);
    else
      gameinstance.move(AI.opponentmarker, moves[i]);
    // get the score
    var score = -1 * AI.negamax(gameinstance, -color);

    // revert the move
    gameinstance.revert();
    // get the max score
    if(score > bestscore) {
      bestscore = score;
      bestmove = moves[i];
      candidate=[];
      candidate.push(moves[i])
    } else if(score == bestscore) {
      candidate.push(moves[i]);
    }
  }
  bestmove = candidate[Math.floor(Math.random()*candidate.length)];
  return bestmove;
}

AI.negamax = function(gameinstance, color) {
  var bestscore = -999;

  //get the score
  if(gameinstance.is_gameover()) {
    return color * AI.get_score(gameinstance);
  } else {
    // get the possiable move
    var moves = gameinstance.get_move();

    for(var i=0; i<moves.length; i++) {
      // set the move
      if(color == 1)
        gameinstance.move(AI.marker, moves[i]);
      else
        gameinstance.move(AI.opponentmarker, moves[i]);
      // get the score
      var score = -1 * AI.negamax(gameinstance, -color);

      // revert the move
      gameinstance.revert();
      // get the max score
      if(score > bestscore) {
        bestscore = score;
      }
    }
    return bestscore;
  }
}


var Human = Human || {};

Human.init = function(marker) {
  Human.marker = marker;
  Human.type = 'H';
}

Human.move = function(gameinstance, pos) {
  gameinstance.move(Human.marker, pos);
}

function clickHandler(e) {
    var y = Math.floor(e.clientY / (height / 3));    
    var x =  Math.floor(e.clientX / (width/ 3)); 
    var pos =  x + ( y * 3 );

    if(game.board[pos]!="-") {
      alert("invalid position...");
      return;
    }
    // Human move
    Human.move(game, pos);
    game.print();
    check();

    // AI move
    AI.move(game);
    game.print();
    check();
}

function check() {
  if(game.is_gameover()) {
    if(game.winner == AI.marker) 
      alert("AI win...");
    else if(game.winner == Human.marker)
      alert("You win...");
    else
      alert("Nobody win...");
    game.init();
    game.print();
  }
}


function Play() {
  game.init();
  game.print();
  Human.init("X");
  AI.init("O");
}

Android

有時間再將 html5 改寫成 Android，說實在Android上面的 TicTacToe 實在太多了，但是我下載了幾個，玩起來總覺得沒有畫在紙上好玩的感覺，後來覺得是在紙上畫上格子玩，把整張紙畫的滿滿的趣味不見了，所以Android的方向就改成接近原本在紙上的玩法！

想玩的話，可以上google play download，網址如下：

https://play.google.com/store/apps/details?id=com.robin.tictactoe

Robin Chiu

2014年8月18日星期一

TicTacToe 井字遊戲

由來

井字遊戲

AI

Html5

Android

沒有留言:

張貼留言

2014年8月18日 星期一

TicTacToe 井字遊戲

由來

井字遊戲

AI

Html5

Android

沒有留言:

張貼留言

2014年8月18日星期一