Boards 4.0

This is an ongoing project featuring:

1. BoardLang, a DSL for easily creating combinatorial games in Scala.
2. A collection of simple games implemented using BoardLang. (WIP)
3. Minimax and RL based solvers to play (2), implemented in a game-independent manner. (COMING SOON)
4. A web interface for playing (2) against (3) or other human players. (WIP)

Featured games (this list will continually expand):

1. Chess
2. Chaturanga

This is a continuation from a long lineage of similar projects (1.0, 2.0, 3.0).

Information for Developers

Project Structure

Boards is composed of 6 subprojects, which you will find in the top-level directories of the same names:

• dsl contains the implementation of the BoardLang DSL.
• games contains the rule specifications for the games themselves, written using BoardLang.
• bots contains general and game-specific strategies for playing these games.
• server code which is compiled to JVM bytecode for use on a web server. Handles user requests, authentication and persistence.
• client code which is transpiled to JS and served to the user's web browser. Handles rendering and user input.
• common code which is shared by both the server and client, and compiled into both projects. Primarily contains data formats for communication therebetween.

Requirements

Boards is written entirely in Scala, and in order to work on this project you will need the following:

• An up-to-date JDK for development in a JVM-based language.
• Scala 3.5.2 itself.
• sbt, the pre-eminent build tool for Scala projects.
• Git for version control.

Libraries

Boards relies on the following open-source libraries, this installation of which should be handled automatically by sbt:

• The Play Framework for handling web requests on the server.
• Slick for database access by functional relational mapping.
• H2 for running an embedded database.
• Apache Pekko, an actor framework, used here for managing server-side state in relation to web socket sessions.
• Circe for automatic serialisation/deserialisation to/from JSON.
• Laminar for client-side rendering.
• Airstream, which is required by Laminar, is a library for functional reactive programming.

Local Execution

To download the project into a subdirectory named Boards, run:

git clone https://github.com/SgtSwagrid/Boards.git

To run a local development server, navigate to the Boards directory and run:

sbt "project server" "~run"

You should then be able to access the website at localhost:9000 in your browser.

Development

For development purposes, it is recommended that you use IntelliJ IDEA with the Scala plugin. IntelliJ configuration files are deliberately included in the project to offer a uniform developer experience with consistent formatting rules, code highlighting and build configurations. If you are using IntelliJ, the Boards Development Server run option is equivalent to the command shown above.

In any case, the project is configured to automatically detect code changes while the server is running, so that changes are reflected immediately. Note however that this unfortunately isn't foolproof and if something isn't working, a full server restart is the safest option.

Architecture of the BoardLang DSL

A key commponent of Boards is BoardLang, an embedded domain-specific language (eDSL) for creating turn-based board games in Scala.

• You will find the implementation of BoardLang in dsl/src/main/scala/boards.
• You will find examples of games created using BoardLang in games/src/main/scala/boards.

Philosophy

BoardLang uses a functional style and all objects are immutable. Fundamentally, a game is built by defining some number of PieceTypess and composing Rules to precisely specify what the player can and can't do with these pieces. Each Action the player takes causes a transition to a new GameState in accordance with the current Rule.

Important Abstractions

• Game: A precise specification of the rules for a game (e.g. Chess, Connect Four, etc).

For the state of the game:

• InstantaneousState: The current "physical" state of the game. Contains the Board and current PieceSet, and tracks the activePlayerId.
• GameState: The total state of the game. Contains the entire game history, including all past InstantaneousStates and user Actions.
• Rule: A mechanism for, given some current GameState, enumerating possible player Actions and corresponding successor GameStates, as well as performing Action legality testing.

For the game board and pieces:

• Board: The topology of the game, describing which positions are in bounds and the connectivity therebetween.
• Piece: A specific piece that is on the board at a specific time in a specific place.
• PieceType: A property held by a Piece used to distinguish different kinds of pieces (e.g. rook, knight, etc).
• PieceSet: A set of Pieces, used in particular by an InstantaneousState, with specialised functionality for filtering, Action querying and modification.

Mathematical types:

• VecI: An integer vector representing a position on the Board.
• Ker: A set of vectors describing a region in space.
• Dir: A direction or set thereof, used for describing relative positions.
• Ray: A specific kind of Ker formed by making up to some number of steps in some Dir.

Rule Semantics

There are two important things to note about Rules in BoardLang:

1. A Rule is not Markovian in the current InstantaneousState, which is to say that the state transitions can depend arbitarily on the full state history in GameState. To see why, consider chess: en passant is legal only on the turn directly following the initial double pawn move. The account for this, the Rule must be able to see when and how the pawn being captured arrived in its current position.

2. The Rule itself is a property of the GameState, not of the entire Game. In particular, this means that the Rule is dynamic rather than static, meaning it can (and typically does) change over time. The Game specifies the initial Rule, and thereafter each successor GameState is infused with a new Rule upon creation. When a Rule generates successor GameStates, it is also responsible for determining which Rule should apply thereafter from that state. The reason is that this makes it much easier to reason about sequences of Actions, and implicitly provides support for two kinds of situation which arise very frequently: turn phases and game phases.

Turn Phases

