Reversi with CPU
Implemented weak CPU
* ** Implemented static evaluation logic
* ** Implemented MinMax method
/**
* Copyright rso ( http://wonderfl.net/user/rso )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/3XTy
*/
// forked from bkzen's Reversi
/*
* Implemented weak CPU
* ** Implemented static evaluation logic
* ** Implemented MinMax method
*/
package
{
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.GradientType;
import flash.display.Graphics;
import flash.display.Loader;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Matrix;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.net.URLRequest;
import flash.system.LoaderContext;
import flash.text.TextField;
/**
* リバーシ
* @mxmlc -o bin/Reversi.swf -load-config+=obj\Alltest3Config.xml
* @author jc at bk-zen.com
*/
[SWF (backgroundColor = "0xFFFFFF", frameRate = "30", width = "465", height = "465")]
public class Reversi extends Sprite
{
private const phaseInit: int = 0;
private const phaseStart: int = 1;
private const phaseTurnInit: int = 5;
private const phaseTurnWait: int = 6;
private const phaseTurnStoneMove: int = 7;
private const phaseTurnChange: int = 8;
private const phaseResult: int = 50;
private const phaseEnd: int = 100;
private const STN_URL: String = "http://assets.wonderfl.net/images/related_images/b/bc/bc29/bc29dba5e4eb1b1e57129ac8dc783a8347c5c2f3";
private var phase: int = phaseInit;
private var board: Board;
private var boardBase: Shape;
private var boardView: BitmapData;
private var cellNavi: Sprite;
private var cellBtns: Array = [];
private var cellBtnFirst: CellBtn;
private var stnRect: Rectangle;
private var stnPoint: Point;
private var player1: Player;
private var player2: Player;
private var nowTurn: int;
private var pass: int;
private var infoTxt: TextField;
private var stoneBmd: BitmapData;
private var loader: Loader;
private var cpu : abstractCPU;
public function Reversi()
{
if (stage) init();
else addEventListener(Event.ADDED_TO_STAGE, init);
}
private function init(e: Event = null): void
{
removeEventListener(Event.ADDED_TO_STAGE, init);
//
loader = new Loader();
loader.contentLoaderInfo.addEventListener(Event.COMPLETE, onComp);
loader.load(new URLRequest(STN_URL), new LoaderContext(true));
}
/**
* 石画像読み込み完了
* @param e
*/
private function onComp(e: Event): void
{
loader.contentLoaderInfo.removeEventListener(Event.COMPLETE, onComp);
stoneBmd = Bitmap(loader.content).bitmapData;
make();
addEventListener(Event.ENTER_FRAME, loop);
}
/**
* 色々作る
*/
private function make():void
{
board = new Board();
boardBase = new Shape();
cellNavi = new Sprite();
var g: Graphics = boardBase.graphics;
var m: Matrix = new Matrix();
m.createGradientBox(SIZE, SIZE, 45 * Math.PI / 180);
g.beginGradientFill(GradientType.LINEAR, [0x00CC00, 0x006600], [1, 1], [0x00, 0xFF], m);
g.lineStyle(1);
var ix: int, iy: int, beforeBtn: CellBtn;
for (var i:int = 0; i < LENGTH; i++)
{
ix = (i % 8) * CEL_SIZE;
iy = (i >> 3) * CEL_SIZE;
var cellBtn: CellBtn = new CellBtn(ix, iy, i, onClickCell);
cellNavi.addChild(cellBtn);
cellBtns.push(cellBtn);
if (beforeBtn == null) cellBtnFirst = beforeBtn = cellBtn;
else beforeBtn = beforeBtn.next = cellBtn;
g.drawRect(ix, iy, CEL_SIZE, CEL_SIZE);
}
var bmp: Bitmap = new Bitmap(boardView = new BitmapData(SIZE, SIZE, true, 0x0), "auto", true);
bmp.x = boardBase.x = cellNavi.x = board.x;
bmp.y = boardBase.y = cellNavi.y = board.y;
addChild(boardBase);
addChild(bmp);
addChild(cellNavi);
stnRect = new Rectangle(0, 0, CEL_SIZE, CEL_SIZE);
stnPoint = new Point();
infoTxt = new TextField();
infoTxt.background = infoTxt.border = true;
infoTxt.width = stage.stageWidth - board.x * 2;
infoTxt.height = stage.stageHeight - SIZE - board.y * 3;
infoTxt.x = board.x;
infoTxt.y = board.y * 2 + SIZE;
addChild(infoTxt);
cpu = new MinMaxCPU(STN_W, 2);
}
/**
* セルをクリックしたときのイベントハンドラ
* @param e
*/
private function onClickCell(e: MouseEvent):void
{
var i: int = CellBtn(e.target).index;
var cb: CellBtn = cellBtnFirst;
do { cb.visible = false; } while (cb = cb.next);
board.put(i, nowTurn);
phase = phaseTurnStoneMove;
}
private function loop(e: Event ): void
{
var c: Cell, cs: Cells, nowColor: String = "", i: int;
switch (phase)
{
case phaseInit:
/**
* 初期化
*/
boardView.lock();
boardView.fillRect(boardView.rect, 0x0);
c = board.first;
do
{
if (c.stone != STN_N)
{
stnPoint.x = c.posX;
stnPoint.y = c.posY;
stnRect.x = c.frame * CEL_SIZE;
boardView.copyPixels(stoneBmd, stnRect, stnPoint);
}
}
while (c = c.next);
boardView.unlock();
phase = phaseStart;
break;
case phaseStart:
/**
* スタート。何かもっとやることあったようなきがしたけど忘れた。
*/
nowTurn = STN_B;
pass = 0;
phase = phaseTurnInit;
log("開始");
trace(board.numStnB + " : " + board.numStnW);
break;
case phaseTurnInit:
/**
* ターン開始。
* おける場所をハイライトする。
*/
nowColor = (nowTurn == STN_B ? "黒" : "白");
log(nowColor + "の番です", false);
cs = board.canPuts(nowTurn);
trace(cs.length);
if (cs.length == 0)
{
pass++;
log(nowColor + "は置ける場所がないのでパスします。", false);
phase = phaseTurnChange;
if (pass == 2)
{
phase = phaseResult;
return;
}
return;
}
else
{
pass = 0;
c = cs.first;
do
{
CellBtn(cellBtns[c.index]).visible = true;
}
while (c = c.next);
}
cs.clear();
phase = phaseTurnWait;
break;
case phaseTurnWait:
if(nowTurn == STN_W){
//cs = board.canPuts(nowTurn);
//var idx : int = cs.first.index;
cpu.putBoard(board);
var idx :int = cpu.nextStep();
board.put(idx, nowTurn);
var cb: CellBtn = cellBtnFirst;
do { cb.visible = false; } while (cb = cb.next);
// cs.clear();
phase = phaseTurnStoneMove;
log(cpu.msr);
}
// 待ち
break;
case phaseTurnStoneMove:
/**
* 石を動かす
*/
boardView.lock();
boardView.fillRect(boardView.rect, 0x0);
c = board.first;
do
{
if (c.moveF != 0)
{
c.frame += c.moveF;
if (c.frame == 0 || c.frame == STN_F) c.moveF = 0;
else i++
}
if (c.stone != STN_N)
{
stnPoint.x = c.posX;
stnPoint.y = c.posY;
stnRect.x = c.frame * CEL_SIZE;
boardView.copyPixels(stoneBmd, stnRect, stnPoint);
}
}
while (c = c.next);
boardView.unlock();
if (i == 0) phase = phaseTurnChange;
break;
case phaseTurnChange:
/**
* ターン終了して相手のターンに変える。
*/
if (board.numStnB + board.numStnW == LENGTH)
{
phase = phaseResult;
return;
}
nowTurn = nowTurn ^ 3;
phase = phaseTurnInit;
break;
case phaseResult:
/**
* 結果表示
*/
log("終了です。", false);
log("黒 ： 白 = " + board.numStnB + " : " + board.numStnW + " で " + (board.numStnB == board.numStnW ? "引き分けです。" : board.numStnB < board.numStnW ? "白の勝ちです。" : "黒の勝ちです。"));
phase = phaseEnd;
break;
}
}
/**
* ログ表示
* @param str
* @param clear
*/
private function log(str: String, clear: Boolean = false): void
{
if (clear) infoTxt.text = str;
else infoTxt.appendText(str + "\n");
infoTxt.scrollV = infoTxt.maxScrollV;
}
}
}
const STN_N: int = 0; // 何もなし
const STN_B: int = 1; // 黒
const STN_W: int = 2; // 白
const STN_F: int = 6; // 石のフレーム最後尾(0スタート)
const CEL_SIZE: int = 50; // セルのサイズ
const SIZE: int = CEL_SIZE * 8; // 盤のサイズ
const LENGTH: int = 64; // セルの総数
class Board
{
private const DEF_BOARD: Array = [
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 2, 0, 0, 0,
0, 0, 0, 2, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0
];
public var first: Cell;
public var cells: Array;
private var _numStnB: int;
private var _numStnW: int;
public var x: int = 5;
public var y: int = 5;
function Board(arr: Array = null)
{
if (arr == null) arr = DEF_BOARD.concat();
makeBoard(arr);
}
/**
* この場所におけるかチェック(多分使わない)
* @param index
* @return
*/
public function canPut(index: int): Boolean
{
return false;
}
/**
* 置けるセルを取得
* @param stn
* @return
*/
public function canPuts(stn: int): Cells
{
var c: Cell = first, res: Cell, tmp: Cell, l: int;
var opp: int = stn ^ 3;
do
{
if (c.stone == STN_N && checkLine(c, stn, opp))
{
if (res == null) tmp = res = c.clone();
else tmp = tmp.next = c.clone();
l++;
}
}
while (c = c.next);
return new Cells(res, l);
}
/**
* index の場所に 石をおく
* @param index
* @param stn
*/
public function put(index: int, stn: int): void
{
var cell: Cell = cells[index], c: Cell, opp: int = stn ^ 3, i: int = 1, mf: int = stn == STN_B ? -1 : 1;
cell.frame = stn == STN_B ? 0 : STN_F;
cell.stone = stn;
c = cell.tl; // 左上
if (c && c.stone == opp && checkTL(c, stn)) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.tl); }
c = cell.t; // 上
if (c && c.stone == opp && checkT(c, stn) ) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.t); }
c = cell.tr; // 右上
if (c && c.stone == opp && checkTR(c, stn)) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.tr); }
c = cell.l; // 左
if (c && c.stone == opp && checkL(c, stn) ) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.l); }
c = cell.r; // 右
if (c && c.stone == opp && checkR(c, stn) ) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.r); }
c = cell.bl; // 左下
if (c && c.stone == opp && checkBL(c, stn)) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.bl); }
c = cell.b; // 下
if (c && c.stone == opp && checkB(c, stn) ) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.b); }
c = cell.br; // 右下
if (c && c.stone == opp && checkBR(c, stn)) { do {
if (c.stone == stn) break;
c.moveF = mf, i++, c.stone = stn;
} while (c = c.br); }
if (stn == STN_B)
{
_numStnB += i;
_numStnW -= i - 1;
}
else
{
_numStnW += i;
_numStnB -= i - 1;
}
}
/**
* どこかのラインが取れるかチェック
* @param cell
* @param stn
* @param opp
* @return
*/
private function checkLine(cell: Cell, stn: int, opp: int): Boolean
{
var c: Cell;
c = cell.tl; // 左上
if (c && c.stone == opp && checkTL(c, stn)) return true;
c = cell.t; // 上
if (c && c.stone == opp && checkT(c, stn) ) return true;
c = cell.tr; // 右上
if (c && c.stone == opp && checkTR(c, stn)) return true;
c = cell.l; // 左
if (c && c.stone == opp && checkL(c, stn) ) return true;
c = cell.r; // 右
if (c && c.stone == opp && checkR(c, stn) ) return true;
c = cell.bl; // 左下
if (c && c.stone == opp && checkBL(c, stn)) return true;
c = cell.b; // 下
if (c && c.stone == opp && checkB(c, stn) ) return true;
c = cell.br; // 左下
if (c && c.stone == opp && checkBR(c, stn)) return true;
return false;
}
// その方向に取れるのがあるかどうかをチェックする。TL(左上), T(上), TR(右上), L(左), R(右), BL(左下), B(下), BR(右)
private function checkTL(c: Cell, stn: int): Boolean
{
do {
if (c.stone == stn) return true;
else if (c.stone == STN_N) return false;
} while (c = c.tl);
return false; }
private function checkT( c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.t ); return false; }
private function checkTR(c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.tr); return false; }
private function checkL( c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.l ); return false; }
private function checkR( c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.r ); return false; }
private function checkBL(c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.bl); return false; }
private function checkB( c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.b ); return false; }
private function checkBR(c: Cell, stn: int): Boolean { do { if (c.stone == stn) return true; else if (c.stone == STN_N) return false; } while (c = c.br); return false; }
/**
* ボードの初期化
* @param arr
*/
private function makeBoard(arr: Array):void
{
var i: int, n: int = arr.length, c: Cell, tmp: Array = [], s: int;
tmp.push(first = c = new Cell(i, arr[i]));
for (i = 1; i < n; i++)
{
tmp.push(c.next = c = new Cell(i, s = arr[i]));
if (s == STN_B) _numStnB ++;
else if (s == STN_W) _numStnW ++;
}
i = 0, c = first;
do
{
if (i % 8)
{
if (i >> 3) c.tl = tmp[i - 9];
if (63 - i >> 3) c.bl = tmp[i + 7];
c.l = tmp[i - 1];
}
if (i % 8 != 7)
{
if (i >> 3) c.tr = tmp[i - 7];
if (63 - i >> 3) c.br = tmp[i + 9];
c.r = tmp[i + 1];
}
if (i >> 3) c.t = tmp[i - 8];
if (63 - i >> 3) c.b = tmp[i + 8];
i++;
}
while (c = c.next);
cells = tmp;
}
/**
* 何かに使うかもってことでとりあえず作った str から Array に変える
* @param str
* @return
*/
public function dataToArray(str: String): Array
{
return str.split(":");
}
/**
* 現在のマップをStringに変える。
* @return
*/
public function toData(): String
{
var c: Cell, res: String = "";
c = first;
do
{
res += c.stone + ":";
}
while (c = c.next);
return res.slice(0, res.length - 1);
}
/**
* 黒の数
*/
public function get numStnB(): int { return _numStnB; }
/**
* 白の数
*/
public function get numStnW(): int { return _numStnW; }
public function clone() : Board{
var newbd:Board = new Board(dataToArray(toData()));
return newbd;
}
public function clear():void{
first = null;
cells.splice(0);
}
}
/**
* 1マス
*/
class Cell
{
public var next: Cell;
public var tl: Cell, t: Cell, tr: Cell, l: Cell, r: Cell, bl: Cell, b: Cell, br: Cell;
public var index: int;
public var stone: int;
public var data1: Cell;
public var data2: int;
public var frame: int;
public var moveF: int;
public var posX: int, posY: int;
function Cell(i: int, s: int)
{
index = i;
stone = s;
frame = s == STN_W ? STN_F : 0;
posX = (index % 8) * CEL_SIZE;
posY = (index >> 3) * CEL_SIZE;
}
public function clone(): Cell
{
var c: Cell = new Cell(index, stone);
c.tl = tl, c.t = t, c.tr = tr, c.l = l, c.r = r, c.bl = bl, c.b = b, c.br = br;
return c;
}
/**
* Cloneしたときはこれで消さないと GC対象にならないので注意。
*/
public function clear(): void
{
tl = t = tr = l = r = bl = b = br = next = data1 = null;
}
}
/**
* マスの塊。
*/
class Cells
{
public var first: Cell;
public var length: int;
function Cells(f: Cell, l: int)
{
first = f;
length = l;
}
public function clear(): void
{
var c: Cell = first, next: Cell;
if (c == null) return;
do
{
next = c.next;
c.clear();
}
while ((c = next));
first = null;
}
public function getCell( i :int): Cell{
var ret : Cell = first;
while(i > 0){
ret = ret.next;
i--;
}
return ret;
}
}
import flash.display.Sprite;
import flash.events.MouseEvent;
/**
* ボタン。ユーザーが取れる位置のボタン。
*/
class CellBtn extends Sprite
{
public var next: CellBtn;
private var _index: int;
function CellBtn(ix: int, iy: int, i: int, handler: Function)
{
x = ix, y = iy, _index = i;
graphics.beginFill(0xFFFFFF, 0.5);
graphics.drawRect(0, 0, CEL_SIZE, CEL_SIZE);
buttonMode = true, visible = false;
addEventListener(MouseEvent.CLICK, handler);
}
public function get index(): int { return _index; }
}
/**
* プレイヤー
*/
class Player
{
protected var _stone: int;
function Player(s: int) { _stone = s; }
public function get stone(): int { return _stone; }
}
/**
* CPUの思考ルーチンとなる親クラス
* 形式的に抽象クラスとして使う
*/
class abstractCPU
{
protected var stone :int;
protected var board:Board
public function abstractCPU(_stone:int) : void{ stone = _stone}
public function putBoard(_board : Board){ board = _board}
public function nextStep() : int{
throw new Error("抽象クラスのため直接インスタンス化は不可");
}
protected function eval(board : Board) : int{ return 0;}
public var msr: String;
}
class weakCPU extends abstractCPU
{
//静的評価関数に使用する重み付け
private const EVAL_MAP: Array = [
150, -40, 20, 5, 5, 20, -40, 150,
-40, -80, -1, -1, -1, -1, -80, -40,
20, -1, 5, 1, 1, 5, -1, 20,
5, -1, 1, 0, 0, 1, -1, 5,
5, -1, 1, 0, 0, 1, -1, 5,
20, -1, 5, 1, 1, 5, -1, 20,
-40, -80, -1, -1, -1, -1, -80, -40,
150, -40, 20, 5, 5, 20, -40, 150,
];
public function weakCPU(_stone : int){
super(_stone);
}
public override function nextStep() : int {
var canputs :Cells = board.canPuts(stone);
var eval_values : Array = new Array();
if(canputs.length == 0){
throw new Error("置ける場所無し");
}
var cell : Cell = canputs.first;
do{
var tmpboard : Board = board.clone();
tmpboard.put(cell.index, stone);
var val : int = eval(tmpboard);
eval_values.push(val);
tmpboard.clear();
}while(cell = cell.next);
//msr = board.toData();
msr = eval(board).toString();
return canputs.getCell(Util.max(eval_values)).index;
}
//静的評価関数
protected override function eval(board : Board) : int{
var ret:int = 0;
for(var i:int = 0;i < EVAL_MAP.length;i++){
if(board.cells[i].stone == stone){
ret += EVAL_MAP[i];
}
else if(board.cells[i] == (stone ^ 3)){
ret -= EVAL_MAP[i];
}
}
return ret;
}
}
/**
* MinMax法で考えるCPU
* */
class MinMaxCPU extends abstractCPU
{
//静的評価関数に使用する重み付け
private const EVAL_MAP: Array = [
150, -40, 20, 5, 5, 20, -40, 150,
-40, -80, -1, -1, -1, -1, -80, -40,
20, -1, 5, 1, 1, 5, -1, 20,
5, -1, 1, 0, 0, 1, -1, 5,
5, -1, 1, 0, 0, 1, -1, 5,
20, -1, 5, 1, 1, 5, -1, 20,
-40, -80, -1, -1, -1, -1, -80, -40,
150, -40, 20, 5, 5, 20, -40, 150,
];
private const MIN : int = 0;
private const MAX : int = 1;
private var depth : int;
public function MinMaxCPU(_stone : int, _depth : int){
super(_stone);
depth = _depth;
}
public override function nextStep() : int {
var eCell : Eval_Cell = calcNextStep(depth, MAX, board);
return eCell.index;
}
private function calcNextStep(dep : int, algo : int, bd : Board) : Eval_Cell {
var tmpStone : int = stone;
if(algo == MIN){
tmpStone ^= 3;
}
var canputs :Cells = bd.canPuts(tmpStone);
var eval_values : Array = new Array();
if(canputs.length == 0){
//throw new Error("置ける場所無し");
return new Eval_Cell(int.MIN_VALUE, -1);
}
var cell : Cell = canputs.first;
do{
var tmpboard : Board = bd.clone();
tmpboard.put(cell.index, tmpStone);
var val : int;
if(dep == 0){
val = eval(tmpboard);
}else{
val = calcNextStep(dep - 1, algo ^ 1, tmpboard).score;
}
eval_values.push(val);
tmpboard.clear();
}while(cell = cell.next);
//msr = board.toData();
//msr = eval(bd).toString();
var idx : int = Util.min(eval_values);
if(algo == MAX){
idx = Util.max(eval_values);
}
return new Eval_Cell(eval_values[idx], canputs.getCell(idx).index);
}
//静的評価関数
protected override function eval(board : Board) : int{
var ret:int = 0;
for(var i:int = 0;i < EVAL_MAP.length;i++){
if(board.cells[i].stone == stone){
ret += EVAL_MAP[i];
}
else if(board.cells[i] == (stone ^ 3)){
ret -= EVAL_MAP[i];
}
}
return ret;
}
}
/**
* セル評価用のクラス
* スコアとインデックスのセット
**/
class Eval_Cell{
public var score : int;
public var index : int;
public function Eval_Cell(_score : int, _index : int){
score = _score, index = _index;
}
}
class Util
{
//配列中の最大となる数の添え字を返す
public static function max(a:Array) : int{
if(a == null || a.length == 0 ){throw new Error("error");}
var val :int = a[0], ret :int = 0;
for(var i:int=1;i < a.length;i++){
if(val < a[i]){
val = a[i];
ret = i;
}
}
return ret;
}
//配列中の最小となる数の添え字を返す
public static function min(a:Array) : int{
if(a == null || a.length == 0 ){throw new Error("error");}
var val :int = a[0], ret :int = 0;
for(var i:int=1;i < a.length;i++){
if(val > a[i]){
val = a[i];
ret = i;
}
}
return ret;
}
}