Scala3でQuartoを実装してみた

## まえがき

みなさん、Quartoをご存知ですか？

自分は先日、会社で教えてもらって初めて知りました。

4x4のフィールドにコマを置いて勝敗を争うボードゲームなのですが、シンプルながらなかなかに奥深くて面白かったので、コードで表現してみることにしました。

そして、せっかくイチから書くなら、Scala3を採用してその表現力を生かしたい、ということで、コードは全部Scala3です。


以下、Scala3の新機能の紹介を交えながら、コードを解説していきます。

コードのリポジトリは[こちら](https://github.com/yuiwai/quarto)です。
日々ちょっとずつ、色々なアイデアを試していますので、必ずしもこの記事での解説が最新のコードと一致していない場合もあることをご了承ください。

> ScalaのバージョンはScala3.0.0-M3で書いています。


#### Optional Bracesについて

Scala3の新しいシンタックスとして[Optional Braces](https://dotty.epfl.ch/docs/reference/other-new-features/indentation.html)が採用されました。
今までブレースを書いていた箇所で省略できる記法です。

一例は以下のようなclass/trait/objectの定義です。

```scala
// これを
trait A {
  def f = ???
}

// こう書くこともできる
trait A:
  def f = ???
```

個人的にはこの新しい記法が好きなため、コードは基本的にはブレースを省略する方針で書いています。


## Quartoについて

まずはQuartoのルールを見ていきます。

[Quarto](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A2%E3%83%AB%E3%83%88_(%E3%83%9C%E3%83%BC%E3%83%89%E3%82%B2%E3%83%BC%E3%83%A0))は、２人で対戦するボードゲームです。

4x4のフィールドに交互にコマを置いていき、同じ属性のコマを4つ並べた方が「クアルト」と宣言することで勝利となります。

コマには以下の４種類の属性があります。

- 色: 白 or 黒
- 高さ: 高い or 低い
- 穴: あり or なし
- 形: 丸 or 四角

2x2x2x2で、計16種類のコマがあります。
フィールドも4x4で16マスなので、ちょうど全部埋まります。

そして、Quartoの大きな特徴で面白い点が、「相手が置くコマを選んで渡す」ところです。

プレイヤーは白/黒のそれぞれ８ピースを手元に持ち、相手に一つを渡します。渡された側はそれを任意のマスに置きます。
この繰り返しでゲームが進行していきます。


## Pieceの表現を考える

まずはQuartoの特徴である16種類のコマの表現を考えてみます。

それぞれ２種類の値を持つ属性が4つある、ということで、ビットによる表現が自然ではないでしょうか。

4つの属性それぞれに1ビットを割り当てる実装も考えられますが、今回は属性の種類ごとに1ビットを割り当てます(4属性x2種類=8ビット)。

実際のコードでの定義は以下のようになっています。

```scala
  private val EMPTY = 0
  private val HAS_HOLE = 1
  private val IS_FLAT = 2
  private val IS_SHORT = 4
  private val IS_TALL = 8
  private val IS_SQUARE = 16
  private val IS_CIRCLE = 32
  private val IS_BLACK = 64
  private val IS_WHITE = 128
```

例えば、**穴あり、高い、丸い、黒**のコマは

```scala
val p1 = HAS_HOLE | IS_TALL | IS_CIRCLE | IS_BLACK
```

と表現できます。

こうすることで、同じ属性を持ったコマが並んでいる状態の取得が容易になります。

例えば、4つ並んだコマ(p1, p2, p3, p4)が、同じ属性を持っているかどうかを以下のように判定できます。

```scala
// trueならクアルト！
p1 & p2 & p3 & p4 != 0
```


一方で、この実装だと本来はありえないような組み合わせが起こりえます。例えば、白と黒のビットが両方立っている状態などです。
このような不正な状態でコマが初期化されないように制約が必要ですが、それについては後述します。


## Union Typesによる座標の制約

Quartoの座標は4x4の制約があります。これをうまく型で表現できないでしょうか。

Scala3で加わった新しい強力な型に[Union Types](https://dotty.epfl.ch/docs/reference/new-types/union-types.html)があります。

TypeScriptではおなじみかと思いますが、**「 A or B or C 」**のような型を表現できるものです。

実際のコードではこれにLiteral-based Singleton types(という呼称でいいのかな？)を組み合わせて使っています（これは2.13でも使えます）。

```scala
type Coord = 0 | 1 | 2 | 3
opaque type Pos = (Coord, Coord)
```

> `opeque type` については後述します。ここでは `Pos` は `Coord` のタプル(x座標、y座標の意)だということだけ注目していただければ大丈夫です。

`Coord` は**「 0 or 1 or 2 or 3 」**を表す型です(0, 1, 2, 3も、ぞれぞれ型です)。
これにより、位置を表す `Pos` は、そのx座標、y座標に、**[ 0, 1, 2, 3 ]** のいずれかしか取れません。

もし仮に、 `Pos` の定義が

```scala
opaque type Pos = (Int, Int)
```

だとしたら、 `Int` が取りうる値全てが入る型になってしまいます。
もちろん、この実装でも動くのですが、前者の方がより詳細なルールを型で表している点で優れているかと思います。


`Union Types` は、Scala3に関するリサーチのアンケートでも人気だった機能で、これにより型の表現力が飛躍的に向上します。
乱用は良くないと思いますが、ここぞというところで上手く使うと、2系では難しかった柔軟な表現が出来るので、ぜひ活用してください!


## enumによる属性の表現(+α)

Scala3にはついに(?)、[enum](https://dotty.epfl.ch/docs/reference/enums/enums.html) が実装されました！

これまで、列挙型を作ろうとすると、`sealed` と `final` を組み合わせて頑張るなど、かなり冗長でした。
(Scala3のenumは、ざっくり言うと、この `sealed` 作戦の糖衣構文となります。詳細は[ドキュメント](https://dotty.epfl.ch/docs/reference/enums/desugarEnums.html)を読んでください）

今回は、このenumを属性の網羅に使ってみたいと思います。

```scala
// 穴の有無
enum Face:
  case Hole, Flat

// 高さ
enum Height:
  case Tall, Short

// 形
enum Shape:
  case Square, Circle

// 色
enum Color:
  case White, Black
```

非常にスッキリ書けますね！

これで、例えば色を引数で指定して欲しい、といった文脈では `Color` を受け取ることができます。


enumは引数を取ることもできます。
盤上にコマを置く操作の結果型として定義された、`PutResult` を見てみます。

```scala
enum PutResult:
  case Success(board: Board)
  case AlreadyExists(pos: Pos)
```

コマを置く処理が成功した場合は、`PutResult.Success(board)` が返ります。
`Board` は盤を表す型で、コマが置かれたあとの新しい状態の盤が渡ってきます。

一方、置こうとした場所にすでにコマが置かれていた場合、処理は失敗します。
その結果を表すのが `PutResult.AlreadyExists(pos)` です。
置こうとした位置を表す `pos` が渡ってきます。

enumはパターンマッチすることが出来るので、呼び出し元では次のようなコードを書くことになります。

```scala
putResult match
  case PutResult.Success(board) => ???
  case PutResult.AlreadyExists(pos) => ???
```

網羅性のチェックも行われて嬉しいですね！


また、enumにはメソッドも持てます。
（実際のコードにはありませんが）上記の `PutResult` に、成功かどうかを返す `isSuccess: Boolean` を足してみます。

```scala
enum PutResult:
  case Success(board: Board)
  case AlreadyExists(pos: Pos)
  def isSuccess: Boolean = this match
    case Success(_) => true
    case _ => false
```

この記法を使えば、列挙型全体の網羅的な処理を一箇所にまとめて書けるので、割と好きです。


## Opaque Type AliasesによるPieceの実装

前述の項ではコマ(`Piece`)をビットによって表現していることに触れましたが、不正な状態のコマが生成されてしまう可能性についての問題が残っていました。

ここでは、Scala3の新機能である [Opaue Type Aliases](https://dotty.epfl.ch/docs/reference/other-new-features/opaques.html) を利用してこの問題に対処してみたいと思います。

名前から想像できるように、この機能はある型のエイリアスを生成します。特徴は、このエイリアスが指し示す実体の型が、定義されたスコープ内からしか見えないということです。

`Piece` の実際の定義を見てみましょう。

```scala
// 部分的に抜粋
object Quarto:
  opaque type Piece = Int
```

`Quarto` オブジェクトの中で、`Piece = Int` というエイリアスが定義されています。
つまるところ、`Piece` は`Int` に過ぎないのですが、この事実は、`Quarto` オブジェクトの外からは見えないというのがミソ。

この`Piece` に、（スコープ外からも見える）振る舞いを足す方法は、次項で見ていきます。
ここでは、不正な`Piece` の生成を避けることにフォーカスしましょう。

```scala
object Quarto:
  opaque type Piece = Int
  object Piece:
    def empty: Piece = EMPTY
    def apply(face: Face, height: Height, shape: Shape, color: Color): Piece =
      EMPTY.withFace(face).withHeight(height).withShape(shape).withColor(color)
    def all(color: Color): Set[Piece] = 
      for {
        face <- Set(HAS_HOLE, IS_FLAT)
        height <- Set(IS_TALL, IS_SHORT)
        shape <- Set(IS_SQUARE, IS_CIRCLE)
      } yield (face | height | shape).withColor(color) 
```

`Quarto` オブジェクトの中に、`Piece` オブジェクトを配置し、その配下にファクトリメソッドを置きます。

`apply` は各属性の値を与えて`Piece` を返すメソッドですが、実際のゲーム中に新しくコマが生成されることは無く、あくまで検証用に用意したものです。
`withFace` や、`withHeight` といったメソッドは、`Piece` に生えているものですが、詳細は事項に譲ります。ここではよしなに指定された属性のビットをセットしてくるものです。

実際のゲームでは、色指定で全種類の`Piece` をまとめて返す`all` を使います。
（色を指定しているのは、対戦者が色別でコマを保持するので、分けた方が便利かな、と思ったからです）

`all` の実装を見るとわかりますが、右辺の型は`Set[Int]` です。
ですが、メソッドの返り値の型は`Set[Piece]` になっています。
ここは`Quarto` オブジェクトのスコープ内なので、`Piece = Int` が見えているため、このように書けるのです。外のスコープで`Int` を`Piece` にする手段はありません。

このようにファクトリメソッドを経由しなければコマを生成出来ないため、そのファクトリメソッドの中で生成のルールを守ってさえいれば、不正なコマを生成することを防げます。

さらに、`Opaque Type Aliases` を使うと、実行時には実体の型として扱われる(`Piece` は実行時にはただの`Int` )ため、余計なインスタンス生成のコストもかからないも嬉しい点です。

`Opaque Type Aliases`、とても便利ですね！


## Extension Methodsによる振る舞いの追加

前項で出てきた`Piece` の`withColor` などのメソッドは、どこから出てきたものでしょう。
`Piece` はただの`Int` なので、これらのメソッドは生えていません(もし生えていても、外のスコープからは見えません）。

これは、Scala3の新機能である、[Extension Methods](https://dotty.epfl.ch/docs/reference/contextual/extension-methods.html) によって実現しています。
Scala2の`implicit class` を置き換えたもので、特定の型に対してメソッドを拡張することができます。


具体的なコードを見て見ましょう。
`Quarto` オブジェクトのスコープ内に、以下のような`extension` の実装を置いています。

```scala
  // 部分的に抜粋
  extension(piece: Piece)
    def withFace(face: Face): Piece = face match
      case Face.Hole => piece | HAS_HOLE & ~IS_FLAT
      case Face.Flat => piece | IS_FLAT & ~HAS_HOLE
    def withHeight(height: Height): Piece = height match
      case Height.Tall => piece | IS_TALL & ~IS_SHORT
      case Height.Short => piece | IS_SHORT & ~IS_TALL
    def withShape(shape: Shape): Piece = shape match
      case Shape.Square => piece | IS_SQUARE & ~IS_CIRCLE
      case Shape.Circle => piece | IS_CIRCLE & ~IS_SQUARE
    def withColor(color: Color): Piece = color match
      case Color.Black => piece | IS_BLACK & ~IS_WHITE
      case Color.White => piece | IS_WHITE & ~IS_BLACK
```

こう書くことで、`Piece` に対して`withFace` などの一連のメソッドを拡張しています。

どんな型に対しても拡張が可能ですが、特に`Opaque Type Aliases` とのコンビネーションが強力で、**既存の型に別名を与えた上で、追加のメソッドを生やし、元の型の振る舞いを隠蔽する**、ということができます。

例えば、`case class` は非常に便利ですが、`copy` メソッドが強制的に公開されてしまうという悩みがありました。
`Opaque Type Aliases` と`Extension Methods` の組み合わせて、`copy` メソッドを隠蔽した上で、適切な更新系のメソッドを生やす、といったことができます。

雑な例ではありますが、こんな感じにできます。

```scala
object Building:
  private final case class ElevatorInternal(floor: Int) // privateなので、外からは見えない
  opaque type Elevator = ElevatorInternal // 外からはElevatorが見える
  object Elevator:
    def apply(floor: Int): Elevator = ???
  extension(elevator: Elevator):
    def up(): Elevator = ???
    def down(): Elevator = ???

val elevator = Building.Elevator(10)
elevator.up()
elevator.down()

// Compile Error! ここではcopyメソッドは見えない
elevator.copy()
```

外側を囲むオブジェクトのスコープの中に全てをおさめなければならないので、コードが若干煩雑になってしまう感は否めないのですが、それでも享受できるメリットの方が大きいと思います。


## Contextual Abstractionsによる思考部分の抽象化

Quartoにおいて、対戦者が思考する箇所は2つあります。

- 相手にどのコマを渡すか？
- 相手から渡されたコマを盤上のどこに置くか？


この2つの判断を提供する `Decider` を定義します。

```scala
trait Decider[F[_]]:
  def give(quarto: Quarto): F[Option[Piece]] // 渡すコマを選択
  def put(quarto: Quarto, piece: Piece): F[Option[Pos]] // コマを置く場所を選択
```

`F[_]` を使っているのは、同期/非同期などの効果を任意に選択できるようにするためです。

この`Decider` を使って、実際に「コマを渡す -> コマを置く」の流れを実装しているのが`QuartoOperation` です。

```scala
class QuartoOperation[F[_]](using decider: Decider[F], F: FlatMap[F]):
  def next(quarto: Quarto): F[QuartoResult] = 
    for {
      pieceOpt <- decider.give(quarto)
      posOpt <- pieceOpt.map(decider.put(quarto, _)).getOrElse(F.unit(None))
    } yield (pieceOpt, posOpt) match
      case (Some(piece), Some(pos)) => quarto.put(pos, piece)
      case _ => QuartoResult.Draw(quarto)
```

`(using decider: Decider[F] ...)` の部分は、Scala2のimplicit parameterに相当し、`Decider` の`F` に対するインスタンスを要求しています。

この`Decider` のインスタンスを与えるためには、`given` を使います。
例えば、`Future` に対するインスタンスを作る場合は、こんな感じになります。

```scala
given Decider[Future] = ???
```

書き方が色々あるので、詳しくは、[Given Instances](https://dotty.epfl.ch/docs/reference/contextual/givens.html) を読んでみてください。

Scala2では`implicit` が様々な使われ方をしていたが故に、有益ではあるけど、混乱も招くヤツという印象もありました。
Scala3では、用途に合わせて適切な構文が整備され、コードから意図が読み取りやすくなったと思います。


## [おまけ] Scala.jsでフロント実装

Scala3はすでにScala.jsをサポートしています。
つまり、Scala3で書いたコードはJavaScriptとして書き出しが可能です。

ということで、今回書いたQuartoのコードを使って、[フロントエンドもScala3で試作](https://github.com/yuiwai/quarto/tree/master/js)しています。

まだまだ模索中で、やりたいことに合わせてコードもゴリゴリ変わっている状態ですが、その中で便利だと思ったScala3の新機能である [Context Functions](https://dotty.epfl.ch/docs/reference/contextual/context-functions.html) についてご紹介します。

何かしらのコンテキスト(例えば、`ExecutionContext` など)を引回す際、Scala2の場合はimplicitな引数を使用して以下のように書きます。

```scala
def runAsync(implicit ec: ExecutionContext): Result = ???
```

これScala3ではを次のように書くことができます。

```scala
def runAsync: ExecutionContext ?=> Result = ???
```

返り値の型が`ExecutionContext ?=> Result` となっています。
「暗黙の引数として`ExecutionContext` を受け取って、`Result` を返す関数」を返すイメージです。

このように、一つの型の中に含めて書くことが出来るようになったおかげで、柔軟な取り扱いが出来るようになりました。
例えば、`Context Function` にエイリアスを作ったり、`Context Function` を引数に受け取ったりなどです。

今回のQuartoの実装ではゲームUIの描画にCanvasを使っているのですが、`CanvasRenderingContext2D` を引き回す必要があります。
ネストされた描画のメソッドで毎回コンテキストを引数に書くのは面倒ですし、コードもごちゃごちゃしてきます。
そこで、こう書けます。

```scala
// 説明のためのサンプルで、実際のコードとは異なっています
type DrawOpe = CanvasRenderingContext2D ?=> Unit
def drawPiece(pos: Pos, piece: Piece): DrawOpe = ctx ?=> ???
def drawPathWithFill(ope: DrawOpe): DrawOpe = ctx ?=> ???
```

`DrawOpe` は、`CanvasRenderingContext2D` を受け取る`Context Function` を表す型です。
このコンテキストを受け取って使うには、メソッド本体で`ctx ?=> ` のようにします。
そして、`DrawOpe` を引数に受け取ることもできるため、ネストもキレイに書けます。

この構文は、Scala3.0.0-M3になってもなお変更があったくらい、練りに練られたもので、とても使いやすい形になっていると思います（さすがに、もう変わらないはず...）。


## あとがき

Scala3の新機能の一部の紹介を交えながら、実際のコードを解説してみました。
もちろん、Scala3の新機能はまだ他にもありますので、気になった方はぜひ[ドキュメント](https://dotty.epfl.ch/docs/reference/overview.html)を読んでみてください。

Scala3では、Scala2で使いにくかった部分が改善され、痒いところにより手が届くようになったと思います。

特に、個人的には今回紹介した `Opaque Type Aliases` がお気に入りです。
実装時の強い制約を実現しつつ、実行時のパフォーマンスも良いので、一石二鳥ですね！

また、Quartoのようなシンプルで奥深いボードゲームは、コードを書く題材としても非常に良いです。
今回の自分の実装はただの一例に過ぎないので、もっと良い表現がないか、模索していただくのも楽しいと思いますし、他のボードゲームなどもコードに落としてみると面白いのではないでしょうか。

年末年始はぜひ、Scala3に触れつつ、お好きなボードゲームで遊んでください！
それでは、良いお年を！