- Start an online Alquerque session on http://omerkel.github.io/Alquerque/html5/src
- Android APK available for install
https://github.com/OMerkel/Alquerque/releases/tag/release_0.1
- requires minimum Android 4.4.2 (API-19)
- Runs in various browsers on
- desktop systems like BSDs, Linux, Win, MacOS and
- mobile platforms like Android, FirefoxOS, iOS.
Alquerque - 2 player abstract strategic perfect information traditional board game with computer AI option.
Alquerque is a board game demonstrator with computer AI using Monte-Carlo Tree Search (MCTS) with UCB (Upper Confidence Bounds) applied to trees (UCT in short). Alquerque is a medieval Spanish board game closely influenced and originated from the Middle East also known there as the game called Quirkat, Qirkat, or El-Quirkat. Etymological studies by Arie van der Stoep seem to strengthen the thesis for evidence of Roman influences. Assumption is that the Arabic qirq or qirqa is borrowed from the Latin word calculus (meaning a pebble or stone piece). If your sources distinguish among various Alquerque game variants then the most likely name for the implemented game found here might be "Alquerque de doze". The oldest written description might be by Abu al-Faraj al-Isfahani in his works of Book of Songs ("Kitab al-Aghani"). Although the rules were not described in there. An medieval source mentioning rules is the Libro de los juegos affiliated to (or at least commissioned by) Alfonso X el Sabio of León and Castile. Robert Charles Bell came up with modern rule proposals and enhancements later on. This Alquerque implementation has minor rule refinements neither covered by Alfonso X nor Robert Charles Bell. Still the final rule set is close to the suggestions made by R.C. Bell.
Keywords, Categories Monte-Carlo Tree Search (MCTS), Upper Confidence Bounds (UCB), UCB applied to trees (UCT), AI, 2-player board game, deterministic game with perfect information, JavaScript, ECMAScript, W3C WebWorker
This Alquerque is a board game using Monte-Carlo Tree Search (MCTS) with UCB (Upper Confidence Bounds) applied to trees (UCT in short) for the computer player AI. The board game is used for demonstration purposes of the UCT algorithm.
The game view exposes turn and move state directly on the board:
- A compact badge opposite the menu identifies the active player.
🧑and🤖distinguish human and AI players;Player ▼identifies the light side andPlayer ▲the dark side. A small spinner rotates to the left of the symbol. - Every pawn that can start a legal move has a light-green circular ring. The selected pawn uses a darker green ring painted above the other highlights. When the default anti-reversal rule blocks that pawn from returning to its previous square, a red X marks the forbidden square.
- The previous move remains visible in light blue: a dashed ring marks its empty source and a solid ring marks the pawn at its target.
- Pawn movement is a two-part soft jump. The pawn moves and grows toward the midpoint, then moves to the target while shrinking to its normal size.
- When the game ends, a translucent celebration panel immediately below the title bar congratulates the light or dark winner and states whether all opposing pawns were captured or the opponent had no legal move.
There are different rules available for Alquerque de doze. The default rules as implemented here are as follows. Mind that some parts of the rules might be altered through selected options.
Alquerque is a board game. The rectangular Alquerque board has fixed dimension of 5 times 5 positions horizontally and vertically. Positions on board are connected by a fixed line pattern showing potential paths of movement for players’ checkers. The checkers are placed on the positions (or points) of line intersections in the line pattern. There are two opposing players: one is controlling the light checkers and the other is controlling the dark checkers.
The twelve light checkers are placed on all positions of rows 1 and 2, and positions d3 and e3 initially. Thus the row 1 is referred to as being the base row of the player controlling the light checkers. The twelve dark checkers are placed on all positions of rows 4 and 5, and positions a3 and b3 initially. Thus the row 5 is referred to as being the base row of the player controlling the dark checkers.
Alquerque is played alternating players’ turns. The player controlling light checkers moves first. A player either
- must capture opponent’s pieces if possible or
- must perform a normal non-capturing move otherwise.
Passing a turn is not allowed.
Movement of checkers is performed strictly along the lines of the board onto adjacent free positions.
A light checker can not move from it's position to positions on rows with lower numbers. A dark checker can not move from it's position to positions on rows with higher numbers. Thus neither a light nor a dark checker can move backwards in direction of the player's own base row.
By default, a checker must not reverse its own previous non-capturing move: it cannot move straight back to the point it came from. This restriction is tracked separately for every checker and avoids draw situations caused by repeatedly taking back moves. The option Inverting each pieces' own last move is... allowed disables this restriction. It does not apply to captures.
A checker that reached the opponent's base row can not be moved any longer but only capture opponent's checkers if possible. Anyway the checker is allowed to perform non-capturing moves again, too, if after the capture it is not positioned on the opponent's base row any longer.
Captures are compulsory. If capturing is possible on a player’s turn then the player must perform a capturing move. A capture can be performed in any straight direction indicated by the line pattern of the board (even in direction of own base row).
An opponent's checker on an adjacent position along a line of an own checker is captured by jumping over it in straight line onto an adjacent free position along the line. Jumping to perform captures is done in straight line without any change of direction. Checkers captured leave the board and do not return. By each jump exactly one single opponent's checker is jumped over and thus captured at a time. Checkers can not jump over or capture checkers of own color. Captures can be done and are mandatory if available any time on own turn after the game has started.
In a player's turn multiple consecutive captures performed with the same own checker are allowed and compulsory. The player must continue to capture in the possible multiple consecutive capture until no additional capture is possible. It is not necessary to select the longest possible path to capture the maximum opponent’s pieces. On alternative paths the player may decide freely on which one to continue capturing. After each single straight line jump if performing multiple consecutive captures the direction of jumps may be changed although reverse direction change is not allowed. A captured checker is removed from game play instantly while being jumped. Thus it can not be reused to be jumped again in a multiple capture move.
Checkers can not be stacked by moving or jumping on top of the other.
A player wins by either capturing all opponent's checkers or if the opponent can not perform any legal move. With given rules a tie or draw game is only possible if the option Inverting each pieces' own last move is... allowed is chosen. Per default inverting each pieces' own last move is strictly forbidden.
- Guillaume Maurice Jean-Bernard Chaslot, "Monte-Carlo Tree Search", PHD Proefschrift, Universiteit Maastricht, NL, 2010.
- Guillaume Chaslot, Sander Bakkes, Istvan Szita and Pieter Spronck, "Monte-Carlo Tree Search: A New Framework for Game AI", in Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, Stanford, California, 2008. Published by The AAAI Press, Menlo Park, California.
- Alfonso X el Sabio, "Libro de los Juegos" or "Libros del Axedrez, Dados et
Tablas", 98 double-sided pages, available at the monastery library Real Sitio
de San Lorenzo del Escorial, Madrid, Spain, written from 1251 to 1282.
- Transcript/Translation into English by Sonja Musser Golladay
- Robert Charles Bell, "Board and Table Games from Many Civilizations", Volume 1, Dover Publications, US, 1979.
- Sonja Musser Golladay, "Los libros de acedrex dados e tablas: Historical, Artistic and Metaphysical Dimensions of Alfonso X's Book of Games", PhD Dissertation, 591pp., The University of Arizona, US, 2007.
- Arie van der Stoep, "The origin of morris and draughts by etymology", in Board Game Studies Journal, Issue 9, 2015, ISSN 2183-3311, http://bgsj.ludus-opuscula.org, published by Associação Ludus, Lisboa, Portugal, 2015.
The application itself ships no third party runtime code. It is plain HTML5, CSS and ECMAScript modules and runs from any static web server.
Development dependencies (not shipped, see package.json):
- Vitest and @vitest/coverage-v8: unit tests and coverage
- jsdom: DOM for the unit tests of the view modules
- Playwright: end to end tests in a real browser
- Biome: linter and formatter for JavaScript, CSS, HTML and JSON
- markdownlint-cli2: linter for the documentation
Open http://omerkel.github.io/Alquerque/html5/src, or serve the sources locally and open http://localhost:4173/index.html:
Mind: The port number of your local server is a matter of your environment settings.
npm run serveThe application needs no build step. html5/src is what gets deployed;
any static web server will do.
Node.js 20 or newer. Install the development tooling once, and the browser used by the end to end tests:
npm install
npx playwright install chromium| Command | What it does |
|---|---|
npm run lint |
Biome (JavaScript, CSS, HTML, JSON) and markdownlint over the whole workspace |
npm run lint:code |
Biome only, warnings treated as errors |
npm run lint:md |
markdownlint only |
npm run lint:code:fix |
applies Biome's formatting and safe fixes |
npm run lint:md:fix |
applies markdownlint's automatic fixes |
npm test |
unit tests (Vitest, jsdom for the view modules) |
npm run test:watch |
unit tests in watch mode |
npm run coverage |
unit tests plus the 96 % statement, branch, function and line gate |
npm run test:e2e |
end to end tests in Chromium (Playwright, starts the server itself) |
npm run ci |
lint, coverage and end to end tests in the order used by the build server |
The current automated baseline contains 198 unit tests and 10 Chromium end to end tests. Coverage thresholds are 96 % for statements, branches, functions and lines.
A single unit test file, or a single test by name:
npx vitest run tests/unit/board.test.js
npx vitest run -t 'makes captures compulsory'
npx playwright test --headed -g 'plays a human move'Reports are written to coverage/ (open coverage/index.html) and to
playwright-report/; both are ignored by Git.
Lint findings are fixed in the source, never suppressed: there is no
biome-ignore and no markdownlint-disable anywhere in the workspace.
Requirements and their traceability to these tests are listed in doc/requirements.md.
Source layout under html5/src:
| Path | Content |
|---|---|
index.html, css/ |
markup and the hand written jQuery Mobile look-alike theme |
js/core/ |
game rules and state as pure functions |
js/engine/ |
UCT/MCTS and the random baseline engine |
js/worker/ |
the Web Worker owning the game session |
js/ui/ |
bootstrap, board rendering, input, navigation, options |
Design and rationale: doc/requirements.md, doc/software_architecture.md, doc/engine_mcts_ucb.md.
- Association for the Advancement of Artificial Intelligence, http://www.aaai.org
- HTML Living Standard, Web Workers, https://html.spec.whatwg.org
- Standard ECMA-262 ECMAScript Language Specification, http://www.ecma-international.org/publications/standards/Ecma-262.htm
- Alphonso X - Book of Games - A Game Researcher's Resource, http://historicgames.com/alphonso
- Board Game Studies Journal, http://bgsj.ludus-opuscula.org
|
Oliver Merkel, |
 |
All logos, brands and trademarks mentioned belong to their respective owners.