Clairvoyant

Adversarial Search Documentation

This documentation refers to the Adversarial Search problem.

Your script for the algorithm must evaluate to a function satisfying the following criteria:

  • It shall have an arity of 2, the first argument is the base Solver class and the second is a game instance.
  • It shall return an instance of a Solver object extending the base Solver class.
  • The Solver object shall implement the following functions:

Your script for the case must evaluate to a function satisfying the following criteria:

  • It shall have an arity of 2, the first argument is the base Game class, and the second is the base Position class.
  • It shall return an instance of a Game object extending the base Game class.
  • The Game object shall implement the following functions:
    • A getInitialPosition() function, which returns a Position object.
    • A getActions(position) function, which takes a Position object and returns an array of Action objects.
    • A getResult(position, action) function, which takes a Position object and an Action object, and returns a new Position object which results from taken the given action in the given position.
  • The Position object shall extend the base Position class and implement the following functions:
    • A getId() function which returns a unique string for this position.
    • A render(context) function which takes a 2D canvas rendering context which is 500 by 1000 pixels. It can be used to graphically draw the position onto the canvas.
    • An isTerminal() function, which returns true if no actions can be taken from the position, and false otherwise.
    • A getScore() function, which returns a value from -1 to 1 indicating the utility of a terminal position. For non-terminal positions, it can return anything.
    • A getPlayer() function, which returns 1 if it is the first player's turn, 0 if it is a state before a random action takes place, and -1 if it is the second player's turn.
  • Action objects may have any shape, however:
    • They must include an accessible "name" field of type string, which must be unique among any actions that can be taken from any single position.
    • They may optionally include an accessible "label" field of type string, which will be used (if present) to override the name field for the purpose of displaying text on edges representing actions. They need not be unique.
At present, your code is run as-is on your web client. Long-running or infinite loops will therefore crash your web client. Take appropriate actions to mitigate this issue when writing custom code.

c
class
AdversarialSolver

f
function
constructor(game : AdversarialGame)

Here, you can do any setup you need to execute before any position is initialized.

If you override this function, you must call super() at the beginning of the function.

f
function
abstract
*runExpansion(position : AdversarialPosition) : Generator<Expansion>

Given the root position, this function should grow the game tree by expanding positions using the expand function.

f
function
abstract
*runAlgorithm(position : AdversarialPosition) : Generator<AlgoStep>

Given the root position, this function should explore the existing game tree and yield steps using the algoStep function. This function should not call expand().

To explore the game tree, use the moves field in the Position object.

f
function
expand(position : AdversarialPosition) : Expansion

This function is meant to be yielded by your implementation of runExpansion generator.

It will populate the given position's moves field.

f
function
algoStep() : AlgoStep

This function is meant to be yielded by your implementation of runAlgorithm generator.

c
class
AdversarialGame
implements EditableComponent

f
function
constructor()

The constructor of the game. Note that you will have to return an instance of a game on your case script.

f
function
abstract
getInitialPosition() : AdversarialPosition

You must implement this function, which will be run on initialization. It will return the initial position of the game.

The application will check for the implementation of abstract methods from the AdversarialPosition type using the value returned by this function.

f
function
abstract
getActions(position : AdversarialPosition) : Action[]

Here is where you will implement legal move search for your game. If you prefer to do that in your position, simply return the result of calling your position's getActions method.

f
function
abstract
getResult(position : AdversarialPosition, action : Action) : AdversarialPosition

Here is where you will implement position generation for your game. Given a position and an action taken from that position, return the resulting position. You can assume that the action was taken from calling getActions with the source position as the argument.

c
class
AdversarialPosition

p
property
moves : Move[]

This is a list of moves that can be taken from the current position. This list is populated as a side effect the first time the solver's expand function is called on it.

p
property
bestMoves : Move[]

This is a subset of moves considered optimal for the current position. This should be populated by your algorithm.

p
property
utility : number | undefined

This is your calculated utility for the position. It should range from -1 to 1 and should be populated by your algorithm.

The renderer will use this value to render the border color of nodes.

It will also be rendered as a fixed property in the Position inspector.

p
property
data : any

This is an object you can use to store serializable data.

It will be shown as a fixed property in the Position inspector

If you store cyclic or otherwise nonserializable data in this field, it could cause issues when rendering the data in JSON.

p
property
style : NodeOptions

This will allow you to fine-tune the look of nodes in the tree display.

A lot of the properties you can supply to nodes are already automatically populated by the renderer. You can override them, but this could hide some of the default behaviour.

f
function
constructor()

This serves as the initialization for your position. You should call super() at the start of your code to initialize some of the internal properties indicated above.

f
function
drawHelper(ctx : CanvasRenderingContext2D) : CanvasHelper

This can be used in your render function to use the CanvasHelper API.

f
function
abstract
getId() : string

This function must be implemented and must return a unique string for the given position.

If the same position ID is returned by positions generated from different sources, the last one will be discarded and the first position with that ID will be used. This can result in convergent edges, or even cycles, in the game graph.

f
function
abstract
render(ctx : CanvasRenderingContext2D) : void

This function must be implemented. It provides a rendering context with which to graphically draw the position onto the canvas.

f
function
abstract
isTerminal() : boolean

This function must be implemented and must return true for all terminal position and false for positions where actions can still be taken.

f
function
abstract
getScore() : number

This function must be implemented and must return a value from -1 to 1 for terminal positions. For non-terminal positions, it can return anything.

The closer the value is to 1, the more positive it is for the first player. The closer it is to -1, the better it is for the second player.

f
function
abstract
getPlayer() : number

This function must be implemented and must return -1, 0, or 1.

1 indicates that the first player is to play, -1 indicates the second player, and 0 indicates a random action turn for non-deterministic games.

f
function
abstract
getHeuristic() : number

This function may be optionally implemented. If it is implemented, it should return a heuristic value from -1 to 1 which indicates the utility of the current non-terminal position.

Normally, if the position is terminal, it should return the same as getScore.

I
interface
Action

p
property
name : string

This serves as an identifier for the action. It must be unique among all actions that can be taken in any single position.

p
property
label : string = null

This property can be assigned to display a different label on action edges than the action name.

Actions can and should contain more fields, defined at the user's discretion.

I
interface
Move

p
property
action : Action

This contains the action that goes from the source position containing this move to the target position.

p
property

This is the target position reached when this move's action is taken from the source position.