README.md 36.4 KB
Newer Older
Brady James Garvin's avatar
Brady James Garvin committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
# Boost Board Game Application (Fall 2021 Version)

A progressive web app (PWA) for learning and playing the board game Boost.

Boost is a turn-based abstract strategy board game like checkers, chess,
Xiangqi, or Shōgi.  It was designed to be new and interesting for humans to play
while still admitting a simple AI and supporting various homework assignments on
algorithms and data structures in the SOFT 260 course at UNL.

# Quick Start

Recursively clone this repository and `cd` into the root folder:

```
$ git clone --recursive git@git.unl.edu:soft-core/soft-260/boost-board-game.git
$ cd boost-board-game
```

(If you forget `--recursive` when cloning, you can `cd` into your clone and run
`git submodule update --init --recursive` instead.)

Install dependencies:

```
$ npm install
```

(Near the end you may see some warnings because `create-react-app` transitively
depends on some deprecated packages.)

Optionally run the test suites to make sure everything so far is okay:

```
$ npm run test
```

And then serve the application locally:

```
$ npm start
```

Once the app is running, click on the "Rules" button to read the rules of the
game.

When you are done, press control-c to stop the server.

# Development Workflow

The project includes a VSCode workspace named `boost-board-game.code-workspace`.
Most development tasks can be completed from within VSCode, though command-line
development is also possible.  The subsections below describe how to perform
common development tasks.

## Code Generation

As described later in the architecture overview, some projects depend on code
generated by other projects.  Normally this code generation happens
automatically when you lint, test, build, or run the app, but if you need to
force an update (for example, if you change the game or engine code while the
app is still running), you can use a project's `generate` script.  In VSCode,
the `generate` scripts can be run from the "NPM SCRIPTS" tray, where the
`generate` script in the outermost `package.json` generates code for all
projects.  Or, on the command line:

```
$ (cd …; npm run generate)
```

for a specific project or

```
$ npm run generate
```

for all projects.

## Linting

VSCode should automatically detect each project's stylelint and ESLint
configurations and dependencies and run those tools on the fly as you edit the
code, though you may have to tell VSCode to trust the project the first time you
open it.

Alternatively, you can also manually lint.  In VSCode, the `lint` scripts can be
run from the "NPM SCRIPTS" tray, where the `lint` script in the outermost
`package.json` generates code for all projects.  Or, on the command line:

```
$ (cd …; npm run lint)
```

for a specific project or

```
$ npm run lint
```

for all projects.

Because of a Git precommit hook, linting happens automatically when you commit,
and commits are blocked if there are any linting errors.

## Unit Testing

Individual projects' unit test suites are set up to run in "watch" mode by
default, which means that you can start the test script once, and it will rerun
the test suite every time you save a code change.  In VSCode, the `test` scripts
can be run from the "NPM SCRIPTS" tray.  Or, on the command line:

```
$ (cd …; npm run test)
```

If you want to run the tests only once and not watch for code changes, you can
use the `test-once` scripts.  On the command line:

```
$ (cd …; npm run test-once)
```

Alternatively, to run the unit tests once for all projects, run either the
`test` or the `test-once` script from the outermost `package.json`.  From the
command line:

```
$ npm run test
```

On the command line only, if you want to only run tests whose names match some
text, you can pass the standard `-t` option to a project-specific `test` or
`test-once` script:

```
$ (cd …; npm run test -- -t '[some test-name text]')
```

## System Testing

The main app is set up to run in "watch" mode, which means that you can start it
once, and it will refresh the page in your browser every time you save a code
change.  From VSCode, run the outermost `package.json`'s `start` script from the
"NPM SCRIPTS" tray.  Or, on the command line:

```
$ npm run start
```

Alternatively, the `start` script in the `boost-app` project also starts the
app, but without rebuilding the engine.  It can be run either from the "NPM
SCRIPTS" tray or the command line:

```
$ (cd boost-app; npm run start)
```

