Rosenberg

Rosenberg is an engine for the board game Nova Luna written in Java. Nova Luna is played by two to four players with the goal of placing square tiles onto the table and thereby connecting them with other tiles. The aim of the game is to complete as many tasks, that are given by the tiles, as possible. For further explanation of the game refer to the playing instructions of Nova Luna. Note that the original game was slightly modified for this project as described in one of the following sections.

This program is both an implementation of the game Nova Luna and an analysis tool used to evaluate game states. Typical applications of this engine would include: playing and undoing moves, uniformly sampling random moves or acting as a computer opponent inside another application. Using the various commands and their arguments this program could play the role of a weak opponent, a very strong opponent or an opponent that always does random moves.

Overview

The engine is driven by a current game state that is always present. Text commands are used to update and analyse the current game state. At program start-up the engine is initialized with a non-beginner game between the two players white and black. The tiles used for this initial game have been brought into a random permutation and black is allowed to play the first move. This initial game is equivalent to the command setup false ws, as is explained in the commands section. In order to warm up the engine (load any lazy-loaded classes and initialize static fields) a very brief evaluation is performed on the initial game state before the engine is finally ready to accept and process commands.

At least two and at most four players are needed per game, as is required by the rules of the game. Using for example the command setup false b does allow for a game with only one player to be set up and analyzed, however this is not equivalent to the solo game mode that is described by the official Nova Luna rules and is not officially supported by this engine.

Features

Rosenberg provides the following features that mainly result in strong and efficient game evaluations:

• Monto Carlo Tree Search: MCTS is used to analysis game states by evaluating possible future outcomes in a tree structure. Instead of relying purely on random rollouts, rollouts are driven by strong heuristics that are used to randomly sample legal moves.
• Multi Threading: An arbitrary amount of threads can work on and contribute to the same Monte Carlo search tree, thereby analysing the same game state in parallel. By default the amount of threads will be equal to twice the number of (logical) processor cores.
• Evaluation caches: Any analysis of a game state (as part of MCTS) is stored and used again in later evaluation in order to quickly accelerated the analysis of game states seen before. This is particularly useful when analysing the same game state multiple times, when analysing a child game state of an already evaluated state or when the same game state appears twice in the Monte Carlo search tree. At default the cache is around 64 megabytes large.
• Uniformly sampled random moves: For any given game state, that is not a terminal game state, a random legal move can be sampled, such that the resulting probability distribution is a uniform distribution over all legal game moves of the given game state. In addition, this is done without generating all legal moves.
• Fast and efficient game implementation: The backbone of the engine consists of a very fast and efficient game implementation that, for example, allows for doing and undoing moves in O(1) time complexity. This is particularly crucial for doing a lot of rollouts as part of the MCTS.
• and much more...

Limiting Engine Strength

If the engine is acting as a bot that plays random moves only, via the randommove or playrandommove command, then the engine strength is independent of the hardware the engine is running on. If however the engine is acting as an intelligent agent and moves are requested using the evaluate command then the evaluation restrictions need to be carefully selected in order to achieve the desired, consistent engine strength.

If the engine is supposed to play at a consistent strength level, consider limiting either the evaluation tree size or tree depth (or both) and set the max. evaluation time to infinite, i.e. unrestricted time. This will result in equally strong moves no matter the hardware.

If the engine is supposed to play at its best, use evaluate <time> to only limit the maximum evaluation time. This way, there won't be any restrictions put onto the evaluation tree and the engine will aim for maximizing move strength given its time and hardware.

Note: Even if the engine is set up to play at a consistent strength, as described above, the strength may still vary due to the random nature of the MCTS algorithm but also due to the evaluation cache. If previous evaluations have filled up the evaluation cache with helpful game state analysis then the engine strength might go up. To mitigate this effect restart the engine after each and every game and make sure to only run evaluation commands if the engine is supposed to play its next move.

Also note: If the engine is supposed to play at its best capabilities and is allowed to continue thinking while its opponent is pondering on what move to play, consider using evaluate infinite to let the engine deepen its understanding of the current game state, by filling up the evaluation cache, thereby allowing it to play even more strongly on its next moves. Once the opponent has decided on their move, and it is our turn to move again, then the engine's intermediate game evaluation can be stopped immediately using the stop command, after which the engine can continue analysing the new game state in order to play its next move.

If the engine is playing its moves through the evaluate command, the move that the engine wants to be played is being output as best move <move> as part of the evaluation results. Additional evaluation results, for example the win probability might also be of interest and might be displayed to the user. However, keep in mind that the engine's probability of winning is purely based on the engine's strength. With higher engine strength, and therefore stronger evaluation, the probability of winning will come closer to the actual score of the game state, in the sense that the probability of winning will converge to either 0 or 1 if an optimally playing bot would either lose or win against itself by playing from that game state.

