Instead of using Google Drive to store Nova-related material (e.g., presentations, design docs, etc.), let's put it in the Wiki repository.

This will allow people using tools like Obsidian to have access to everything in a single place.

Recommended Courses (UC Berkeley)

Not relevant.

Resources

• Missing implementation (fill this out)
• Automaton<State> implementation for zero_by::Session

Guidance on Methods

The Automaton<S> interface allows solvers to traverse game states based on a game's rules. Before you do anything, you should at least skim the docstrings on the Automaton<S> generic trait declaration. Doing this will let you understand what we are trying to do here, and why the semantics/abstractions around state transitions are the way they are.

Side note: In puzzles, we don't really care about player count, so you will not need to encode whose turn it is into state hashes. If we wanted to make this a multiplayer game, we would need to use the turn bitpacking utilities provided in crate::games::utils.

1. start

This function reads the configuration of the crossteaser game Session (please see this issue to see how it is initialized) and returns a hash of the starting state of the specified variant.

Since the variant information only defines the amount of empty slots together with the length and width of the game board, there is ambiguity on the following:

• Where the empty slots are
• How the pieces in the non-empty slots are oriented

It should not matter how you choose to disambiguate, as a strong solution should end up exploring all possibilities anyway (and all states within the same variant under our variant definition are reachable from all other states).

To help you do this, a Face enum is defined with the possible orientations of a puzzle piece. Other than that, it is completely up to you how you encode/decode the board into/from a State (which is just a 64-bit unsigned integer). It will take some creativity, but make sure you have some degree of performance in mind (a lot of the time we spend during solving will be doing hashing and unhashing). Since boards are essentially matrices, you can take a look at the nalgebra package (which you will need to use anyway) for performant linear algebra constructs.

However you end up hashing and unhashing, you should probably factor it out into functions of their own, because it is something that you will do in the next two methods as well.

(Chill) warning: This function is called only once per solve.

2. transition

This simply takes a state and returns a list of possible states reachable from that state. This is the most technical part of this implementation, but it introduces no new concepts. This can definitely be made super slow, so as a baseline, make sure that the runtime and memory usage of whichever algorithm you use is in O(LW), where L is the length of the board and W is the width.

If you are feeling extra, you can encode the location of the empty slots into the state hash to speed this up significantly for variants with considerably fewer empty slots than pieces. Clever use of the turn bitpacking utilities should allow you to do this. Note that the hash and unhash functions you (supposedly) made for the implementation of start should come in pretty handy here.

Warning: This function is called once for every state in the puzzle!

3. accepts

Unhash the input state and return true iff the puzzle is solved. This should be done in O(LW) time, where L is the length of the board and W is the width. Again, if you are feeling extra, encoding some statistics about the orientation of all pieces into the State hash should allow you to do this in constant time with relation to the board size (at no additional cost to the runtime of transition, because you can just update these statistics based on each type of move).

Warning: This function is also called once for every state in the puzzle!

Unhash and Hash Function Techniques

I know this is a lot, so here are three options of unhash and hash function signatures you can use, in order of increasing difficulty:

1. fn hash(representation: Vec<Vec<Face>>) -> State and fn unhash(state: State) -> Vec<Vec<Face>>: This is slow because you need to check every slot in the representation to get the information you need for transition and accepts, and because you need to do a ton of memory requests to the operating system (because of the nested Vec<_>).
2. Recommended: fn hash(representation: Vec<Face>, empty_locations: u64) -> State and fn unhash(state: State) -> (Vec<Face>, u64): This is (a lot) faster because it flattens the representation matrix into a single contiguous piece of memory, and because it keeps track of the locations of the empty slots in the board (meaning that transition can simply take a look at the pieces around them to know what moves can be made).
3. fn hash(representation: Vec<Face>, empty_locations: u64, face_counts: EfficientEncoding) -> State and an inverse unhash: This somehow adds the information of how many of each type of face is currently facing the player, which would make the accepts function a constant-time operation. I don't know exactly how to do this, so I will be super impressed if you do it.
4. Choose some combination of the above techniques based on the variant parameters for peak performance.

There is no need to do matrix multiplication in homogenous-utility games. This would leverage the fact that they only rely on the Automaton<State> interface, as Solvable<N> becomes useless. This is generally only useful for puzzles where all end states are equivalent (e.g., RubiksCube variations).