Automatic refreshes due to code changes will *not* clear any persisted Redux
state.  Because the app uses the local storage engine from `redux-persist` for
persistence, you can clear your data during development by running
`localStorage.clear()` in the developer console and then manually refreshing the
page.

## Deployment

The main app runs entirely client-side, so it can be deployed as a `build`
folder to be placed on any hosting platform.  From VSCode, run the the outermost
`package.json`'s `build` script from the "NPM SCRIPTS" tray.  Or, on the command
line:

```
$ npm run build
```

Alternatively, the `build` script in the `boost-app` project also builds the
app, but without rebuilding the engine.  It can be run either from the "NPM
SCRIPTS" tray or the command line:

```
$ (cd boost-app; npm run build)
```

At the end of either command's output you should see a link to further
deployment instructions.

# Architecture Overview

The code for the Boost board game application is organized as follows:

*   The project `@unlsoft/stylelint-config` contains the stylelint configuration
    for the CSS coding style used across the other projects.

*   The project `@unlsoft/eslint-config` contains the ESLint configuration for
    the JavaScript coding style used across the other projects.  Per
    `create-react-app` convention, in a development build of the main app, a
    separate, weaker coding style also warns at runtime about likely bugs.

*   The project `@unlsoft/boost-game` is responsible for representing positions
    as bit boards and for features that rely on bit-board operations to run
    acceptably fast, primarily move generation and static evaluation.  Because
    so much of the bit-board logic can be precomputed and unrolled,
    `@unlsoft/boost-game` does not implement game logic itself, but is actually
    a parameterized code generator that writes game logic into separate
    JavaScript files.

*   The project `@unlsoft/boost-engine` contains the game-playing engine, the
    application's AI.  Like other abstract strategy board game engines, this
    engine is designed to run in a separate thread or process from any UI, and
    it communicates with a controller using a protocol called BEI (see the
    protocol documentation further below).  The engine has a library of games
    that it knows how to play, and its build system automatically generates the
    source code for each of these games using `@unlsoft/boost-game`.

*   The project `@unlsoft/boost-app` is a `create-react-app` PWA that provides
    the application's game controller and UI.  Like `@unlsoft/boost-engine` it
    relies on a game library generated by `@unlsoft/boost-game`, and it also
    includes `@unlsoft/boost-engine` as a suite of web workers via symlink.

# Generating `Game` Objects with `boost-game`

When `@unlsoft/boost-game` is installed as a development dependency, it provides
a command `generate-boost-game` that writes a JavaScript implementation of a
Boost game to standard out.  The exact code produced depends on a number of
command-line options, described below.  You can also run `generate-boost-game
--help` to see a list of all of the above options, their short descriptions, and
their default values.

## Command-Line Options Affecting Game Rules

There are six main command-line options that can be passed to
`generate-boost-game` to control what kind of game is generated:

*   `--board-width [number]` sets the width of the game board in points.  If
    omitted, the default width of nine points is used.

*   `--board-height [number]` sets the height of the game board in points.  If
    omitted, the default height of nine points is used.

*   `--player-count [number]` sets the number of players (and therefore the
    number of non-dragon piece colors).  If omitted, the default of two players
    is used.

