オセロAIゲーム木を用いたオセロAIの開発
概要
オセロの強いAIをゲーム木を用いて開発するのがこの研究の目標。ただし一般PCで扱える実行速度であることが条件である。
なお、開発したオセロAIはこちらから相手としてプレイすることができます。ぜひたたかってみてください。
ゲーム木及びその探索法の実装についてはこちらの記事を参考のこと。
強さの指標
様々な戦略をもつプレイヤーやAIが相手になる。特定のAIだけに強いのは望ましくない。
あらゆる戦略を確率的に取りうるランダムに手を打つ(隅は優先的に取る)AIに対する勝率を強さの指標とする。
評価関数の工夫
石のひっくり返されない度(信頼度)を３つに分け評価する
不確定石 次の手でひっくり返され得る石
暫定石 次の手ではひっくり返され得ない石
確定石 今後ひっくり返されることがない石
石の配置による評価テーブルを3つの信頼度に分け用意する。重み付けは遺伝的アルゴリズムで学習させる。(PCをフル稼働させて数日掛かりました・・・)
評価
・強さ
・実行速度(ノードの評価数)
実装
盤面クラス
namespace ReversiEngine {
/// <summary>盤面</summary>
public class Board : ICloneable{
private int stone_count;
private readonly Stone[,] board;
/// <summary>コンストラクタ</summary>
public Board() {
this.stone_count = 0;
this.board = new Stone[Size, Size];
}
/// <summary>コンストラクタ</summary>
/// <param name="board">石配列</param>
public Board(Stone[,] board) {
if(board == null) {
throw new ArgumentNullException();
}
if(Size != board.GetLength(0) || Size != board.GetLength(1)) {
throw new ArgumentException();
}
this.board = (Stone[,])board.Clone();
for(int x, y = 0; y < Size; y++) {
for(x = 0; x < Size; x++) {
if(this.board[x, y] != Stone.None) {
stone_count++;
}
}
}
}
/// <summary>コンストラクタ</summary>
public Board(Board board) {
if(board == null) {
throw new ArgumentNullException();
}
this.board = (Stone[,])board.board.Clone();
this.stone_count = board.stone_count;
}
/// <summary>盤面のサイズ</summary>
public const int Size = 8;
/// <summary>盤面インデクサ</summary>
public Stone this [int x, int y]{
get {
return board[x, y];
}
set {
if(board[x, y] == Stone.None && value != Stone.None) {
stone_count++;
}
else if(board[x, y] != Stone.None && value == Stone.None) {
stone_count--;
}
board[x, y] = value;
}
}
/// <summary>石を配置可能か判定</summary>
public bool IsLocatable(int x, int y, Stone color) {
if(color == Stone.None) {
throw new ArgumentException();
}
if(board[x, y] != Stone.None) {
return false;
}
Func<int, int, bool> is_locatable_dxy = (dx, dy) => {
int px = x + dx, py = y + dy;
if(px < 0 || px >= Size || py < 0 || py >= Size) {
return false;
}
if(board[px, py] == color || board[px, py] == Stone.None) {
return false;
}
for(;;) {
px += dx;
py += dy;
if(px < 0 || px >= Size || py < 0 || py >= Size) {
return false;
}
if(board[px, py] == Stone.None) {
return false;
}
if(board[px, py] == color) {
return true;
}
}
};
if(is_locatable_dxy(-1, -1)) {
return true;
}
if(is_locatable_dxy(-1, 0)) {
return true;
}
if(is_locatable_dxy(-1, +1)) {
return true;
}
if(is_locatable_dxy( 0, -1)) {
return true;
}
if(is_locatable_dxy( 0, +1)) {
return true;
}
if(is_locatable_dxy(+1, -1)) {
return true;
}
if(is_locatable_dxy(+1, 0)) {
return true;
}
if(is_locatable_dxy(+1, +1)) {
return true;
}
return false;
}
/// <summary>石を配置可能か判定</summary>
public bool IsLocatable(Stone color) {
for(int x, y = 0; y < Size; y++) {
for(x = 0; x < Size; x++) {
if(IsLocatable(x, y, color)) {
return true;
}
}
}
return false;
}
/// <summary>石を隅に配置可能か判定</summary>
public bool IsCornerLocatable(Stone color) {
return IsLocatable(0, 0, color) || IsLocatable(Size - 1, 0, color) || IsLocatable(0, Size - 1, color) || IsLocatable(Size - 1, Size - 1, color);
}
/// <summary>石を配置</summary>
public void Locate(int x, int y, Stone color) {
bool flip_stone = false;
Action<int, int> locate_dxy = (dx, dy) => {
int px = x, py = y;
for(;;) {
px += dx;
py += dy;
if(px < 0 || px >= Size || py < 0 || py >= Size) {
return;
}
if(board[px, py] == Stone.None) {
return;
}
if(board[px, py] == color) {
break;
}
}
px -= dx;
py -= dy;
while(x != px || y != py) {
board[px, py] = color;
flip_stone = true;
px -= dx;
py -= dy;
}
};
locate_dxy(-1, -1);
locate_dxy(-1, 0);
locate_dxy(-1, +1);
locate_dxy( 0, -1);
locate_dxy( 0, +1);
locate_dxy(+1, -1);
locate_dxy(+1, 0);
locate_dxy(+1, +1);
if(flip_stone) {
board[x, y] = color;
stone_count++;
}
}
/// <summary>石の信頼性を判定</summary>
public StoneReliability JudgeReliability(int x, int y) {
Stone color = board[x, y];
StoneReliability reliability = StoneReliability.Definite;
if(color == Stone.None) {
return StoneReliability.None;
}
Func<int, int, bool> isexist_opposite_dxy = (dx, dy) => {
int px = x, py = y;
for(;;) {
px += dx;
py += dy;
if(px < 0 || px >= Size || py < 0 || py >= Size) {
return false;
}
if(board[px, py] == Stone.None) {
return false;
}
if(board[px, py] != color) {
return true;
}
}
};
Func<int, int, bool> is_edge_dxy = (dx, dy) => {
int px = x, py = y;
for(;;) {
px += dx;
py += dy;
if(px < 0 || px >= Size || py < 0 || py >= Size) {
return true;
}
if(board[px, py] == Stone.None) {
return false;
}
}
};
Action<int, int> renovate_reliability = (dx, dy) => {
bool wall_a, wall_b, stone_a, stone_b;
wall_a = is_edge_dxy(dx, dy);
wall_b = is_edge_dxy(-dx, -dy);
if(wall_a && wall_b) {
return;
}
stone_a = isexist_opposite_dxy(dx, dy);
stone_b = isexist_opposite_dxy(-dx, -dy);
if(wall_a && !wall_b && !stone_a) {
return;
}
if(!wall_a && wall_b && !stone_b) {
return;
}
if(stone_a && !stone_b && !wall_b) {
reliability = StoneReliability.Uncertain;
return;
}
if(!stone_a && stone_b && !wall_a) {
reliability = StoneReliability.Uncertain;
return;
}
reliability = StoneReliability.Interim;
};
renovate_reliability(1, 0);
if(reliability == StoneReliability.Uncertain) {
return reliability;
}
renovate_reliability(0, 1);
if(reliability == StoneReliability.Uncertain) {
return reliability;
}
renovate_reliability(1, 1);
if(reliability == StoneReliability.Uncertain) {
return reliability;
}
renovate_reliability(1, -1);
if(reliability == StoneReliability.Uncertain) {
return reliability;
}
return reliability;
}
/// <summary>石の個数</summary>
public int StoneCount {
get{
return stone_count;
}
}
/// <summary>石の個数をカウント</summary>
public int CountStone(Stone stone) {
int cnt = 0;
for(int x, y = 0; y < Size; y++) {
for(x = 0; x < Size; x++) {
if(board[x, y] == stone) {
cnt++;
}
}
}
return cnt;
}
/// <summary>初期配置</summary>
public static Board Init() {
Board ret = new Board();
ret[3, 3] = Stone.White;
ret[3, 4] = Stone.Black;
ret[4, 3] = Stone.Black;
ret[4, 4] = Stone.White;
return ret;
}
/// <summary>盤面が埋まっているか否か</summary>
public bool IsFill {
get {
for(int x, y = 0; y < Size; y++) {
for(x = 0; x < Size; x++) {
if(board[x, y] == Stone.None) {
return false;
}
}
}
return true;
}
}
/// <summary>ゲームセットか否か</summary>
public bool IsEndGame {
get {
if(IsFill || !IsExistStone(Stone.White) || !IsExistStone(Stone.Black)) {
return true;
}
if(!IsLocatable(Stone.White) && !IsLocatable(Stone.Black)) {
return true;
}
return false;
}
}
/// <summary>石が存在するか否か</summary>
public bool IsExistStone(Stone stone) {
for(int x, y = 0; y < Size; y++) {
for(x = 0; x < Size; x++) {
if(board[x, y] == stone) {
return true;
}
}
}
return false;
}
/// <summary>可視化</summary>
public override string ToString() {
string str = "";
for(int x, y = 0; y < Size; y++) {
for(x = 0; x < Size; x++) {
if(board[x, y] == Reversi.Stone.White) {
str += "□";
}
else if(board[x, y] == Reversi.Stone.Black) {
str += "■";
}
else {
str += " ";
}
}
str += "\n";
}
return str;
}
/// <summary>クローン</summary>
public object Clone() {
return new Board(this);
}
}
}
石列挙型
namespace ReversiEngine {
///<summary>石 列挙型</summary>
public enum Stone : int{
/// <summary>石が配置されていない</summary>
None = 0 ,
/// <summary>白</summary>
White = +1,
/// <summary>黒</summary>
Black = -1
};
///<summary>石 信頼性</summary>
public enum StoneReliability : int{
///<summary>未配置</summary>
None = 0,
///<summary>不確実 - 次の手で返される可能性アリ</summary>
Uncertain,
///<summary>暫定 - 次の手で返される可能性ナシ</summary>
Interim,
///<summary>確定 - 今後返される可能性ナシ</summary>
Definite
};
}
棋譜クラス
namespace ReversiEngine {
/// <summary>棋譜</summary>
public class Decision {
/// <summary>X座標</summary>
public int X {
get; private set;
} = 0;
/// <summary>Y座標</summary>
public int Y {
get; private set;
} = 0;
/// <summary>パスか否か</summary>
public bool IsPass {
get; private set;
} = false;
/// <summary>配置</summary>
public static Decision Place(int x, int y) {
return new Decision { X = x, Y = y };
}
/// <summary>パス</summary>
public static Decision Pass {
get {
return new Decision { IsPass = true };
}
}
/// <summary>文字列化</summary>
public override string ToString() {
return $"{X},{Y},{IsPass}";
}
}
}
プレイ状態クラス
namespace ReversiEngine {
///<summary>プレイ状態クラス</summary>
public class State : IState<Decision>, ICloneable {
/// <summary>コンストラクタ</summary>
public State(Board board, Evaluator evaluator, Stone PlayerColor, Stone NextColor, bool is_finale_mode = false) {
if(board == null || evaluator == null) {
throw new ArgumentNullException();
}
if(PlayerColor == Stone.None || NextColor == Stone.None) {
throw new ArgumentException();
}
this.Board = (Board)board.Clone();
this.Evaluator = evaluator;
this.PlayerColor = PlayerColor;
this.NextColor = NextColor;
this.IsFinaleMode = is_finale_mode;
}
/// <summary>盤面状態</summary>
public Board Board {
get; private set;
}
/// <summary>評価法</summary>
public Evaluator Evaluator {
get; private set;
}
/// <summary>プレイヤーの石の色</summary>
public Stone PlayerColor {
get; private set;
}
/// <summary>次に打つ石の色</summary>
public Stone NextColor {
get; private set;
}
/// <summary>終局読みモードを有効にするか</summary>
public bool IsFinaleMode {
get; private set;
}
/// <summary>盤面の評価</summary>
public double Evaluation {
get {
return Evaluator.Evaluate(Board, PlayerColor, IsFinaleMode);
}
}
/// <summary>ゲームセットか否か</summary>
public bool IsEndGame => Board.IsEndGame;
/// <summary>次の手をコレクションとして返す</summary>
public IEnumerable<Decision> NextDecisions() {
bool exist_locatable = false;
for(int i, j = 0; j < Board.Size / 2; j++) {
if(Board.IsLocatable(j, j, NextColor)) {
exist_locatable = true;
yield return Decision.Place(j, j);
}
if(Board.IsLocatable(Board.Size - j - 1, j, NextColor)) {
exist_locatable = true;
yield return Decision.Place(Board.Size - j - 1, j);
}
if(Board.IsLocatable(j, Board.Size - j - 1, NextColor)) {
exist_locatable = true;
yield return Decision.Place(j, Board.Size - j - 1);
}
if(Board.IsLocatable(Board.Size - j - 1, Board.Size - j - 1, NextColor)) {
exist_locatable = true;
yield return Decision.Place(Board.Size - j - 1, Board.Size - j - 1);
}
for(i = j + 1; i < Board.Size / 2; i++) {
if(Board.IsLocatable(i, j, NextColor)) {
exist_locatable = true;
yield return Decision.Place(i, j);
}
if(Board.IsLocatable(Board.Size - i - 1, j, NextColor)) {
exist_locatable = true;
yield return Decision.Place(Board.Size - i - 1, j);
}
if(Board.IsLocatable(i, Board.Size - j - 1, NextColor)) {
exist_locatable = true;
yield return Decision.Place(i, Board.Size - j - 1);
}
if(Board.IsLocatable(Board.Size - i - 1, Board.Size - j - 1, NextColor)) {
exist_locatable = true;
yield return Decision.Place(Board.Size - i - 1, Board.Size - j - 1);
}
if(Board.IsLocatable(j, i, NextColor)) {
exist_locatable = true;
yield return Decision.Place(j, i);
}
if(Board.IsLocatable(j, Board.Size - i - 1, NextColor)) {
exist_locatable = true;
yield return Decision.Place(j, Board.Size - i - 1);
}
if(Board.IsLocatable(Board.Size - j - 1, i, NextColor)) {
exist_locatable = true;
yield return Decision.Place(Board.Size - j - 1, i);
}
if(Board.IsLocatable(Board.Size - j - 1, Board.Size - i - 1, NextColor)) {
exist_locatable = true;
yield return Decision.Place(Board.Size - j - 1, Board.Size - i - 1);
}
}
}
if(!exist_locatable) {
yield return Decision.Pass;
}
}
/// <summary>次の盤面状態を生成する</summary>
public IState<Decision> NextState(Decision decision) {
State ret = (State)Clone();
if(!decision.IsPass) {
ret.Board.Locate(decision.X, decision.Y, NextColor);
}
if(NextColor == Stone.Black) {
ret.NextColor = Stone.White;
}
else if(NextColor == Stone.White) {
ret.NextColor = Stone.Black;
}
return ret;
}
/// <summary>次に隅が配置可能ならばその打つ手を返す</summary>
/// <remarks>隅に配置不能ならばnullを返す</remarks>
public Decision NextCornerDecision() {
double ev, max_ev = double.NegativeInfinity;
Decision decision, max_ev_decision = null;
if(Board.IsLocatable(0, 0, NextColor)) {
decision = Decision.Place(0, 0);
ev = NextState(decision).Evaluation;
if(max_ev < ev) {
max_ev = ev;
max_ev_decision = decision;
}
}
if(Board.IsLocatable(0, Board.Size - 1, NextColor)) {
decision = Decision.Place(0, Board.Size - 1);
ev = NextState(decision).Evaluation;
if(max_ev < ev) {
max_ev = ev;
max_ev_decision = decision;
}
}
if(Board.IsLocatable(Board.Size - 1, 0, NextColor)) {
decision = Decision.Place(Board.Size - 1, 0);
ev = NextState(decision).Evaluation;
if(max_ev < ev) {
max_ev = ev;
max_ev_decision = decision;
}
}
if(Board.IsLocatable(Board.Size - 1, Board.Size - 1, NextColor)) {
decision = Decision.Place(Board.Size - 1, Board.Size - 1);
ev = NextState(decision).Evaluation;
if(max_ev < ev) {
max_ev = ev;
max_ev_decision = decision;
}
}
return max_ev_decision;
}
/// <summary>石の個数をカウント</summary>
public int CountStone(Stone stone) {
return Board.CountStone(stone);
}
/// <summary>クローン</summary>
public object Clone() {
return new State(Board, Evaluator, PlayerColor, NextColor, IsFinaleMode);
}
}
}
評価法クラス
namespace ReversiEngine {
/// <summary>評価法クラス</summary>
public class Evaluator {
static readonly int[,] ev_table_uncertain = new int[Board.Size, Board.Size]
{ { 0, -798, -10, -546, -546, -10, -798, 0 },
{ -798, -501, -40, -150, -150, -40, -501, -798 },
{ -10, -40, 26, 49, 49, 26, -40, -10 },
{ -546, -150, 49, -50, -50, 49, -150, -546 },
{ -546, -150, 49, -50, -50, 49, -150, -546 },
{ -10, -40, 26, 49, 49, 26, -40, -10 },
{ -798, -501, -40, -150, -150, -40, -501, -798 },
{ 0, -798, -10, -546, -546, -10, -798, 0 }};
static readonly int[,] ev_table_interim = new int[Board.Size, Board.Size]
{ { 0, -532, -224, -111, -111, -224, -532, 0 },
{ -532, -494, -32, -156, -156, -32, -494, -532 },
{ -224, -32, 27, 49, 49, 27, -32, -224 },
{ -111, -156, 49, 22, 22, 49, -156, -111 },
{ -111, -156, 49, 22, 22, 49, -156, -111 },
{ -224, -32, 27, 49, 49, 27, -32, -224 },
{ -532, -494, -32, -156, -156, -32, -494, -532 },
{ 0, -532, -224, -111, -111, -224, -532, 0 }};
static readonly int[,] ev_table_definite = new int[Board.Size, Board.Size]
{ { 2500, 767, 607, 642, 642, 607, 767, 2500 },
{ 767, 344, 284, 103, 103, 284, 344, 767 },
{ 607, 284, 114, 182, 182, 114, 284, 607 },
{ 642, 103, 182, 202, 202, 182, 103, 642 },
{ 642, 103, 182, 202, 202, 182, 103, 642 },
{ 607, 284, 114, 182, 182, 114, 284, 607 },
{ 767, 344, 284, 103, 103, 284, 344, 767 },
{ 2500, 767, 607, 642, 642, 607, 767, 2500 }};
/// <summary>コンストラクタ</summary>
public Evaluator() { }
/// <summary>評価</summary>
/// <param name="board">盤面</param>
/// <param name="evaluate_color">評価する石</param>
/// <param name="finale_mode">終局読みモードを有効にするか</param>
/// <returns>評価値</returns>
public double Evaluate(Board board, Stone evaluate_color, bool finale_mode = false) {
if(evaluate_color == Stone.None) {
throw new ArgumentException();
}
if(finale_mode) {
return board.CountStone(evaluate_color);
}
if(!board.IsExistStone(evaluate_color)) {
return double.MinValue;
}
if(!board.IsExistStone((evaluate_color != Stone.Black) ? Stone.Black : Stone.White)) {
return double.MaxValue;
}
int ev = 0, evaluate_stone_cnt = 0, opponent_stone_cnt = 0;
bool isexist_uncertain_evaluate_stone = false, isexist_uncertain_opponent_stone = false;
for(int x, y = 0; y < Board.Size; y++) {
for(x = 0; x < Board.Size; x++) {
if(board[x, y] == Stone.None) {
continue;
}
if(board[x, y] == evaluate_color) {
evaluate_stone_cnt++;
var stone_reliability = board.JudgeReliability(x, y);
switch(stone_reliability) {
case StoneReliability.Uncertain:
isexist_uncertain_evaluate_stone = true;
ev += ev_table_uncertain[x, y];
break;
case StoneReliability.Interim:
ev += ev_table_interim[x, y];
break;
case StoneReliability.Definite:
ev += ev_table_definite[x, y];
break;
}
}
else{
opponent_stone_cnt++;
var stone_reliability = board.JudgeReliability(x, y);
switch(stone_reliability) {
case StoneReliability.Uncertain:
isexist_uncertain_opponent_stone = true;
ev -= ev_table_uncertain[x, y];
break;
case StoneReliability.Interim:
ev -= ev_table_interim[x, y];
break;
case StoneReliability.Definite:
ev -= ev_table_definite[x, y];
break;
}
}
}
}
if(evaluate_stone_cnt > opponent_stone_cnt && !isexist_uncertain_evaluate_stone) {
return ev + 1.0e+6;
}
if(evaluate_stone_cnt < opponent_stone_cnt && !isexist_uncertain_opponent_stone) {
return ev - 1.0e+6;
}
return ev;
}
}
}
プレイヤークラス
namespace ReversiEngine {
///<summary>プレイヤー</summary>
public interface Player {
/// <summary>次の手を打つ</summary>
/// <returns>決定オブジェクトを返す</returns>
Decision Play(Board current_board);
/// <summary>プレイヤーの色</summary>
Stone Color { get; }
}
///<summary>プレイヤー (ゲーム木のノード評価数 5000)</summary>
public class WakabaTechE5000Player : Player {
Stone player_color;
Evaluator evaluator;
/// <summary>コンストラクタ</summary>
public WakabaTechE5000Player(Stone player_color) {
this.player_color = player_color;
evaluator = new Evaluator();
}
/// <summary>次の手を打つ</summary>
/// <returns>決定オブジェクトを返す</returns>
public Decision Play(Board current_board) {
if(current_board.CountStone(Stone.None) > 10) {
State root_state = new State(current_board, evaluator, player_color, player_color);
return DiscontinuableIDDFSMethod<State, Decision>.Search(root_state, 5, 12, 5000, Decision.Pass);
}
else {
State root_state = new State(current_board, evaluator, player_color, player_color, is_finale_mode: true);
return CompleteSearchMethod<State, Decision>.Search(root_state, Decision.Pass);
}
}
/// <summary>プレイヤーの色</summary>
public Stone Color {
get {
return player_color;
}
}
}
}