For weak solves, an instance of A* would yield solid performance for fast exploration.

Factor out copy-pasted code from mur, sur, etc., as much as possible.

Create a way to query single existing database tables through a restricted subset of SQL (ExQL?) which only supports streaming operators (excluding streaming cross products) and does not support nested queries.

This query language is intended to specify how to extract data from a bit-packed table (hence Ex(traction)QL) and into a file that can be consumed by a real SQL engine, which is why we can justify having a restricted set of operations.

Needed:

1. Compiler module (Target Table + String -> Query Plan / Operator List)
2. Operator module (Iterator + Operator -> Iterator)
3. Output module (Iterator + Format -> File)

Example

This might not make a lot of sense. Some central ideas are:

• Knowing that we can avoid full scans when we see KEY == LITERAL
• Renaming things at every necessary clause, and knowing that there is always a KEY

FROM (name)
WHERE ((KEY == attribute 2) && (attribute2 == 5))
GROUP BY ((attribute1) as KEY), ((attribute2) as KEY)
HAVING ((unique1 == 6) && (attribute3 == KEY))
SELECT ((unique1) as KEY), ((function(KEY)) as result2)
ORDER BY (-KEY)
LIMIT (2000)

Essential Clauses

Since we can offload a lot of utility to a real SQL engine, these clauses are the most important to implement.

1. FROM
2. LIMIT
3. WHERE
4. SELECT

Recommended Courses (UC Berkeley)

If you can't tell whether this is out of your scope, we recommend the following experience:

• CS 61B (minimum)
• CS 186
• CS 164
• CS 162

Resources

• Missing implementation (fill this out)
• Solvable<2> implementation for zero_by::Session
• Solvable<N> declaration
• nalgebra documentation

Guidance on Methods

These methods are mostly used in multiplayer games, so this will turn out to be incredibly straightforward/boilerplate. However, I encourage you to read the Solvable<N> declaration trait declaration so that what you do makes sense.

1. weights

Return a 1x1 stack-allocated SMatrix representing the identity matrix [ 1 ]. This essentially says that player 1 (the only player) values their own utility at a multiplier of 1.

2. utility

Return a 1-dimensional stack-allocated SVector representing [ 1 ]. This means that player 1 gets "1 utility point" out of finishing the game.

3. coalesce

Return a 1-dimensional stack-allocated SVector representing [ 1 ]. This intuitively means that at every state, player 1 is the player whose turn it is, and hence the player whose utility will be optimized when making the decision of which state to transition into.

Remark

Note that it literally does not matter what scalar values you put into these constructs. At a high level, this is because once a player is locked into playing crossteaser, they are pretty much bound to whatever "utility" the end states represent for them. In contrast, this would not be the case if different end states had different utility values for the player (e.g., if ending up with an empty slot in the corners was somehow worse than ending up with one in the middle), because there would be a difference in which one they try to get to (apart from remoteness, if that is an incentive for them).

Complete sections on the following topics:

• Working model of games
• Game categorization
• Available solving algorithms and their requirements
• Available interfaces and their semantics
• Project architecture
• In-depth development practices
  • Style guidelines
  • Documentation guidelines
  • Collaboration guidelines
  • Teamwork best practices
  • Maintainers
  • etc.
• Guides on how to do expected tasks:
  • Adding a game
  • Implementing a solver
  • Making a database
  • Adding a command to the CLI
  • Adding an interface
  • etc.

This should be done in the Wiki, which is in this repository (it is also a submodule of the main GamesmanNova repository).

Recommended Courses (UC Berkeley)

This only requires you to be familiar with how things are done in the project.

Alter the semantics of KVStore, adhere to the following:

trait KVStore {
  fn put(...);
  fn get(...) -> &[u8];
  fn del(...);
}

trait Table: KVStore {
  fn schema(...) -> Schema;
  fn size(...) -> u64;
  ...
}

trait Tabular<T: Table> {
  fn create_table(...) -> &T;
  fn select_table(...) -> &T;
  fn delete_table(...);
}

This is to facilitate eventually implementing Iterator<R: Record> on an implementation of Table to optimize full/wide scans.

Note: This not asking to make a complete web server; just to make this "callable" by a specific web server implementation.

