If you are reading this file, you are interested or have been forced to work on this program. By skimming through this file, you are supposed to be given a few pointers to make your life easier.
After having finished the remaining document, you will know:
- What problem this program attempts to solve
- What technologies are used (and why)
- How the server is structured (and why)
- How to use the server (and how to configure it)
Please keep in mind to update this file if you make any larger changes. That makes sure that future contributors have a reliable reference document.
It is assumed you have basic knowledge of the KGP protocol. If this is not the case, please consult the “spec” directory in the root directory of this repository. Some knowledge of the rules of Kalah are also presumed.
A KGP server based on freeplay is flexible in the way it presents a
client with state commands. Go-kgp provides two separate modes:
- A “public, practice server”, a web-facing server that accepts
(optionally identified) client connections to play games against
one-another and bots.
Additionally the server can be run in a one-shot mode that would render all historical games as separate files that can be viewed offline.
- A “closed, tournament program”, a program that executes agent programs using Docker containers, coordinating a multi-stage tournament between them.
(In the context of the AI1 lecture, these are used before and after the submissions deadline for student programs. The first gives them a chance to test their agents against one another and against bots, the second evaluates their performance objectively.)
The server is written in Go, version 1.16. The source code has been formatted using gofumpt, and staticcheck has been consistently used to avoid common issues. It is recommended to have these issues part of your workflow. Both can be integrated into the gopls LSP Server.
The Server intentionally relies on the libraries from the Go Standard Library, as far as possible. The only exceptions are :
- github.com/mattn/go-sqlite3
- A SQLite 3 library used to store all data that has to be stored.
- nhooyr.io/websocket
- A WebSocket library used to implement communication over HTTP.
- github.com/BurntSushi/toml
- A TOML configuration file parser, used to load and store configuration files.
The decisions to use SQLite 3, as compared to MariaDB or PostgreSQL, was made to make deployment simpler and because it is entierly sufficient for the use-case of this server. Keep in mind that
“SQLite does not compete with client/server databases. SQLite competes with
fopen().”
The program is structured into a number of mostly de-coupled modules. This section describes their intent and important concepts. If you are just reading into the source code for the first time, it is recommended to proceed in the order given here.
One of the motivations for de-coupling modules is that we can re-use
them for various programmes. E.g. ./cmd/practice will use and
initialise the right modules to have a public practice server, while
./cmd/competition will differ in what and how is used.
This module defines the shared data structures used in other modules
and to exchange data between modules (e.g. to allow loading data from
the database in the go-kgp/db module and to display it on the
website in the go-kgp/web module). The relevant types are:
Side, abool-like type. Used to indicate the two possible sides of a board (NorthandSouth).Outcome, auint8-like type. Used to indicate possible outcomes of a match:WIN- The southern player won
LOSS- The southern player lost
DRAW- Both players played to a draw
State, auint8-like type. Used to indicate game statesONGOING- The game hasn’t finished
NORTH_WON- The northern player won.
SOUTH_WON- The southern player won.
NORTH_RESIGNED- The northern player resigned.
SOUTH_RESIGNED- The southern player resigned.
UNDECIDED- The game was played to a draw.
ABORTED- The game was aborted and couldn’t be finished.
Board, a Kalah board without any players. We implement the conventional rules and checks on this object.Agent, an interface to describe an agent that can make moves. The most important method isRequestthat determines what move an agent makes given aBoard.User, a complex structure to represent users. Users differ from agents in that they have metadata which is stored in the database and can be displayed on the website. An agent can be asked to give a user.Game, a complex structure to represent games. games are played on aBoardbetween twoAgents.Move, a complex structure to represent a move. A move is made by an agent and has metadata like a timestamp (Stamp), aGameandAgent.
Beside the root module, this module (excluding submodules) contains a a number of general utilities and abstractions:
conf.go- Management of the configuration file and flags.
graph.go- Generic code to generate a dominance graph using Graphviz.
state.go- Service management and program state, as described below.
The general structure of go-kgp is that the modules introduced in
the following sections provide service managers as specified by the
conf.Manager
interface, importantly consisting of a Start and Shutdown method.
The manager is also extended by two other specialised interfaces
(conf.Scheduler, conf.Database) that mainly exist to avoid
cyclical dependencies.
The program state is passed through all the managers to coordinate shared execution contexts and allow for the managers to be shutdown orderly (e.g. on receiving a shutdown signal from the operating system).
The sub-directories of go-kgp/cmd store the source code of all
concrete executable libraries that connect all the modules into the
programmes mentioned in Problem Statement.
The database module is responsible for storing and retrieving all persistent data. As mentioned above it is based on SQLite, and uses a few pragmas to accelerate the performance and reliability.
The module maintains separate connections for reading and writing, so that the two do not interfere under high load.
Queries are stored in .sql files in the same directory and are
injected into the execeutables using Go 1.16+’s embed package. These
make use of expresison parameters and prepared statements to avoid SQL
injections and also further increase efficiency.
Doe that as the database will periodically remove old games, the database is also automatically optimised. If this is not sufficient, all executable should handle a SIGUSR1 signal that would rebuild the database using the VACUUM command.
The game logic for a Game is given in the function =Play=. To
accelerate games it will skip trivial moves (where an agent has only
one legal choice) and end as soon as one player has collected more
than half of the available stones, as the other side cannot win
anymore from that point on. These measures are taken to accelerate
the game-play.
The Play function intentionally does not care what agents kind of
agents are playing. This is deferred to the Request method of the
Agent interface, so that each implementation can decide further
details.
This module is responsible for three related issues:
- Accepting TCP connections and starting games (
manage.go) - Implementing the Agent interface for network clients (
client.go, most importantly see =Client.Request=) - Parsing the KGP protocol and responding correctly (
proto.go,verify.go)
The web module manages the web interface and accepts games via
WebSocket.
Files ending in .tmpl use the html/template template-language to
generate HTML pages. Most dynamic pages (installed in =web.Start=,
using functions from routes.go) are just responsible for connecting
information from the Database to these templates.
Note that the templates make use of the ability to define custom
functions in Go. These are found in web.go, and include the SVG
game rendering code.
The main interface of this module is Bot, an extension of Agent
interface by a IsBot method. This interface is currently only
implemented by a MinMax client that several schedulers use.
The MinMax agents have two parameters, search-depth and “accuracy”. Latter describes a chance that a agent will “accidentally” make a random move. If this chance is 100% we get the =random= agent.
Note that the MinMax agents (see =Request=) are never interrupted while computing a move. This gives them an advantage over an equivalent agent.ppp
As MinMax agents have no dynamic state, there is no issue in having them play multiple games at the same time.
The cmd.Scheduler interface is implemented in this Module. These are either indefinite (with no apriori, upper bound on how many games are scheduled) or finite. Finite schedulers can be composed and used to filter agents through multiple stages of a tournament.
- FIFO
- This indefinite scheduler is used by the web interface to match
incoming agents with others or if none are available, bots.
The complication of this scheduler derives from the need to find a balance between separate concerns:
- Decrease the latency between the initial connection and the first game.
- Maximise the number of games that agents play against real agents and not bots.
- Give agents a chance to a quit between games, to avoid “aborted game” messages in the public log (Soft-priority).
Points 1. and 2. stand in contention with one another since as the latency is reduced, the chance of having two real agents waiting to be paired also shrinks. But if we wait for two agents to appear in the waiting-queue (and do not make use of bots), then a agent may wait too long.
The middle-way implemented by FIFO is to have new games start every n seconds (starting from a full minute) so that friends can coordinate when to connect to the server, at which point all agents will be matched against one another in pairs of two, the possible remaining agent will play against a bot.
- NoOp
- An indefinite scheduler that rejects all game requests.
- Sanity
- A finite scheduler that takes a list of agents that all have to play against a random agent and win to pass.
- Round-Robin
- A finite scheduler, Used in tournament situations to
have each agent play at least one game on each side of the Kalah
board against one another.
An agent passes a Round-Robin scheduler if it does not loose more than half the games.
- Combo
- A composition of composable, finite schedulers that are run through in sequence. A composable scheduler (such as “Sanity” and “Round-Robin”) most be able to accept a set of agents to start with and produce a set of agents that passed. Additionally it has to be able to render a report in troff + ms syntax.
The combo scheduler extends the notion of a agent to that of a “controlled agent”, that is to say an agent that the program has access to and can start or terminate. This notion is formalised in the “go-kgp/sched/isol” sub-module and implemented for Docker images.
You should be able to build the using Go toolchain with cgo (i.e. a standard C compiler like GCC + Glibc) and SQLite 3 libraries. On GNU/Linux systems these should all be available or pre-installed by your local package manager.
$ go run ./cmd/practice
Optionally you might also want to have Graphviz (specifically the
dot executable) installed to generate a dominance graph.
Invoke the above command with -help to generate a overview of flags
that can be used to modify the behaviour.
The accompanying =Dockerfile= provides an alternative environment to start the practice server along with all the necessary dependencies.
To organise a tournament, you should have a number of agents that can
be compiled into docker containers. It is best to have the source
code of all agents collected in a single directory, where each
sub-directory contains a Dockerfile to build the agent:
./agents/ ./agents/agent1/Dockerfile ./agents/agent1/agent.py ./agents/agent2/Dockerfile ./agents/agent2/Agent.java ./agents/agent3/Dockerfile ./agents/agent3/AGENT.COBOL ...
The names of these directories are not important. Given this structure, you should be able to invoke the tournament program as follows:
$ go run ./cmd/tournament -auto -dir agents/
This will build a Docker image for each sub-directory, test if it can
connect to a server and then proceed to run the entire tournament
with all the functioning clients. The information the clients need to
connect to the server are passed through the environmental variables
KGP_HOST (for the hostname) and KGP_PORT (for the TCP port).
The results of each game will be written into the default database.
It might be add a -db flag to avoid re-using the database multiple
times:
$ go run ./cmd/tournament -db "$(date +%s).db" -auto -dir agents/
The best way to represent the results of the tournament is by having
it rendered in a report. The tournament server can prepare this
automatically using GNU roff (groff) that all distributions should
make available. The configuration option game.closed.result can be
set to indicate what file you would like to use for the output. By
default it will attempt to render a PDF file in the current working
directory. Other legal extensions include .ps (Postscript), .html
(HTML) and .txt (a plain text file). If not set/unset, the program
will output the text output directly to the standard output.