Scalaでリバーシ（オセロ）
正月はScalaをやってました。
リバーシを題材に、「コップ本」片手に悪戦苦闘をしてました。
添削歓迎！
/** * リバーシ ver4.0 */ /** 位置 */ case class Pos(argx:Int, argy:Int) { val x = argx val y = argy def add(dir:Dir):Pos = Pos(x+dir.dx, y+dir.dy) } /** 方向 */ case class Dir(argdx:Int, argdy:Int) { val dx = argdx val dy = argdy } /** 共通定義 */ trait ReversiCommon { /** 盤面サイズ */ val BoardSize = 8 val Empty = ' ' // 空 val Black = '●' // 黒 val White = '○' // 白 val Wall = '壁' // 壁 /** * 方向(dx dy)のリスト * (右 右上 上 左上 左 左下 下 右下) * を意味する． */ val directions = List( Dir(0,1), Dir(-1,1), Dir(-1,0), Dir(-1,-1), Dir(0,-1), Dir(1,-1), Dir(1,0), Dir(1,1)); } /** 盤面。まわりを壁で囲っている。 */ class Board extends ReversiCommon { var board = new Array[Array[Char]](BoardSize+2) for(u <- 0 to BoardSize+1) { board(u) = new Array[Char](BoardSize+2) for(v <- 0 to BoardSize+1) { board(u)(v) = (u,v) match { case (0,_) => Wall case (9,_) => Wall case (_,0) => Wall case (_,9) => Wall case (4,4) => White case (5,5) => White case (5,4) => Black case (4,5) => Black case _ => Empty } } } def get(x:Int, y:Int):Char = board(x)(y) def get(pos:Pos):Char = get(pos.x, pos.y) def put(x:Int, y:Int, c:Char):Unit = board(x)(y) = c def put(pos:Pos, c:Char):Unit = put(pos.x, pos.y, c) // 白や黒の駒の数を返す。Emptyを指定すると空きの数を返す。 def count(color:Char):Int = { var result = 0 for (line <- board) { // 各行をリストに変え、要素がcolorの数を取得する。 result += line.toList.count(_==color) } result } override def toString = { // 個々の行は "" ではさんで、行間は改行ではさむ。 board.map(line=>line.mkString("")).mkString("\n") } /** 盤面を複製する */ override def clone():Board = { var result = new Board() for (y <- 1 to BoardSize) { for (x <- 1 to BoardSize) { result.put(x, y, this.get(x,y)) } } result } /** 候補を数字で書く。現在の盤面は変更せず、新しい盤面を作って返す。 */ def createCandidate(hands:List[Pos]):Board = { var result = clone val chars = "????????????????????".toCharArray() // 「○に１」から「○に２０」まで // val chars = "ＡＢＣＤＥＦＧＨＩＪＫＬＭＮＯＰＱＲＳＴＵＶＷＸＹＺ".toCharArray() var index = 0 for (hand <- hands) { result.put(hand, chars(index)) index += 1 } result } } /** ゲームのルールをつかさどるクラス */ class ReversiGame extends ReversiCommon { /** 相手の色を返す。 */ def getOpponent(c:Char) = if (c == Black) White else Black /** * 1方向に関して駒の挟むことのできる範囲を返す． * @param board 盤面 * @param bw 手番 * @param pos 駒を置く場所 * @param dir 調べる方向 */ private def getFlippablePos(board:Board, bw:Char, pos:Pos, dir:Dir): Option[Pos] = { assert(board != null) assert(bw==Black || bw==White, bw) // 駒は白か黒のどちらか assert(board.get(pos)==Empty, board) // そこは駒が置けない。 val opp = getOpponent(bw) var p = pos add dir while (board.get(p) == opp) { val next = p add dir if (board.get(next) == bw) return Some(p) p = next } None // この方向には挟めない。 } /** * 駒を挟める方向を列挙する * @param board 盤面 * @param bw 手番 * @param pos 駒を置く場所 * @return 方向とひっくり返す終端のリスト */ def getFlippableList(board:Board, bw:Char, pos:Pos): List[(Dir,Pos)] = { var result = List[(Dir,Pos)]() for (dir <- directions) { val p = getFlippablePos(board, bw, pos, dir) p match { case Some(pos) => result ::= (dir,pos) case None => } } result } /** 候補手のリストを生成する．*/ def getMovableHands(board:Board, bw:Char): List[Pos] = { var result = List[Pos]() for(y <- 1 to BoardSize) { for(x <- 1 to BoardSize) { if (board.get(x,y)==Empty) { val pos = Pos(x,y) // ひっくり返せるなら候補に追加する。 if (getFlippableList(board, bw, pos).size > 0) { result ::= pos } } } } result } /** * 駒を置いて反転処理を行う。 * 新しい盤面を作成して返す。元の盤面は変更されない。 * @param board 盤面 * @param bw 手番 * @param pos 駒を置く場所。必ず置ける場所を指定すること。 * @return 次の盤面 */ def flipPieces(board:Board, bw:Char, pos:Pos): Board = { assert(board != null) assert(bw==Black || bw==White, bw) // ひっくり返せる位置と方向をリストで取得する。 val dirposlist = getFlippableList(board, bw, pos) assert(dirposlist.size > 0, "board=\n"+board.toString+"\nbw="+bw+" pos="+pos) // 戻り値の盤面を作成 var result = board.clone() // まずは、その位置に駒を置く。 result.put(pos, bw) // ひっくり返す for ((dir,end) <- dirposlist) { var p=pos do { p = p add dir result.put(p, bw) }while (p != end) } result // 作成した盤面を返す。 } /** * 指定された２つのプレーヤーで対戦を行う。 * @return 勝者を返す。引き分けの場合は、Noneを返す。 */ def play(blackPlayer:Player, whitePlayer:Player): Option[Player] = { def getOpponentPlayer(player:Player) = if (player==blackPlayer) whitePlayer else blackPlayer var board = new Board() var player = blackPlayer // 黒が先攻 var bw = Black var lastHand:Option[Pos] = None // 直前の手 var endflag = false while (! endflag) { // プレーヤーが次の手を決める。 println(board) printPrompt(bw, player) val sel = player.getHand(board, bw) sel match { case Some(hand) => { println(hand) if (getFlippableList(board, bw, hand).size==0) { println("その場所は置けません。反則負けです。\n"+ board+bw+hand) return Some(getOpponentPlayer(player)) } // 次の手があれば駒を置いてひっくり返す。 board = flipPieces(board, bw, hand) } case None => { println("PASS") // もし、直前の手もPASSならば終了。 // これは、両者がいけない場合と、すべて埋まった場合を兼ねる。 endflag = (lastHand==None) } } lastHand = sel player = getOpponentPlayer(player) // 攻守交替 bw = getOpponent(bw) } // 両者の駒の数を数える。 val b_count = board.count(Black) val w_count = board.count(White) val winner:Option[Player] = if (b_count > w_count) Some(blackPlayer) else if (b_count < w_count) Some(whitePlayer) else None println(Black+"Black:"+blackPlayer+"="+b_count+" "+White+"White:"+whitePlayer+"="+w_count) winner match { case Some(player) => println("winner="+player) case None => println("draw") } winner } def printPrompt(bw:Char, player:Player):Unit = { print(""+bw+player+">>") } } /** 抽象プレイヤー */ trait Player extends ReversiGame { /** 手を返す。PASSのときにはNoneを返す。*/ def getHand(board:Board, bw:Char): Option[Pos] } /** 人間のプレイヤー */ class ManPlayer extends Player { def getHand(board:Board, bw:Char): Option[Pos] = { assert(board != null) assert(bw == Black || bw == White, bw) val hands = getMovableHands(board, bw) if (hands.size == 0) return None // 置ける場所がない場合は自動でPASS // 候補を表示 println("候補を表示") println(board.createCandidate(hands)) println("候補の中から選んで、番号を入力してください。(Ctrl-Cで中断)") var hand:Pos = null while (hand==null) { printPrompt(bw, this) // キーボードから文字列を入力。数値に変換。 try { import java.io._ val line = new BufferedReader(new InputStreamReader(System.in)).readLine() val sel = Integer.parseInt(line) - 1 hand = hands(sel) } catch { case _ => println("入力エラー！") } } Some(hand) } override def toString = "ManPlayer" } /** 次の手を、常に最初に見つけた候補を選ぶ間抜けなプレイヤー */ class StupidPlayer extends Player { def getHand(board:Board, bw:Char): Option[Pos] = { assert(board != null) assert(bw == Black || bw == White, bw) val hands = getMovableHands(board, bw) if (hands.size == 0) return None // 置ける場所がない場合、PASS // 常に最初の手を選ぶ。 Some(hands(0)) } override def toString = "StupidPlayer" } /** 次の手を、候補手の中からランダムに選ぶ間抜けなプレイヤー */ class RandomPlayer extends Player { def getHand(board:Board, bw:Char): Option[Pos] = { assert(board != null) assert(bw == Black || bw == White, bw) val hands = getMovableHands(board, bw) if (hands.size == 0) return None // 置ける場所がない場合、PASS // ランダムに選ぶ val hand = hands(randomInt(hands.size)) Some(hand) } /** 0..max-1までの乱数 */ private def randomInt(max:Int):Int = Math.floor(Math.random*max).toInt override def toString = "RandomPlayer" } /** 次の手で、最大の駒数になるように選ぶ、幼稚なプレイヤー */ class NextHandPlayer extends Player { def getHand(board:Board, bw:Char): Option[Pos] = { assert(board != null) assert(bw == Black || bw == White, bw) val hands = getMovableHands(board, bw) if (hands.size == 0) return None // 置ける場所がない場合、PASS // 最大の手を捜す。 var bestRate = -1000 var bestHand:Pos = null for (hand <- hands) { val next_board = flipPieces(board, bw, hand) val rate = next_board.count(bw) // 自分の駒が多ければよい。 if (bestRate < rate) { bestRate = rate bestHand = hand } } Some(bestHand) } override def toString = "NextHandPlayer" } /** MinMax法を使って選ぶ、多少マシなプレイヤー */ abstract class GenericMinMaxPlayer extends Player { /** 評価関数 */ def eval(board:Board, bw:Char): Int def getHand(board:Board, bw:Char): Option[Pos] = { assert(board != null) assert(bw == Black || bw == White, bw) getMinMaxHand(board, bw, bw, 3)._1 } /** PASSがあるので難しい・・・ */ private def getMinMaxHand(board:Board, bw:Char, self:Char, depth:Int): (Option[Pos], Int) = { def minmax(list:List[(Pos,Int)]): (Pos,Int) = { var (bestHand,bestRate) = list.head for ((hand,rate) <- list.tail) { if ((bw==self && bestRate > rate) || (bw!=self && bestRate < rate)) { bestHand = hand bestRate = rate } } (bestHand, bestRate) } // 深さが１なら、次の手で最善の手を返す。 if (depth==0) { val hands = getMovableHands(board, bw) if (hands.size == 0) return (None, eval(board, bw)) // 置ける場所がない場合、PASS val handratelist = hands.map(hand => { val next_board = flipPieces(board, bw, hand) val rate = eval(next_board, bw) (hand,rate) }) val (bestHand,bestRate) = minmax(handratelist) (Some(bestHand),bestRate) } else { val hands = getMovableHands(board, bw) val opp = getOpponent(bw) // 置ける場所がない場合、パスして次の候補を探す。 if (hands.size == 0) { val (pos,rate) = getMinMaxHand(board, opp, self, depth-1) return (None,rate) } // それぞれの盤面に対して評価値と手を取得し、最大の手を探す。 val handratelist = hands.map(hand => { val next_board = flipPieces(board, bw, hand) val (pos,rate) = getMinMaxHand(next_board, opp, self, depth-1) (hand,rate) }) val (bestHand,bestRate) = minmax(handratelist) (Some(bestHand),bestRate) } } override def toString = "GenericMinMaxPlayer" } /** MinMax法を使って選ぶ、多少マシなプレイヤー */ class SimpleMinMaxPlayer extends GenericMinMaxPlayer { /** 評価関数 */ def eval(board:Board, bw:Char): Int = board.count(bw) // 自分の駒が多ければよい。 override def toString = "SimpleMinMaxPlayer" } /** MinMax法を使って選ぶ、多少手強いプレイヤー */ class ClevarMinMaxPlayer extends GenericMinMaxPlayer { /** 重み付けテーブル */ val Weight = Array( Array(120, -20, 20, 5, 5, 20, -20, 120), Array(-20, -40, -5, -5, -5, -5, -40, -20), Array( 20, -5, 15, 3, 3, 15, -5, 20), Array( 5, -5, 3, 3, 3, 3, -5, 5), Array( 5, -5, 3, 3, 3, 3, -5, 5), Array( 20, -5, 15, 3, 3, 15, -5, 20), Array(-20, -40, -5, -5, -5, -5, -40, -20), Array(120, -20, 20, 5, 5, 20, -20, 120)) /** * 評価関数。 * 参考 http://hitsujiai.blog48.fc2.com/blog-entry-26.html */ def eval(board:Board, bw:Char): Int = { val opp = getOpponent(bw) var value = 0 for (y <- 1 to BoardSize) { for (x <- 1 to BoardSize) { val col = board.get(x, y) if (col == bw) value += Weight(y-1)(x-1) else if (col == opp) value -= Weight(y-1)(x-1) } } value } override def toString = "ClevarMinMaxPlayer" } object ReversiPlay extends ReversiGame { def buttle10(player1:Player, player2:Player):Unit = { // 10回対戦してどちらのプレイヤーが強いか調べる。 val ButtleCount = 4 var count1 = 0 var count2 = 0 for (i <- 1 to ButtleCount/2) { val winner1 = play(player1, player2) winner1 match { case Some(`player1`) => count1 += 1 case Some(`player2`) => count2 += 1 case None => } // 先攻後攻を交替でもう一度 val winner2 = play(player2, player1) winner2 match { case Some(`player1`) => count1 += 1 case Some(`player2`) => count2 += 1 case None => } } println("score "+player1+"="+count1+" "+player2+"="+count2+ " draw="+(ButtleCount-count1-count2)) } def main(args: Array[String]) { if (args.size > 0 && args(0)=="demo") { buttle10(new SimpleMinMaxPlayer(), new ClevarMinMaxPlayer()) } else { val b_player = new ManPlayer() val w_player = new ClevarMinMaxPlayer() play(b_player, w_player) } } }
