- Generated by
1.9.1
|
penguins
1.0.0
|
Go to the source code of this file.
Data Structures | |
| struct | BotParameters |
| Various parameters for the bot algorithm. More... | |
| struct | BotMove |
A penguin -> target pair. More... | |
| struct | FillSpan |
| Used internally by flood_fill. More... | |
| struct | BotState |
| Contains temporary data created during the evaluation of bot's moves. More... | |
Enumerations | |
| enum | BotPlacementStrategy { BOT_PLACEMENT_SMART , BOT_PLACEMENT_RANDOM , BOT_PLACEMENT_FIRST_POSSIBLE , BOT_PLACEMENT_MOST_FISH } |
| Values of BotParameters::placement_strategy. More... | |
| enum | BotMovementStrategy { BOT_MOVEMENT_SMART , BOT_MOVEMENT_RANDOM , BOT_MOVEMENT_FIRST_POSSIBLE } |
| Values of BotParameters::movement_strategy. More... | |
Functions | |
| void | init_bot_parameters (BotParameters *self) |
| Initializes all fields of the given BotParameters to default values. More... | |
| BotState * | bot_state_new (const BotParameters *params, Game *game, Rng *rng) |
| Constructs a BotState (similarly game_new). More... | |
| void | bot_state_free (BotState *self) |
| Recursively destroys a BotState and its substates (similarly to game_free). More... | |
| BotState * | bot_enter_substate (BotState *self) |
| Allocates BotState::substate if necessary and returns it. More... | |
| bool | bot_compute_placement (BotState *self, Coords *out_target) |
| Computes the best placement for the current player given the current game state. More... | |
| int | bot_rate_placement (BotState *self, Coords penguin) |
| Assigns a score to the placement at the given coordinates. More... | |
| bool | bot_compute_move (BotState *self, Coords *out_penguin, Coords *out_target) |
| Computes the best move for the current player given the current game state. More... | |
| BotMove * | bot_generate_all_moves_list (BotState *self, int penguins_count, Coords *penguins, int *moves_count) |
Creates a list with all the possible moves (as penguin -> target pairs) of the provided penguins. More... | |
| int * | bot_rate_moves_list (BotState *self, int moves_count, BotMove *moves_list) |
| Applies bot_rate_move to every move in the provided list and returns a pointer to the list of scores. More... | |
| int | bot_rate_move (BotState *self, BotMove move) |
| The heart of the bot, assigns a score to the given move according to its usefulness. More... | |
| bool | bot_quick_junction_check (BotState *self, Coords coords) |
| A precondition for junction checks to know if a more expensive flood fill test is necessary. More... | |
| short * | bot_flood_fill_reset_grid (BotState *self, short **fill_grid, size_t *fill_grid_cap) |
| Allocates a grid for use in bot_flood_fill_count_fish and fills it with zeroes. More... | |
| int | bot_flood_fill_count_fish (BotState *self, short *grid, Coords start, short marker_value) |
| Counts all fish accessible within an enclosed area starting at the given point using the flood fill algorithm. More... | |
| void | flood_fill (int x, int y, bool(*check)(int x, int y, void *data), void(*mark)(int x, int y, void *data), FillSpan *(*alloc_stack)(size_t capacity, void *data), void *data) |
| An implementation of flood fill using the span filling algorithm. More... | |
| enum BotPlacementStrategy |
Values of BotParameters::placement_strategy.
| Enumerator | |
|---|---|
| BOT_PLACEMENT_SMART | The standard "smart" algorithm, see bot_compute_placement for its description. |
| BOT_PLACEMENT_RANDOM | Pick a random tile for placement. |
| BOT_PLACEMENT_FIRST_POSSIBLE | Pick the first possible tile (first tile in the first row). |
| BOT_PLACEMENT_MOST_FISH | Pick the tiles with the most fish in the vicinity. |
| enum BotMovementStrategy |
Values of BotParameters::movement_strategy.
| Enumerator | |
|---|---|
| BOT_MOVEMENT_SMART | The standard "smart" algorithm, see bot_compute_move for its description. |
| BOT_MOVEMENT_RANDOM | Pick a random move. |
| BOT_MOVEMENT_FIRST_POSSIBLE | Pick the first possible move (also known as the "dumb" algorithm). |
| void init_bot_parameters | ( | BotParameters * | self | ) |
Initializes all fields of the given BotParameters to default values.
Definition at line 31 of file bot.c.
Referenced by GamePanel::GamePanel().
| BotState* bot_state_new | ( | const BotParameters * | params, |
| Game * | game, | ||
| Rng * | rng | ||
| ) |
Constructs a BotState (similarly game_new).
Definition at line 42 of file bot.c.
Referenced by BotThread::BotThread().
| void bot_state_free | ( | BotState * | self | ) |
Allocates BotState::substate if necessary and returns it.
Computes the best placement for the current player given the current game state.
The algorithm for the placement phase is very simple:
true if the function managed to find a placement, false if there are no possible placements for the player or if the computation was cancelled. The coordinates of the resulting tile are written to out_target. Definition at line 143 of file bot.c.
Referenced by BotPlacementThread::Entry().
Computes the best move for the current player given the current game state.
The overall algorithm is roughly the following:
Note that when evaluating moves recursively, the provided Game is modified instead of creating a copy of it each time. However, recursive evaluation currently has a significant limitation – it only considers sequences of moves of a single penguin, and doesn't take the opponents' moves into account at all (doing otherwise consumes too much computing time).
true if a move was found, false if there were no moves available for the player or if the computation was cancelled. If found, the move is written to out_penguin and out_target.The aggressive strategy proved to be very effective against other bots, which are usually passive (meaning that they simply try to collect fish) - it first blocks all other players and then collects the rest of the fish. It is even somewhat effective against humans because its aggressiveness essentially relies on the opponent making a mistake, which is not an unreasonable assumption when playing against a human (especially myself). Although, consequently, the stupidest bots, which are simply making literally the first available move after scanning the board (this is what the BOT_MOVEMENT_FIRST_POSSIBLE strategy does), ended up being the algorithm's fatal weakness (well, not exactly fatal, it can still win against those) – primarily because they are very persistent at just moving in a single direction.
Definition at line 295 of file bot.c.
Referenced by BotMovementThread::Entry().
Applies bot_rate_move to every move in the provided list and returns a pointer to the list of scores.
The heart of the bot, assigns a score to the given move according to its usefulness.
In case a cancellation is requested (see BotState::cancelled), this function starts unwinding the recursive calls and returns some garbage score, but otherwise the move computation is stopped.
A precondition for junction checks to know if a more expensive flood fill test is necessary.
A "junction" is a state when then bot has to choose between two or more directions because once it makes a move the other paths will become inaccessible. This function only performs a quick heuristic check which can only tell if the current tile is definitely not a junction, so it is used to know if a further more time-consuming flood fill test is necessary.
| short* bot_flood_fill_reset_grid | ( | BotState * | self, |
| short ** | fill_grid, | ||
| size_t * | fill_grid_cap | ||
| ) |
Allocates a grid for use in bot_flood_fill_count_fish and fills it with zeroes.
Counts all fish accessible within an enclosed area starting at the given point using the flood fill algorithm.
Returns the number of reachable fish, the counted tiles are marked on the provided fill grid with marker_value, which must be non-zero. Additionally is used for junction checks.
| void flood_fill | ( | int | x, |
| int | y, | ||
| bool(*)(int x, int y, void *data) | check, | ||
| void(*)(int x, int y, void *data) | mark, | ||
| FillSpan *(*)(size_t capacity, void *data) | alloc_stack, | ||
| void * | data | ||
| ) |
An implementation of flood fill using the span filling algorithm.
This is essentially the algorithm behind the "bucket" tool in paint programs. The code was pretty much copied (and translated from pseudocode) from Wikipedia.
| x | the starting point |
| y | the starting point |
| check | a function that returns true if the given cell should be marked |
| mark | a function that marks the given cell |
| alloc_stack | a function that allocates that stack for FillSpan s |
| data | extra data to be passed into the provided functions |
Definition at line 725 of file bot.c.
Referenced by BotState::bot_flood_fill_count_fish().
1.9.1