*   `--starting-population-limit [number]` sets the maximum number of starting
    pawns given to each player in a standard board setup.  (It is only a maximum
    because the game code may give players fewer starting pieces when the
    board's perimeter is too crowded.)  If omitted, the default limit of eight
    pawns is used.

*   `--tower-limit [number]` sets the maximum number of towers that each player
    may build.  (This limit only affects when construction moves are available
    to a player; it does not preclude other code from placing extra towers on
    the board.)  If omitted, the default limit of two towers is used.

*   `--demo` overrides the usual rules to allows players to move their pieces
    even when they are defeated.  This can be useful both in testing and
    tutorials for keeping the number of pieces on the board down.

Based on these six options, the game will be assigned a unique string of the
form `boost-[width]-[height]-[players]-[population]-[towers]` or of the form
`boost-[width]-[height]-[players]-[population]-[towers]-demo`, which is called
its **game identifier**.  For example, the game identifier for a standard Boost
game is `boost-9-9-2-8-2`.

## Command-Line Options Affecting the AI

Other command-line options are also available to tweak the weights in the static
evaluation function, which is the function used by `@unlsoft/boost-engine` to
estimate how favorable a position is for each player.  The defaults values, used
when these options are omitted, were chosen by human intuition and are given in
decitempi (tenths of an extra turn).  However, these defaults have not been
empirically validated yet.  If they are changed, care must be taken to consider
what behavior is incentivized by their relative values.  For example, if the
value for being in book is too high relative to the value of a tower, the AI
might forego its second tower to shuffle its pieces instead of exiting the book
line cleanly.

The command-line options for static evaluation weights are as follows:

*   `--ai-pawn [number]` sets the estimated value of a pawn.  The default value
    is 200 decitempi (20 extra turns).

*   `--ai-knight [number]` sets the estimated value of a knight when a player
    has all of their towers.  The default value is 220 decitempi (a pawn plus
    two extra turns).

*   `--ai-endgame-knight [number]` sets the estimated value of a knight when a
    player does not have all of their towers.  The game also computes an
    appropriate fixed penalty for a player not having all of their towers so
    that the AI is not incentivized to sacrifice its towers to make its knights
    more valuable.  The default value is 350 decitempi (a pawn plus 15 extra
    turns).

*   `--ai-knight-activity [number]` sets the estimated value of moving a knight
    one point closer to the closest non-friendly piece (i.e., a dragon or a
    foe).  The default value is 5 decitempi (an extra half turn).

*   `--ai-zero-activity-distance [number]` sets the distance, in points, that
    must lie between a knight and the closest non-friendly piece for that knight
    to have an activity score of zero.  As a knight moves closer to the
    non-friendly piece, its activity score becomes positive (at the rate given
    by `--ai-knight-activity`), and as it moves farther away, its activity score
    turns negative (at the same rate).  The main use of this parameter is to
    control the relative value of pawns and inactive knights; because an
    inactive knight prevents a player from promoting a better-positioned pawn,
    the knight can actually be a liability.  The default value is four points
    (so a knight eight points from the nearest non-friendly piece is estimated
    to be worth the same as a pawn).

*   `--ai-edge-knight-penalty [number]` sets the estimated decrease in value for
    having a knight on the edge of the board.  The default value is 30 decitempi
    (a loss of three turns).

*   `--ai-in-book [number]` sets the estimated value of remaining in book during
    the opening.  (An opening book is a precomputed policy for how to play
    certain opening positions, and in Boost the opening book usually covers
    lines up through construction of a second tower.  If the AI is "in book", it
    has a position covered by that policy, though it is still free to improvise
    variations; if it is "out of book", then it must rely on search alone.)  The
    default value is 30 decitempi (3 turns).

*   `--ai-construction-site [number]` sets the estimated value of a completed
    construction site (a circle of four friendly pieces around an empty point).
    Partial construction sites are awarded partial points: 1/16 value for a
    construction site with one piece in place, 4/16 value for a construction
    site with two pieces in place, and 9/16 value for a construction site with
    three pieces in place.  The number of construction sites that the AI can
    score for each side is limited by the number of additional towers that the
    player can usefully build.  Additionally, construction sites are ineligible
    for scoring if they are not within four points of four friendly mobile
    pieces.  The default value is 80 decitempi (8 turns).

*   `--ai-tower [number]` sets the estimated value of a tower when a player has
    at least four mobile pieces.  The default value is 125 decitempi (12.5 extra
    turns).

*   `--ai-endgame-tower [number]` sets the estimated value of a tower when a
    player does not have at least four mobile pieces.  The game also computes an
    appropriate fixed penalty for a player not having four mobile pieces so that
    the AI is not incentivized to sacrifice its pawns and knights to make its
    towers more valuable.  The default value is 700 decitempi (70 extra turns).

*   `--ai-dragon-proximity [number]` sets the estimated value of moving a dragon
    one point closer to the closest friendly tower when there are at least four
    dragons on the board.  The default value is 10 decitempi (an extra turn).

*   `--ai-tight-spot-penalty [number]` sets the estimated decrease in value for
    having a dragon in a "tight spot"—diagonally between a tower and an edge of
    the board.  The default value is 30 decitempi (three extra turns).

*   `--ai-circle-dragon [number]` sets the estimated additional value of moving
    a dragon next to a friendly tower when there are at least four dragons on
    the board.  The default value is 100 decitempi (ten extra turns).

*   `--ai-crowd-member [number]` sets the estimated additional value of a piece
    that has at least three other friendly pieces at most four points away.  The
    default value is 1 decitempo (one tenth of an extra turn).

*   `--ai-defeat [number]` sets the estimated value of defeating one opponent of
    many.  The default value is 1,000,000 decitempi (100,000 extra turns).

*   `--ai-victory [number]` sets the estimated value of defeating all opponents.
    The default value is 10,000,000 decitempi (1,000,000 extra turns).

## Typical Usage

By convention, one usually redirects the output of `generate-boost-game` to
JavaScript files in a `…/src/games` folder and then writes code like

```
import …_GAME from './games/….js';
import …_GAME from './games/….js';

const GAME_LIBRARY = new Map([
  …_GAME,
  …_GAME,
].map((game) => [game.identifier, game]));
export default GAME_LIBRARY;
```

in `…/src/gameLibrary.js` so that other code can import the game library and
look up games by their identifiers.

# Using `Game` Objects from `@unlsoft/boost-game`

`Game` objects from a game library provide the following fields and methods:

## Constants from Game Generation

These constants are set at code generation time, as described earlier:

*   `game.identifier` is the identifier for the game, as described in the
    previous section.

*   `game.boardWidth` is the width, in points, of the board on which the game is
    played.

*   `game.boardHeight` is the height, in points, of the board on which the game is
    played.

*   `game.playerCount` is the number of players in the game.

*   `game.populationLimit` is the maximum number of starting pawns given to each
    player in a standard board setup.

*   `game.towerLimit` is the maximum number of towers that each player may
    build.  (This limit only affects when construction moves are available to a
    player; it does not preclude other code from placing extra towers on the
    board.)

*   `game.victory` is the static evaluation returned by `getStaticEvaluation`
    (see its description in the section on static evaluation) if the player has
    won the game.

## Piece Types

These constants represent the different piece types, which are returned by
`position.getColorAndPieceType` and passed to `position.modified` as described
later:

*   `game.dragon` is a constant value used to represent a dragon.

*   `game.pawn` is a constant value used to represent a pawn.

*   `game.knight` is a constant value used to represent a knight.

*   `game.tower` is a constant value used to represent a tower.

Although they must be serializable and are therefore not `Symbol`s, they should
still be considered opaque.  Do not write code depending on them having
particular values.

## Algebraic Notation

The following fields and helper methods are useful for encoding and decoding
algebraic notation for files, ranks, points, and moves:

*   `game.prettifyFile(file)` takes a file as a zero-based 𝑥 coordinate and
    returns the corresponding letter in algebraic notation.

*   `game.unprettifyFile(file)` takes a file as a letter in algebraic notation
    and returns the corresponding zero-based 𝑥 coordinate.

*   `game.prettifyRank(rank)` takes a rank as a zero-based 𝑦 coordinate and
    returns the corresponding digits in algebraic notation.

*   `game.unprettifyRank(rank)` takes a rank as a string of digits in algebraic
    notation and returns the corresponding zero-based 𝑦 coordinate.

*   `game.noPoint` is the constant string representing no point at all in
    algebraic notation.

*   `game.prettifyPoint(file, rank)` takes a point as zero-based 𝑥 and 𝑦
    coordinates and returns the corresponding algebraic notation.  If either
    coordinate is `undefined`, it returns `game.noPoint`.

*   `game.unprettifyPoint(point)` takes a point in algebraic notation and
    returns the corresponding zero-based 𝑥 and 𝑦 coordinates in an `Array`.  If
    the point is `game.noPoint`, both coordinates will be `undefined`.

*   `game.pass` is the constant string representing a pass in algebraic
    notation.

*   `game.joinPoints(fromPoint, toPoint)` takes two points in algebraic notation
    and returns the algebraic notation for a move from `fromPoint` to `toPoint`.
    For constructions and promotions, one point may be omitted or set to
    `game.noPoint`, or the two points may be set equal to each other.  (For
    consistency with `game.splitMove` and the main app's UI, the preferred
    practice is to give the same point for both arguments.)  For passes, both
    points should be omitted or set to `game.noPoint`.  (For consistency with
    `game.splitMove`, the preferred practice is to pass `game.noPoint` for both
    arguments.)

*   `game.splitMove(move)` takes a move in algebraic notation and returns the
    algebraic notation for its "from" and "to" points in an `Array`.  For
    constructions and promotions, the "from" point will be the same as the "to"
    point.  For passes, both points will be `game.noPoint`.

*   `prettifyMove(fromFile, fromRank, toFile, toRank)` takes a move as
    zero-based 𝑥 and 𝑦 coordinates for its "from" and "to" points and returns
    the algebraic notation for the move.  Coordinates may be omitted or
    `undefined` for special moves in the same places where `game.joinPoints`
    would take `game.noPoint`.

*   `unprettifyMove(move)` takes a move in algebraic notation and returns the
    corresponding zero-based 𝑥 and 𝑦 coordinates for its "from" and "to" points.
    Coordinates will be repeated for constructions and promotions, and will be
    `undefined` for passes.

## Positions

The following fields and helper method are useful for obtaining `Position`
objects corresponding to the game:

*   `game.blankPosition` is a position containing no pieces.

*   `game.startingPosition` is the game's standard starting position without any
    dragons.

*   `game.deserializePosition(serialization)` deserializes a position previously
    encoded as a string with `position.serialization`, a property described
    further below.

# Using `Position` Objects from `@unlsoft/boost-game`

`Position` objects corresponding to a game provide the following fields and
methods:

## Encodings

*   `position.signature` is the position encoded as a single `BigInt`.  This
    encoding is meant to be used as a reasonably fast hash-table key.  (The
    position itself cannot be a hash-table key because ES6 does not support
    hash-by-value natively.)

*   `position.nextSignature` is equivalent to `position.nextTurn.signature` (see
    the description of `position.nextTurn` in the "Moves" subsection further
    below), but runs faster because it does not actually advance the turn.  It
    is mostly useful for checking candidate moves for repetitions.

*   `position.serialization` is the position serialized as a string.  A position
    can later be deserialized with `game.deserializePosition` as described
    earlier.

## Pieces

*   `position.getColorAndPieceType(x, y)` returns the color and piece type of
    the piece at the zero-based coordinates `x` and `y` as a two-element
    `Array`.  Colors are represented by the number of turns until the
    corresponding player will play (e.g., `0` for the player whose turn it is
    and `1` for the other player in a two-player game), and piece types are
    represented with the constants `game.dragon`, `game.pawn`, `game.knight`,
    and `game.tower` described earlier.  Dragon's colors are always `undefined`.
    If there is no piece at the given coordinates, both the color and piece type
    will be `undefined`.

*   `position.modified(x, y, color, pieceType)` returns a new position
    (`Position` objects are immutable) where the piece at the zero-based
    coordinates `x` and `y` has been replaced with a piece of the given color
    and piece type.  As above, the color should be given as the number of turns
    until the corresponding player moves next (e.g., `0` for the player whose
    turn it is and `1` for the other player in a two-player game), and piece
    types should be given as one of the constants `game.dragon`, `game.pawn`,
    `game.knight`, or `game.tower`, which are also described earlier.  As
    special cases, `color` should be `undefined` if `pieceType` is
    `game.dragon`, and a point can be cleared by passing `undefined` for both
    `color` and `pieceType`.

## Static Evaluation

*   `position.getStaticEvaluation(color)` is the static evaluation of the
    position from the perspective of the player who is to play in `color` turns
    (hence, the possible values for `color` are the same as the values returned
    by `position.getColorAndPieceType` or passed to `position.modified`).
    Higher static evaluation scores are more favorable for that player.  A score
    equal to `game.victory` means that the player to move next has already won.

556
557
558
559
560
561
*   `position.getCircleEvaluation(color)` is the contribution to the static
    evaluation for `color` from that player's progress on a dragon circle.  It
    ignores all other factors, even other player's progress on dragon circles.
    A score equal to `game.victory` means that the player has won by completing
    a dragon circle.

Brady James Garvin's avatar
Brady James Garvin committed
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
*   `position.inBookBonus` is the adjustment to make to a static evaluation when
    a player is in book (see `--ai-in-book` above).  This value is provided
    separately because the opening book, if any, is the engine's responsibility,
    and the `getStaticEvaluation` method only gives a bookless evaluation.

*   `position.live` is `true` if the game is still ongoing, `false` if any
    player has won.

## Moves

*   `position.children` is the list of positions that the current player can
    move to, not considering the repetition rule.  Note that it is the same
    player's turn in the children positions as in the parent position; a turn is
    not considered complete until the code uses `position.nextTurn`.

*   `position.getEncodedMoveTo(child)` returns an opaque representation of the
    move from `position` to `child`.  This method runs faster than `getMoveTo`,
    described below, but the move is not human-readable.

*   `position.getChildByEncodedMove(encodedMove)` returns the child reached by
    playing the move given by its opaque representation.

*   `position.getMoveTo(child)` returns the algebraic notation for the move from
    `position` to `child`.

*   `position.getChildByMove(move)` returns the child reached by playing the
    move given in algebraic notation.

*   `position.nextTurn` is the same as `position`, except that in
    `position.nextTurn` it is the next player's turn.  So, for example,
    `position.getChildByMove('a1a3').nextTurn` would be the position after the
    current player played the move `a1a3`.

## Side Statistics

The field `position.sides` is an array of `Side` objects, one for each player,
indexed by the number of turns until that player is to play (hence, the possible
values for the array index are the same as the values returned by
`position.getColorAndPieceType` or passed to `position.modified`).  The field
`position.dragons` is a `Side` object for the neutral dragons.  Each `Side`
object has the following fields:

*   `side.openingSignature` is the player's pieces encoded as a single `BigInt`,
    but without promotion information, so it treats pawns and knights
    identically.  This encoding is meant to be used as a reasonably fast
    hash-table key in the code for an opening book.  (The side itself cannot be
    a hash-table key because ES6 does not support hash-by-value natively.)

*   `side.pawnCount` is the number of pawns controlled by the player as a
    `BigInt`.  Dragons count as pawns for the dragon side.

*   `side.knightCount` is the number of knights controlled by the player as a
    `BigInt`.  This count is always zero for the dragon side.

*   `side.towerCount` is the number of towers controlled by the player as a
    `BigInt`.  This count is always zero for the dragon side.

*   `side.population` is the total number of mobile pieces (pawns and knights)
    controlled by the player as a `BigInt`.  Dragons count as pawns for the
    dragon side.

# Using `Controller` Objects from `@unlsoft/boost-engine`

When `@unlsoft/boost-game` is installed as a development dependency, it provides
two minified files, `…/node_modules/@unlsoft/boost-engine/dist/engine.js` and
`…/node_modules/@unlsoft/boost-engine/dist/engineThread.js` that implement the
engine's web workers.  These files should be included as-is in any app that
wants to use the engine; for a `create-react-app` app, the easiest approach is
to symlink them to the `public` folder.

For talking to these web workers, the default export from
`@unlsoft/boost-engine` is a `Controller` class, where `Controller` objects
provide the following methods:

*   `new Controller(engineURL, engineThreadURL, gameIdentifier, propertyHandler,
    moveHandler)` creates a controller for an engine whose web workers' source
    code is located at the given URLs and that will play the game identified by
    `gameIdentifier`.  Two callbacks must be provided:

    *   `propertyHandler` will be called with a property name and a value
        whenever the engine sends a description of itself (see the documentation
        for the `id` BEI message below).

645
    *   `moveHandler` will be called with four arguments whenever the engine
Brady James Garvin's avatar
Brady James Garvin committed
646
647
        makes a move (see the documentation for the `move` BEI message below):

648
649
        *   the engine's score for the position in decitempi,

Brady James Garvin's avatar
Brady James Garvin committed
650
651
652
653
654
        *   the chosen move in algebraic notation,

        *   a list of the moves the engine considers best, including the chosen
            move, also in algebraic notation, and

655
656
        *   a list of moves that the engine considers to be the opponent's
            threats, also in algebraic notation.
Brady James Garvin's avatar
Brady James Garvin committed
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673

*   `controller.setStrength(strength)` sets the engine's strength as close as
    possible to `strength` on a scale where `100` is the strength for giving a
    new player an instructive but winnable game, `1500` is the strength of the
    average experienced human player, and `2500` is the strength of a
    grandmaster.  At the moment, for performance reasons, the engine only
    supports strengths up to 2000.

*   `controller.setDepth(depth)` is an alternative to `controller.setStrength`
    that sets the engine's search depth as close as possible to `depth`.  At the
    moment, for performance reasons, the engine only supports depths up to 5
    ply.

*   `controller.setLine(position, taboo)` sends a position and an array of
    preceding positions (which are taboo under the repetition rule) to the
    engine.

674
675
676
677
*   `go(wantThreats)` tells the engine to choose a move to play in the last sent
    position.  The engine's reply will be sent to the `moveHandler` callback
    once the engine is done thinking.  If `wantThreats` is true, the engine will
    also report the opponent's threats it has identified.
Brady James Garvin's avatar
Brady James Garvin committed
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761

*   `stop(wantMove)` tells the engine stop thinking early.  If `wantMove` is
    `true`, the controller will still call `moveHandler` with the best move the
    engine found so far; otherwise that move will be discarded.

Under the hood, the `Controller` constructor creates associated web workers, and
its other methods communicate with these web workers using BEI, a protocol
described in the next section.

# The Boost Engine Interface (BEI) Protocol

BEI is a text-based protocol for communication between a controller (a program
that wants to incorporate a Boost-playing AI) and an engine (a Boost-playing
AI).  It is based on and simplified from the Arimaa Engine Interface (AEI),
which in turn is based on the Universal Chess Interface (UCI).

BEI is built on asynchronous bidirectional communication of short strings called
**messages** between the controller and engine.  For example, a controller might
send messages as lines of text to an engine's standard input and read messages
from the engine's standard output, or the controller and engine might exchange
BEI messages as string payloads in web worker messages.
(`@unlsoft/boost-engine` uses the latter approach.)

Generally the engine should not process later messages until it has finished
processing earlier ones.  The two exceptions are pondering (speculatively
searching ahead during an opponent's turn) and thinking (deciding what move to
make during the engine's own turn), long-running operations that should
effectively happen "in the background" and not prevent the engine from
responding to other communication.

## Controller-to-Engine Messages

The following messages may be sent by a controller to an engine:

*   `bei [value] [value] …` is sent to initiate communication and optionally to
    provide engine-specific startup arguments.  (It must be possible to
    configure an engine to take no startup arguments so that the engine can be
    used with an implementation-agnostic controller, but an engine may still opt
    to take arguments in other settings.)  The engine will reply with a
    `protocol` message, possibly some `id` messages, and then `beiok`.  Apart
    from `isready` messages, the controller must not send any other
    communication until it has confirmed that it is using a compatible protocol
    version and has received a `beiok`.

*   `isready` is sent to ping the engine and ensure that the engine has finished
    processing any previous messages.  The engine will reply with `readyok` once
    all previous messages have been handled.

*   `newgame [identifier]` is sent to start a new game with the given game
    identifier.  The engine will reply with `known` if it can play that game,
    `unknown` if it cannot.

*   `setoption [option] [value]` is sent to set the named engine option to the
    given value.  Currently there are only two supported option names:

    *   `strength` should be followed by a rating on a scale where `100` is the
        strength for giving a new player an instructive but winnable game,
        `1500` is the strength of the average experienced human player, and
        `2500` is the strength of a grandmaster.  If the engine strength is
        never set, the engine should default to its strongest setting; if an
        engine cannot play at the requested strength, it should set its strength
        as close as possible.

    *   `depth` should be followed by a search depth and is an alternative way
        to configure the engine's strength.  Again, if the engine's search depth
        is never set, the engine should default to its strongest setting; if an
        engine cannot search to the requested depth, it should set its search
        depth as close as possible.

*   `setline [serialization] [tabooSerialization] [tabooSerialization] …` is
    sent to tell the engine about a new board position, which is given by the
    first serialization, and all of the previous board positions that affect the
    repetition rule, which are give by the following serializations.  The
    serialization format is the same format as used by `position.serialization`
    from `@unlsoft/boost-game`.

*   `ponder [turns]` is sent to tell the engine that it will be playing after
    the given number of turns and that it may ponder in the background.  The
    `newgame`, `setline`, `go`, and `stop` messages all stop pondering.

*   `go` is sent to tell the engine that it should start thinking in the
    background about what move to play in the current position.  When it is done
    thinking, the engine will respond with `move` message reporting the best
    moves that it was able to find (or one move, a pass, if no real moves are
762
763
764
    possible because the game has already been won or lost).  Alternatively, `go
    wantThreats` has the same effect, except that it asks the engine to also
    respond with any opponent's threats it has identified.  The `newgame`,
Brady James Garvin's avatar
Brady James Garvin committed
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
    `setline`, `ponder`, `go`, and `stop` messages all stop any previous
    thinking and trigger a `move` message, even if the engine was not done
    considering the position.

*   `stop` is sent to tell the engine that it should stop any pondering or
    thinking.  If the engine is thinking, this will prompt it to reply with a
    `move` message.

*   `quit` is sent to tell the engine that no further messages will be sent and
    that it may exit.

## Engine-to-Controller Messages

The following messages may be sent by an engine to a controller:

*   `protocol [version]` is sent as the first message in response to a `bei`
    message to tell the controller what version of BEI the engine uses.  The
    version described here is `2.0.0`.

*   `id [property] [value]` is sent in response to a `bei` message to describe
    the engine to the controller.  Each property should be sent at most once.
    Three property names are supported:

    *   The value for the `name` property is the name of the engine.

    *   The value for the `author` property is the name of the engine's author
        (or the names of the engine's authors if there are more than one).

    *   The value for the `version` property is the version number of the
        engine.

*   `beiok` is sent to indicate the end of responses to a `bei` message.

*   `readyok` is sent to reply to an `isready` message.

*   `known` is sent to reply to a `newgame` message when the engine is able to
    load the specified game from its game library.

*   `unknown` is sent to reply to a `newgame` message when the engine is unable
    to load the specified game from its game library.

*   `move [score] [move] [move] …` is sent to report the best score and best
    moves the engine was able to find whenever the engine stops thinking.  The
    first move is the one chosen by the engine to play.  However, the engine
    should not assume that this move will actually be made; if it is, the engine
    will receive an appropriate `setline` message.  If no moves are possible
    because the game has already been won or lost, the engine must send a single
812
813
814
    placeholder move: a pass.  Alternatively, the message may take the form
    `move [score] [move] [move] … | [threat] [threat] …` if the engine is
    providing a list of opponent's threats that is has identified.
Brady James Garvin's avatar
Brady James Garvin committed
815
816

*   `log [text]` is sent to report a log message from the engine.