Commands

The engine always runs as its own process and therefore any communication with other programs is done using text commands that are send using the standard input of the process. Outputs of the engine are also always in the form of text messages that are send via the output process channel or the error process channel.

A list of all available commands and additional information is given by the following two tables.

⚠️ Warning: Executing illegal actions like playing an illegal move or evaluating a terminated game will result in undefined behaviour and might lead to a program crash.

Also note that the engine will only begin processing commands after it has readied up. The engine will signal that it is ready by sending a brief welcome message consisting of the engine's logo, name and version. For evaluation commands in particular the evaluation time only starts ticking after the engine has readied up.

Name	Aliases	Description
setup	su	Initializes the game by setting up a starting game state of Nova Luna. The game is to be played by two to four players using exactly 68 tiles. If requested a beginner variant will be set up (fewer starting tokens per player). The first player provided is placed onto the game board first, then the second player and so on. The provided ordering of the 68 tiles will determine the initial draw pile. The first tile will be placed at the bottom of the draw pile, the next tile will be placed on top of the first and so on. From this initial draw pile 11 cards will be taken one by one and placed onto the next empty slot on the wheel starting with the slot right next to the moon piece and going in clockwise order. At the start of the game all slots are filled with a tile or the moon piece.
play	p	Plays one or more given moves on the current game state, thereby updating the current game.
playrandommove	pr	Samples a random legal move of the current game state and performs that move.
playstrongmove	ps	Performs a strong move on the current game state. The strong move is chosen by a combination of heuristics. Some randomness is still applied however to spread the variance of selected moves.
playbestmove	pb	Executes an evaluation of the current game state using default evaluation parameters (1 second as max. evaluation time, unrestricted tree size and depth, and two threads per logical processor core) and performs the best move found on the current game state.
undo	u	Undoes the last move that was performed on the current game state, thereby updating the current game.
redo	r	Redoes the last move that was undone on the current game state, thereby updating the current game.
evaluate	e, eval	Evaluates the current game using the provided time and tree constraints and prints out the evaluation results. Note that the engine will use up all given evaluation resources except when the outcome of the game is clear without a doubt (this is often the case during the end of the game). Please note that any restrictions put onto the evaluation, meaning both time and evaluation tree restrictions, might be ignored on very rare occasions. Also note, for example during unrestricted evaluations, in order to deal with size restrictions on the JVM heap the Monte Carlo Search Tree might be cleaned up and replaced with a new tree. However this process does not lose meaningfull evaluation knowledge due to evaluation caching. In the case of new search trees being created during evaluation, the tree size is considered to be the sum over all tree sizes and the tree depth is considered to be the maximum of all tree depths.
cache	c, evalcache, ec	Displays some statistics about the analysis cache used during evaluation.
randommove	rm	Provides a random legal move of the current game state. The random move is sampled in such a way that the resulting probability distribution represents a uniform distribution over all legal moves of the game state.
game	g, overview, o, view	Prints an overview over the current game state including all gameplay relevant information.
gamehash	gh, hash, h	Prints the hash of the currently set up game state.
playertomove	p2m	Provides the player that is allowed to move next.
movelegal	ml, legal	Determines whether a given move is a legal move of the current game state.
stop	s	Stops the currently running game evaluation immediately.
quit	q, exit	Terminates the program.
information	info, i, version, v, author, a	Displays some general information about the engine.
benchmark	b, bench	Performs multiple benchmarks to evaluate both the engine and the hardware that it is being run on.

In addition, the second table describes how to properly use the commands described above:

Name	Usages	Examples	Output
setup	setup <beginner> <players>, setup <beginner> <players> <tiles>	setup false ws	<confirmation>
play	play <move> [move] ...	play false 1 1 -1	<confirmation>
playrandommove	playrandommove	playrandommove	<confirmation>
playstrongmove	playstrongmove	playstrongmove	<confirmation>
playbestmove	playbestmove	playbestmove	<confirmation>
undo	undo	undo	<confirmation>
redo	redo	redo	<confirmation>
evaluate	evaluate, evaluate <time>, evaluate <time> <tree_size>, evaluate <time> <tree_size> <tree_depth>, evaluate <time> <tree_size> <tree_depth> <threads>	evaluate 5000	<evaluation_results>
cache	cache	cache	<evaluation_cache>
randommove	randommove	randommove	<move>
game	game	game	<game>
gamehash	gamehash	gamehash	<game_hash>
playertomove	playertomove	playertomove	<player>
movelegal	movelegal <move>	movelegal true 0 0 0	<move_legal>
stop	stop	stop	<confirmation>
quit	quit	quit	<confirmation>
information	information	information	<engine_info>
benchmark	benchmark	benchmark	<benchmark_results>