Implement a UWAPI response option for the nova query command which fetches and prints some information stored in a database in a specific JSON format. This is dependent on the query system implementation, which will be used to fetch things from the database (and is a harder project).

This will allow UWAPI to fetch game information from nova in order to serve it to the GamesmanUni frontend (effectively making the games solved on nova playable with some additional frontend work).

Example

This project (including the --uwapi flag) should be hidden behind a "uwapi" feature flag.

$ nova query --uwapi "<position-string>"
{
  "position": "<position-string>",
  "children": [ ... ],
  ...
}

Recommended Courses (UC Berkeley)

If you can't tell whether this is out of your scope, we recommend the following experience:

• CS 61A (minimum)
• CS 61B

Would be useful in cases where alpha-beta pruning can yield stable strategies, but where full game tree exploration would be prohibitive to a strong solution.

With this, it would be necessary to consider the possibility of a database query miss as intended behavior, as opposed to it being a bug.

This would probably mean trickling down a solver_mode: SolverMode argument to the existing declaration of Game::solve: fn solve<G>(&G, solver_mode: SolverMode, database_mode: DBMode).

No storage of keys involved beyond index structure. This will involve creating an implementation of an in-memory cache and a B+ Tree, none of which necessarily need to be thread-safe.

Example

/// A page, which may be part of the B+ Tree or filled with records.
enum Page {
  Index([u8; PGSIZE]),
  Data([u8; PGSIZE)),
}

struct Database {
  tables: HashMap<&str, BPTree<&'a mut Cache, Page>>
  cache: Cache<Page>,
  ...
}

impl Tabular for Database { ... }
impl Table for BPTree<...> {...}
impl Drop for Database {...}
impl Persistent for Database { ... }
// ... 

Recommended Courses (UC Berkeley)

If you can't tell whether this is out of your scope, we recommend the following experience:

• CS 61B (minimum)
• CS 61C (minimum)
• CS 186
• CS 162

[WIP]

Resources

Here are some pointers to material that helps understand what we are trying to achieve:

• ByteByteGo video on LSM Trees.

Recommended Courses (UC Berkeley)

If you don't know whether this is within your scope, we recommend the following experience:

• CS 61B (minimum)
• CS 61C (minimum)
• CS 186 (minimum)
• CS 162

Resources

• Missing implementation (fill this out)
• Game implementation for zero_by::Session
• GameData definition
• NovaError::VariantMalformed
• Zero-by variant parsing module
• Guide on Result

Guidance on Methods

1. initialize

