Pierre-Henry Fröhring's Website

Enough of a chess game is implemented to experiment with Actor Model ideas. Pinned pieces and threatened squares are detected. The implementation of these situations is discussed, particularly how the topology of the network of Actors aids computations, and what it means for an object x to be an Actor.

The objective is to implement a chess game, just enough to test Actor Model ideas. Besides showing proper chess board, we are interested in implementing two cases:

Detecting that a piece is pinned.
Preventing the king from moving to a threatened square.

A click on INIT then ATTACKED SQUARE shows that the white king cannot move up because the target square is threatened by a black bishop.
A click on INIT then PINNED shows that the white king cannot move up because the target square is threatened by the queen.

Green squares indicate squares that may represent threats to a king but have been verified not to.
Red squares indicate squares that may represent threats to a king and have been verified to do so.
A blue square indicate a square that may be moved to.
The implementation is available here: GitHub.

JavaScript Actor

The board is an Actor. Thinking above the code, its implementation is:

class Board extends Actor { /* * State * * Store the squares. * Store the kings. * Store the turn. */ /* * Constructor * * Given: * - a HTML Canvas * * Build the board. * Place all pieces. * It is the white team's turn. */ /* * Interface * * move: * Given: * - a start position * - an end position * * If possible, move the piece from the start position to the end position. * else: throw an error. */ }

A square is an Actor. Thinking above the code, its implementation is:

class Square extends Actor { /* * State * * Store its canvas. * Store its color. * Store its neighbors. * Store its piece. * Store its position. * Store its width. */ /* * Constructor * * Given: * - a canvas * - a position * - a width * - a color * * Initialize its state and draw the square on the canvas. */ /* * Interface * * various accessors: canvas, position, … * * is_empty: * replies a boolean that tells if it is occupied by a piece or not. * * add_neighbor: * Given: * - a direction * - a square * * Add the square as a neighbor in the given position. * * … */ }

Each square has neighbors. For a given direction dir (e.g., top), the neighbor of a square s is given by s.get_neighbor(dir) ≡ s'. Given that s has a neighbor s', we can infer that s' also has a neighbor s. Starting from s at the top left corner of the board, we can construct a network of neighboring squares:

If we consider two neighbors, s and s', we represent their relationship with an edge. By doing this step by step, we create the network of squares that represents the chessboard:

A square may be occupied by at most one piece. A piece may occupy at most one square. So, we may add the pieces to the network of squares.

We just superpose the piece and the square to represent this relation.

Assume that we have the board configuration below. From the point of view of the black king, the white bishop is a threat.

How to detect the threat of the black king? By sending probes.

A probe is an Actor. Its above the code description is:

class Probe extends Actor { /* * State * * It has a square. * It has a direction. * It detects pieces of a given team. * It detects pieces of a given type (bishop, rook, or queen). */ /* * Constructor * * Its state is initialized. */ /* * Interface * * start: * next_square is the next square in the given * direction from this probe square. * * next_piece is the piece on the next square if any. * * If the next square is empty, then: this square is safe * and the probe can move to the next square and start again. * * If there is a next piece and it is from the given type and * is on the opposite team, then: throw an exception and die. * * In any other case, the probe dies. * */ /* * Private */ #move(square) { this.#square = square; return this.start(); } }

To detect if a square is threatened by a bishop, it is enough to know that a bishop of the adversary team has a direct view of the given square. Before moving, the king builds four probes like so (in pseudo-code):

move(square) { … opposite_team : Team top_right, bottom_right, bottom_left, top_left : Direction const directions = [top_right, bottom_right, bottom_left, top_right] const bishop_probe = (dir) => new Probe(square, dir, opposite_team, Bishop) directions.forEach((dir) => bishop_probe(dir).start()) … }

Each probe starts simultaneously and travels, maybe in parallel, along the specified direction, searching for a bishop from the opposing team. When a bishop is found, the probe raises an exception to signal that a threat has been detected. Visually, it appears like this:

Looking for a bishop — A probe is created looking at the top right direction

A similar idea is described using this animation: the probes are moving from one square to the next, jumping from one neighbor to the other. Each node and each probe may be mapped to a different process.

Reinterpreting the code in terms of actors and message passing requires minimal effort. For instance, when the browser accesses this page at:

https://phfrohring.com/page/4ccb9b46-4a7e-4cdc-afc5-cce043e00fc4

It sends an HTTP protocol message requesting this web page. The web page contains the following code:

This code can be interpreted as follows: the browser sends a message to the web server, requesting the file data/chess.js. Subsequently, it sends a message to itself, requesting the evaluation of the associated JavaScript code.

When evaluating the code, the browser executes window.chess = build();. This execution can be understood as follows: the browser handles the message build and stores the result in window.chess.

When detecting a threat, the king dispatches probes.
Each probe acts as an independent actor.
Any two probes can execute in parallel.
All probes use the graph structure in a read-only manner to traverse from their original square. They are superimposed on the graph and do not interfere with each other.
If it were possible to allocate a process to each actor, this code would naturally benefit from parallelism without requiring any additional adjustments.

To conclude, this project demonstrates several principles of the Actor Model using a partial implementation of a chess game as an illustration.

By focusing on key functionalities such as detecting pinned pieces and preventing illegal moves, it highlights how the Actor Model can be applied to solve problems using simple rules in a few lines of code and, most importantly, the shape of the network of actors.

The superposition of actors and their non-interference offers significant potential for optimization through parallelism: the code could be parallelized by a runtime without any modification while preserving its straightforward semantics.

Looking ahead, implementing this model using a more suitable runtime, like the EVM, would be valuable to confirm these initial findings and intuitions.