The Ever-Changing Labyrinth (Controller WIP)
king-of-the-hill grid maze javascript
This is a 2-player asymmetric KotH challenge.
- One player controls a pair of telepathically connected adventurers who are trying to get through a maze.
- The other player has the ability to change the maze and tries to keep the adventurers from solving it.
Gameplay
The game is made up of a variable number of rounds, each consisting of up to 1000 turns.
At the beginning of a round, the Maze Master creates an \$n \times n\$ maze, starting at \$n = 3\$, and increasing by \$1\$ on each subsequent round.
Every cell of the maze must always be reachable from every other cell.
Both adventurers begin on the northwest corner cell. The goal is on the southeast corner cell. One adventurer begins facing east and the other begins facing south.
The game proceeds in a turn-based fashion, alternating between each player.
- Adventurers:
- Observe surroundings of themself and the other adventurer:
- The wall directly ahead on the current cell is observed
- If there is no wall directly ahead on the current cell, every wall is observed along each cell ahead in a straight line until a wall obstructs the adventurer's sight
- The walls on the left and right of the current cell are observed
- If there is no wall to the left, the wall ahead on the cell to the left can be observed
- If there is no wall to the right, the wall ahead on the cell to the right can be observed
- The relative position of the other adventurer, if present on one of the cells they can see.
- Either moves forward, changes orientation, or waits
- The maze master, in order:
- Receives \$ 1 + \lfloor \log_n(t) \rfloor \$ mana (where \$t\$ is the turn number, starting at 1), which can be used to modify the maze
- Observes the entire maze, including the position and orientation of each adventurer
- May remove a wall from anywhere in the maze that is not currently visible to either adventurer
- May add a wall to anywhere in the maze that is not currently visible to either adventurer, provided it does not separate the maze into two unconnected halves.
Illustration of how adventurers observe the maze:
The adventurer in the above image is facing east and sees all the green cells and walls. The dotted green lines indicate non-walls the adventurer can see.
Adventurers may occupy the same space and face different directions. Observation occurs before either of them chooses an action; movement is resolved simultaneously.
The cost to modify the maze increases according to the fibonacci sequence. The first time a particular wall segment is added or removed, it costs 1 mana, the second time costs 1 mana, then 2, 3, 5, 8, 13, 21, 34, 55... Modification cost is independent for each edge of the grid where a wall segment can be placed, so it is more costly to toggle the same wall than it is to toggle different walls each time.
The maze master can stockpile an arbitrarily large amount of mana, but can only change two walls per turn (removing one, then adding one)
The round continues until either of the two adventurers reaches the goal cell, at which point, the game will continue onto the next round.
If neither reaches the goal after 1000 turns, then the maze master wins and the game ends.
The maze master does not carry over mana between rounds.
Coding
- Both players may retain as much information as they wish for the entire duration of the game. State may carry on from one round to the next.
- State and retained information will not be remembered between games.
- Players will not be able to access the state of the other player.
- Each player will receive an isolated RNG state at the beginning of each game. To ensure that all games have the same outcome with a given seed, all non-deterministic behavior must use the provided RNG. (Math.random is overridden for each bot, just in case)
- Each bot is allotted 50ms of CPU time at the beginning of the round and 1ms for each turn. Exceeding this allotment will result in a strike.
- Maze generation has a time limit of \$n^2\$ ms. (i.e. 9ms for the \$3 \times 3\$ maze, 16ms for the \$4 \times 4\$ maze, 25ms for \$5 \times 5\$, and so forth.)
- Adventurers are given 10ms to set up state between rounds. Exceeding this time limit results in a strike.
- Generating an illegal maze will result in a strike.
- If a wall added to the maze divides the maze into two unconnected halves, the maze master will receive a strike.
- If a wall to be added or removed is visible by either adventurer, the wall will not change but the mana will still be spent.
- If the maze master does not have enough mana to perform both of its requested actions, its actions will be ignored.
- If the maze master specifies the same wall for both removing and adding, the actions will be ignored.
- If the maze master tries to remove a wall that is already missing or add a wall that is already present, the relevant action will be ignored.
- Illegal adventurer moves will be treated the same as a wait action.
- If a bot gets a strike, the game will be thrown out of the tournament as an outlier. If any particular bot gets 3 strikes during the tournament, it will be disqualified, and all the matches it was a part of will be discarded and ignored.
- Submissions may not attempt to exploit bugs in the controller in order to break other rules.
- Submissions must be compatible with being run inside web workers as well as being run in the foreground.
- Submissions may not call any asynchronous functions (usually I/O)
Adventurers Interface
Your submission must define the body of a function which receives a single argument (random, a function that returns a pseudorandom number between 0 and 1) returns an object with the following interface:
startRound(mazeSize: number)
takeTurn(vision: [Vision, Vision]) -> [number, number]
takeTurn should return a pair of integers describing the action taken by each adventurer. Actions are defined as follows:
const ACTION = {
WAIT: 0,
FORWARD: 1,
TURN_RIGHT: 2,
TURN_AROUND: 3,
TURN_LEFT: 4,
}
Vision is defined as an object with this schema
{
ahead: [
{
ahead: true | false,
left: true | false,
right: true | false,
}
...
],
leftAhead: true | false | null,
rightAhead: true | false | null,
friend: [number, number] | null
}
The zeroth element of the ahead array represents the current cell the adventurer is on, and each subsequent element represents the next cell ahead.
null means that wall cannot be seen, so it is uncertain whether it is present or not.
friend will be an ordered pair of numbers representing the number of cells ahead and the number of cells to the right (will be -1 when the other adventurer is to the left) that the other adventurer is relative to this one. If the other adventurer is not visible, friend will be null
Maze Master Interface
Your submission must define the body of a function which receives a single argument (random, a function that returns a pseudorandom number between 0 and 1) returns an object with the following interface:
generateMaze(mazeSize: number) -> Maze
takeTurn(mana: number, maze: Maze) -> [WallCoord | null, WallCoord | null]
generateMaze should return a row-major array of arrays of objects that describe the east and south walls of the cell. Each cell must have the following schema:
{
east: boolean | null // will be null along the east edge of the maze
south: boolean | null // will be null along the south edge of the maze
}
takeTurn should return a pair of wall coordinates, describing the wall to remove and the wall to add. Both coordinates are optional and may be null or undefined. Wall coordinates should be an array of the row, column, and 'south' or 'east' representing the location of the wall. The schema is as follows:
[number, number, 'south'|'east']
The maze provided to takeTurn is similar to the maze expected to be returned by generateMaze, but with two additional properties on each cell to define the mana cost to update:
{
eastCost: number
southCost: number
}
Submission Format
In order to aid answer scraping, please format your submissions in the following format:
# <submission type>: <name>
Optional blurb
// relevant functions, constants, variables go here
return /* the object */
Description/explanation of how the bot works + whatever you want
<submission type> must be the exact string of either Adventurers or Maze Master which corresponds to your submission type
Only the first code block of your post will be scraped. Submissions will be loaded as if they are the body of a function, which is executed once with no arguments. Submission names should be different from any other submissions.
You may submit both an adventurer bot and a maze master bot, each in its own post. You may also submit multiple bots of the same type as long as they are reasonably different from each other. Please don't hog the leaderboard with near-identical bots.
Scoring and The Tournament
Adventurers compete only with other adventurers, and the same goes for maze masters.
The overall score for a game for both roles is 1000 points per maze completed by the adventurers minus the number of turns taken in total. Score can go negative.
Each adventurer bot will play against each opposing maze master bot an equal number of times until the ranking of the top 5 bots for each role are established with 95% confidence. The overall tournament score for a given bot is averaged across all games that bot played in the tournament.
The adventurer bot with the highest score wins.
The maze master bot with the lowest score wins.
Scores will be updated when a adventurer or maze master is added or updated.
king-of-the-hill grid maze javascript
Pull requests welcome on the controller. Vanilla JS only (Current ES standard is fine), preferably, though jQuery is probably ok. It needs to work on GitHub pages in Firefox and Chrome without needing babel or webpack or similar.
Parts still in need of implementation:
- Fix bugs in Maze Master modification handling (there are certain cases where visibility is not respected properly)
- Code scraper
- Tournament controller
- Better syntax error reporting for bots
- Foreground error reporting for bots (instead of tucking it away in dev tools)
- (nice-to-have, preferably before posting to main) improved renderer that shows visible cells and walls and the effects of the last move (or better yet, changes since last render).
- (nice-to-have, can wait until after posting to main) background game runner that runs in a web worker and can be controlled by the tournament controller
I recommend checking in via the chat room to avoid duplicating work.
Beta bot submissions also welcome, though I'm not sure how these are going to be integrated at the moment.