The initialize function is part of the Game trait, which defines some "administrative" functionality of all game implementations (stuff which isn't too algorithmically complex). It takes in an optional Variant (which is just a string) and returns an instance of the implementer (in our case, a crossteaser Session). This will be 95% percent of the work in this issue.

Variant Protocol

Our variant "protocol" (i.e. the way in which we encode game variants into a string) will allow us to define the size of the puzzle (in terms of its sidelengths) in addition to the number of free slots (spots without a movable piece). It should match the following regular expression: ^\d+x\d+\-\d+$. This means that all variants should look something like LxW-F, where L (length), W (width), and F (free) are positive integers. We will have a default variant of the real-life puzzle, which is a 3 by 3 square with one free slot (which means that the corresponding default Variant string should be 3x3-1).

Your Mission

Your job will be to fill out the missing implementation in a way similar to how it is implemented for the game zero-by. To do this, you will need to check for all the possible ways the user could mess up in specifying a variant, and return NovaError::VariantMalformeds containing useful (but concise) information about how they messed up, with reasonable granularity. For example, if the user passes in 4x6, they might want to see something like "Expected 3 integers but found 2.", not just "Variant could not be parsed.".

In the end, initialize should return an instance of crossteaser::Session containing the right data. Additionally, you will want to write the missing tests to make sure that the right variants work, and that the wrong ones don't. You should refer to the Zero-by variant parsing module to do this if you feel lost.

2. id

This returns an identifier unique to the game variant in string form. Note that it consumes a reference to self, meaning that by that point you will already have verified the data in initialize (because that's how you got self in the first place). Refer to how this is done in Zero-By if you are confused.

3. info

This should return a GameData object containing the information about the game. Please don't write string literals in function blocks; make sure to use the provided constants (again, refer to the implementation of Zero-By). Most of the work here will be to actually write something meaningful to describe the game. To this end, check out this website. If you use it verbatim, make sure to give the guy some credit.

4. solve

You shouldn't need to do anything here. This function just runs whichever solver can solve the caller on the caller. As a side note, notice that since callers are instances of Session, we can specify a solver for each game variant.

Create an ergonomic framework to benchmark and profile hot modules in the project. See the performance book for direction.

While this is not exactly difficult, it will take a tasteful implementation to make it useful. This includes thinking about module organization and CI integration (e.g., for regression testing).

Example

Below is an example of a benchmark function using an imaginary benchmarking framework module Benchmark:

fn solve_bench() -> Result<()> {
  let _time = Benchmark::record_time();
  solve(game);
  ...
}

Here, _time could implement Drop, and record the time difference between its instantiation and going out of scope and record it in a log file in the /dev directory for the sake of ergonomics.

This might not be the best example (since cargo bench already provides timing output), but there are plenty of useful things to try here.

Recommended Courses (UC Berkeley)

We recommend experience with testing frameworks and a mature taste in developer tooling, which university courses unfortunately do not usually teach. Beyond that:

• CS 61B (minimum)

See https://rust-lang.github.io/api-guidelines/documentation.html

In particular, note the importance of the following structure:

/// Quick one-sentence explanation.
///
/// In-depth explanation, possibly spanning multiple paragraphs...
///
/// # Example
///
/// ```no_run
/// let example = something();
/// ...
/// ```
///
/// # Errors
///
/// The exact circumstances under which this errors...
///
/// # Panics
///
/// The exact circumstances under which this panics...
pub fn something(cond: u32) -> Result<()> {
  if cond == 0 {
    panic!()
  } else if cond == 1 {
    Err(anyhow!("Error"))
  } else {
    Ok(())
  }
}

Recommended Courses (UC Berkeley)

This issue just requires the ability to read Rust and write grammatically correct and well-structured English.

• CS 61B (minimum)

Create a wrapper for a generic runtime backed by an opaque implementation of a parallel computation model, like MPI (multi-process), Tokio (async), or Rayon (multi-thread).

The internals of the Runtime can be implemented with Tokio. That is, a Tokio runtime will be encapsulated in a custom Runtime type, and the Tokio runtime will be the coordinator of the parallel implementation's workers. All Runtime calls should be synchronous and blocking, but internally, the Tokio runtime might make asynchronous / non-blocking calls to the underlying model.

In this sense, this is the first part of four things:

1. Synchronous runtime wrapper
2. Asynchronous generic coordinator
3. Bindings to parallel impls. (OpenMPI, rayon, more Tokio, etc.)
4. Thread-safe database implementation

Example

/// Available types of runtime. All of these assume a shared file system.
enum Runtime {
  ThreadPool { threads: u32 },
  Async { tasks: u32 },
  MPI { nodes: u32 },
}

/// Arguments to job functions.
struct Args<G, D> {
  game: &G,
  db: &mut D,
}

/// Solve the game.
fn solve<G: ..., D: ...>(game: &G, db: &mut D) -> Result<()> {
  let rt = Runtime::initialize(Runtime::MPI(30))?;
  rt.dashboard(Interface::Web)?;
  rt.route_logs(LOG_FILE)?;
  
  let mut graph = Graph::<JobID>::new(); // Partition solving jobs (JobID = Partition #)
  let mut set = Vec::<JobID>::new(); // Exploration jobs (JobID = State)
  
  starts = stochastic_exploration(game, db);
  graph = rt.independent(
    ExploreArgs { game, db },
    explore_job::<G, D>,
    jobs: set,
  )?;
  
  rt.dependent(
    SolveArgs { game, db },
    solve_job::<G, D>,
    jobs: graph,
  )?;
}

/// Explore the game tree.
fn explore_job<G: ..., D: ...>(args: Args<G, D>, target: JobID) -> Result<()> { ... }

/// Solve a single partition.
fn solve_job<G: ..., D: ...>(args: Args<G, D>, target: JobID) -> Result<()> { ... }

/// Sample random states in the game tree.
fn stochastic_exploration<G: ..., D: ...>(args: Args<G, D>) -> Result<()> { ... }

Recommended Courses (UC Berkeley)

If you can't tell whether this is out of your scope, we recommend the following experience:

• CS 61B (minimum)
• CS 61C (minimum)
• CS 162
• CS 267