In many games, the turn is divided up into multiple phases. For instance, maybe you first have to roll, then trade, and finally build. To implement this behaviour, one can simply create a separate Rule for each phase, and sequence them together, whereby each phase knows that when it is done, it should replace the Rule with the one corresponding to the next phase.

For an example, consider chess again: after a pawn moves to the final rank, as a separate action it must then promote. With a static Rule, the state would need some kind of a global flag indicating the need for promotion, to override the default behaviour on the next action. This moves the promotion logic outside of the pawn PieceType where it belongs. Instead, with a dynamic Rule, the pawn can simply infuse the successor GameState with a special, one-time promotion rule.

Game Phases

In some games, there are even multiple global game phases. For instance, it is common to have a separate setup phase, which still requires input from the players, but with completely different rules than the main phase (example: Catan). Again, with a dynamic Rule, this is easy to achieve without any global flags by creating a separate Rule for each phase and sequencing them in the same way as before.

Types of Rule

Any Rule is actually a tree of Rules, of the following basic kinds:

• Generator: The leaves of the Rule tree. A Generator simply enumerates legal Actions and the direct consequences thereof. For example, a king in chess might provide a Generator which produces one Move action for each octagonal direction.
• Effect: A passive effect which is only indirectly caused by the Action of the Player. For instance, when we castle in chess, a Generator allows the king to move, but then a susequent Effect ensures that the rook moves too as a result.
• Combinator: A composition of multiple simpler Rules, for reasoning about Action sequencing. For example, in chess, we need to take the union of Rules from individual Pieces to indicate that the Player can choose which Piece to move, then sequence this with Effect.endTurn, then repeat indefinitely. Combinators deliberately hide the dynamic nature of the current Rule, and automatically decide which Rule should apply next after each Action.

Using the BoardLang DSL

Worked Example with Chess

To use the BoardLang DSL, the following import is always required:

import boards.imports.games.{*, given}

Furthermore, any game must inherit from the base class Game:

class Chess extends Game

We can't have chess without a chessboard!

// A chessboard is an 8x8 grid.
override val Board = Kernel.box(8, 8)
  // The following is only required for aesthetic reasons:
  .paint(Pattern.Checkered(Colour.Chess.Dark, Colour.Chess.Light))

We may want to define some types of pieces, otherwise there won't be much to do in our game:

object Pawn extends PieceType.WithTexture(Texture.WhitePawn, Texture.BlackPawn)

object King extends PieceType.WithTexture(Texture.WhiteKing, Texture.BlackKing)

...

Often, the first thing that should happen is some setup. For example, if we're making chess, we might want to start with this Rule to insert a row of white pawns in the second rank from the bottom:

val setup = Effect.insert(/* The owner of the pieces. */ PlayerId(0))(Pawn -> Board.row(1))

After setup, we probably want some kind of main game loop:

val loop = Rule.alternatingTurns:
  ???

This particular Rule will repeat the body indefinitely, ending the turn after each iteration. For most turn-based games, this is how it works; the Players always play in the same clockwise or counterclockwise order.

Inside the main loop, we allow the Player to move one of their pieces:

pieces.ofActivePlayer.actions

pieces.ofActivePlayer is a PieceSet containing only those pieces belonging to the player whose turn it currently is. .actions produces a Rule which allows the Player to move one of the pieces in this PieceSet.

This won't do anything yet, because none of the pieces know which kinds of movement they can do. This can be fixed by having each moveable PieceType implement the actions method:

def actions(pawn: Pawn): Rule =
  pawn.move(if pawn.owner == 0 then Dir.Up else Dir.Down)

The abstract class Game only requires us to implement a single member, rule. This defines the initial Rule for our Game. In other words, from the start of the game, what happens and what are the players allowed to do?

def rule: Rule = setup |> loop

In the above, we start by setting up the game board, then we enter the main game loop.

Now the Players can move pieces around. But the Game will never end as Rule.alternatingTurns goes forever and we have no termination condition. In chess, the game ends when the current Player has no legal moves. For this, we can use the ?: operator (read: orElse) which specifies some alternative behaviour to use precisely when there are no legal Actions in the main path:

pieces.ofActivePlayer.actions ?: Effect.endGame(Draw)

Of course, chess shouldn't always end in a draw. To determine a winner, we also need check detection:

def inCheck(using GameState) = pieces.ofInactivePlayers.canCaptureType(King)

From here, it is also very easy to forbid the Player from taking any action that would result in them being in check. Instead of:

pieces.ofActivePlayer.actions

we use this:

pieces.ofActivePlayer.actions.require(!inCheck)

Now we can replace the termination Effect with:

Effect.endGame(if inCheck then Winner(state.nextPlayer) else Draw)

In other words, if there are no possible Actions, either we are in checkmate (lose) or stalemate (draw).

Important Operators

BoardLang provides a number of important operators for combining and modifying Rules. The most important ones are:

• |: An infix union operator for specifying that the Player may choose which of two Rules to follow. Also available in function notation as Rule.union for use with any number of alternative Rules.
• |>: An infix sequence operator for specifying that the Player must execute both Rules in the given order. Also available in function notation as Rule.sequence for user with any number of chained Rules.
• _.optional: For specifying that the Player can decide whether or not to execute this Rule.
• _.repeatXXX: There are various methods of this kind for performing a Rule multiple times. See Rule.scala for all variants.