ScalaでReversi

ReversiをScalaでコーディングしてみる。

MarkerはEnumeration

object Marker extends Enumeration {
  type Marker = Value
  val Blank, Dark, Light = Value
}
import Marker._

ゲームを抽象的に表すためにMarker, Move, Nodeを次のように定義。

class Move()
object Move {
  val empty: Move = new Move
}

case object Pass extends Move
case class PutMarker(x: Int, y: Int) extends Move {
  override def toString: String = {
    val xs = ('a' + x).asInstanceOf[Char]
    val ys = ('1' + y).asInstanceOf[Char]
    "" + xs + ys
  }
}

trait Node[Repr <: Node[Repr]] {
  def play(move: Move): Option[Repr]
  def possibleMoves(): Seq[Move]
  def isTerminal: Boolean

  val marker: Marker = Dark
  lazy val opponentMarker: Marker =
    if (marker == Dark) Light else Dark
}

実際のreversiゲームにはNodeを通してアクセスされることになる。

class ReversiNode (
    override val marker: Marker,
    val board: ListBoard
) extends Node[ReversiNode] {
 
  override def play(move: Move): Option[ReversiNode] =
    (move: @unchecked) match {
      case Pass =>
        Some(new ReversiNode(opponentMarker, board))
      case PutMarker(x, y) =>
        if (board(x, y) != Blank) return None
        val (b, n) = reverse(x, y)
        if (n > 0)
          Some(new ReversiNode(opponentMarker, b))
        else
          None
    }

  private def reverse(x: Int, y: Int): (ListBoard, Int) = {
    var b = board.updated(x, y, marker)
    var n = 0
    for (t <- List((-1, -1), (-1, 0), (-1, 1),
                   (0, -1), (0, 1),
                   (1, -1), (1, 0), (1, 1))) {
      val (b2, dn) = reverseDxDy(b, x, y, t._1, t._2)
      b = b2
      n += dn
    }
    (b, n)
  }

  private def reverseDxDy(b: ListBoard, x: Int, y: Int, dx: Int, dy: Int): (ListBoard, Int) = {
    val n = opponentMarker
    var b2 = b
    var c = 0
    var s = x + dx
    var t = y + dy
    while (s >= 0 && s < 8 && t >= 0 && t < 8 && b2(s, t) == n) {
      b2 = b2.updated(s, t, marker)
      c += 1
      s += dx
      t += dy
    }
    if (c > 0 && s >= 0 && s < 8 && t >= 0 && t < 8 && b2(s, t) == marker) (b2, c)
    else (b, 0)
  }

  def possibleMoves(): Seq[Move] = {
    val moves = 
        for { x <- 0 until 8
              y <- 0 until 8
              if (board(x, y) == Blank)
              (b, n) = reverse(x, y)
              if (n > 0)
        } yield PutMarker(x, y)
    if (moves.isEmpty) List(Pass)
    else moves
  }

  def isTerminal: Boolean = {
    if (board.isFull) return true
    if (possibleMoves == List(Pass)) {
      val next = play(Pass).get
      if (next.possibleMoves == List(Pass)) {
        return true
      }
    }
    false
  }

  def winner: Marker = {
    val nums = board.numOfMarkers
    if (nums(Dark) < nums(Light)) Light
    else if (nums(Light) < nums(Dark)) Dark
    else Blank
  }

  override def toString: String =
    board.toString

}


object ReversiNode {
  val Start: ReversiNode =
      new ReversiNode(Dark,
                      new ListBoard().updated(3, 3, Light)
                                     .updated(4, 4, Light)
                                     .updated(3, 4, Dark)
                                     .updated(4, 3, Dark))
}


trait Board { def apply(x: Int, y: Int): Marker
  def updated(x: Int, y: Int, m: Marker): Board
  def numOfMarkers: Map[Marker, Int]
}

class ListBoard (
  private val list: List[Marker]
) extends Board {

  def this() = this(List.fill(64) { Blank })

  override def apply(x: Int, y: Int): Marker = list(index(x, y))

  override def updated(x: Int, y: Int, m: Marker): ListBoard =
    new ListBoard(list.updated(index(x, y), m))

  private def index(x: Int, y: Int) = x + y * 8
  
  override def numOfMarkers: Map[Marker, Int] = {
    val map = mutable.HashMap.empty ++
        (Marker.values map {_ -> 0})
    for (m <- list) {
      map(m) = map(m) + 1
    }
    map.toMap
  }

  override def toString: String = {
    val map = Map(Blank -> '.', Dark -> 'X', Light -> 'O')
    val ax = " abcdefgh \n"
    val b = for {y <- 0 until 8
                 ay = ('1' + y).asInstanceOf[Char]
                 l = for (x <- 0 until 8) yield map(list(index(x, y)))
    } yield ay + l.mkString + ay + '\n'
    ax + b.mkString + ax
  }

  def isFull: Boolean = list.forall { _ != Blank }

}

Playerは自分のmarkerを持ち、playすることができる。

trait Player[N <: Node[N]] extends NodeCount {
  var marker: Marker = _
  var opponentMarker: Marker = _
  var name: String = ""

  def init(m: Marker) {
    marker = m
  }
  
  def play(ply: Int, node: N, last: Move): Move
}

可能な手の中からランダムに手を選びプレイするRandomPlayer。馬鹿らしいPlayerだけど、これに5割以上で勝てないPlayerもあり得ることに注意。

class RandomPlayer[N <: Node[N]] extends Player[N] {
  override def play(ply: Int, node: N, last: Move): Move = {
    val moves = node.possibleMoves()
    if (moves.length > 0)
      moves(Random.nextInt(moves.length))
    else
      Move.empty
  }
}

Github https://github.com/stn/reversi/blob/master/src/main/scala/

2011/06/07: コードを更新
2011/06/25: コードを更新