Command data structures

The command protocol uses some predefined data formats that are being used in both communication directions and are explained below.

Identifier	Description
<move>	One move of Nova Luna
<move_legal>	Whether a move is legal
<evaluation_results>	List of results of an evaluation
<evaluation_cache>	Some statistics about the evaluation cache
<benchmark_results>	Results of a performed benchmark
<game>	A game state of Nova Luna
<game_hash>	A hashed game state of Nova Luna
<player>	A player identified by the first character of their player color
<players>	A list of players identified by the first character of their player colors
<tiles>	A list of tiles identified by their ids and separated using spaces
<beginner>	Whether the game should start in beginner mode
<time>	An amount of time in milliseconds or the phrase infinite indicating unlimited evaluation time
<tree_size>	The number of nodes of an evaluation tree or the phrase infinite indicating unlimited tree size
<tree_depth>	The maximum depth of an evaluation tree or the phrase infinite indicating unlimited tree depth
<threads>	An amount of threads
<engine_info>	Some general information about the engine
<confirmation>	A non specific confirmation that is used to confirm the effects of a command

The data structures used expect the following format and data types:

Identifier	Format	Data types
<move>	[refill_wheel] [next_remaining_card_index] [card_position_x] [card_position_y]	[boolean] [int from 0 to 2] [int] [int]
<move_legal>	[move_legal]	[boolean]
<evaluation_results>	-	-
<evaluation_cache>	-	-
<benchmark_results>	-	-
<game>	-	-
<game_hash>	[game_hash]	[long]
<player>	[player_character]	[char from 'b', 'o', 'w' and 's']
<players>	[first_player_character][second_player_character] ...	[char from 'b', 'o', 'w' and 's'] ...
<tiles>	[first_tile_id] [second_tile] ...	[int from 0 to 67] ...
<beginner>	[beginner]	[boolean]
<time>	[time]	[long greater than or equal to 0 or the string 'infinite']
<tree_size>	[tree_size]	[int greater than or equal to 2 or the string 'infinite']
<tree_depth>	[tree_depth]	[int greater than or equal to 2 or the string 'infinite']
<threads>	[threads]	[int greater than or equal to 1]
<engine_info>	-	-
<confirmation>	-	-

Game colors

The colors of players and tiles are identified by one letter strings using the following convention:

Identifier	Color
b	blue
c	cyan
o	orange
y	yellow
w	white
s	black

The letter 's' is used to identify the color black since the german word for black starts with an "s". Note that 'b' is already used by the color blue.

Updated Nova Luna rules

This engine relies on a variant of Nova Luna that follows the standard rulebook except for the following changes:

• Only one draw pile: Instead of allowing for an arbitrary amount of draw piles, as is stated in the original rules, all remaining tiles will be put into one big draw pile.
• Non-hidden draw pile: The entire single draw pile is accessible to all players, meaning that everyone can always see all remaining cards that remain to be drawn as well as the permutation that they are in. Seeing as the draw pile was the only information hidden away from the players, this variation results in a perfect information game which is especially useful for exact game analysis.
• Automatic task completion: Instead of leaving the player the choice of whether to complete tasks, tasks that can be completed will always be completed automatically by the game and tokens will automatically be taken from the respective player. Seeing as not completing tasks is never beneficial, even in the original game, this rule change will not have much of an effect.

Download

Prebuild executables of this project are available for download on the release page of this project. You may either use the following command inside your terminal:

java -XX:MaxRAMPercentage=75.0 -Xms1g -XX:CompileThreshold=100 -XX:+TieredCompilation -XX:TieredStopAtLevel=4 -XX:+UseNUMA -XX:+UseCompressedOops -server -jar rosenberg-<release_version>.jar

... or run the start.bat file, that is provided with each release, to start the engine.

Note that running this project requires you to have a Java runtime installed on your machine that supports at least Java 17. To achieve the best performance consider using the latest version of the Azul Platform Prime Java runtime environment.

How to build

If you wish to build the project yourself you may follow this guide:

• clone this repository onto your local machine
• use either IntelliJ IDEA or any other IDE of your choice to open the project
• set up the Gradle project using a JDK of your choice that supports the required Java version
• optional: make any changes to the project
• run the Gradle > Build task in order to build the project or run the main method inside the Main class directly to build and run the project automatically