- Generated by
1.9.1
|
penguins
1.0.0
|
Contains temporary data created during the evaluation of bot's moves.
Unlike the Game, this is really just a complementary struct for bot_compute_move and bot_compute_placement and less of a class in the OOP sense, though it is implemented as such (refer to the documentation of Game for the explanation). The primary reason for this being the autonomous mode, where the program is invoked each time just to make a single move and is not kept alive for the entire game, meaning that we can't have some additional state (unless we store it in a file, which I didn't want to do to keep things simple). Hence the logic in the autonomous mode and, therefore, the bot algorithm, is generally stateless or, in other words, "fire and forget" – at any point of the game, you can create a BotState, which stores only the intermediate data, compute and make a move, and then destroy it (though of course the BotState objects can be reused later). You could say that this kind of makes the bot algorithm a function of the game state in the mathematical sense.
For the purposes of recursive evaluation (see bot_compute_move), the BotState is actually represented as a linked list (because why not) of substates. Also, it keeps around the previously allocated memory blocks for lists (the _cap fields are for capacity of the lists) because constantly making the OS allocate and free temporary buffers is slow, but also since this makes the overall memory management in the bot much simpler – every function can return whenever and not care about freeing stuff because bot_state_free will free everything in the end.
Additional note regarding the rating functions (bot_rate_placement and bot_rate_move): all score calculations are performed with integers and not floats because integer arithmetic is faster (though marginally on modern CPUs) than floating point one, and we need to perform A LOT of it.
Data Fields | |
| volatile bool | cancelled |
Can be set to true from another thread to cancel the move evaluation. More... | |
References to other stuff | |
The BotState isn't responsible for freeing these. | |
| const BotParameters * | params |
Shouldn't be changed while the bot is running (hence marked as const). More... | |
| Game * | game |
| May be modified during the move evaluation, but once the job is done the Game will be returned to its original state. More... | |
| Rng * | rng |
| Just the Rng, nothing special. More... | |
Substates | |
See bot_enter_substate. | |
| struct BotState * | substate |
| The link to the next recursive substate. Substates are allocated on demand by bot_enter_substate. More... | |
| int | depth |
| The recursion depth of the current state, starts at 0 for the base state and increases in substates. More... | |
Allocation caches | |
See also bot_alloc_buf. | |
| size_t | tile_coords_cap |
| Coords * | tile_coords |
| size_t | tile_scores_cap |
| int * | tile_scores |
| size_t | possible_steps_cap |
| PossibleSteps * | possible_steps |
| size_t | all_moves_cap |
| BotMove * | all_moves |
| size_t | move_scores_cap |
| int * | move_scores |
| size_t | fill_grid1_cap |
| short * | fill_grid1 |
| size_t | fill_grid2_cap |
| short * | fill_grid2 |
| size_t | fill_stack_cap |
| FillSpan * | fill_stack |
Related Functions | |
(Note that these are not member functions.) | |
| 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... | |
| static bool | bot_flood_fill_check (int x, int y, void *data) |
| See bot_flood_fill_count_fish and flood_fill. More... | |
| static void | bot_flood_fill_mark (int x, int y, void *data) |
| See bot_flood_fill_count_fish and flood_fill. More... | |
| static FillSpan * | bot_flood_fill_alloc_stack (size_t capacity, void *data) |
| See bot_flood_fill_count_fish and flood_fill. 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... | |
| const BotParameters* BotState::params |
| Game* BotState::game |
May be modified during the move evaluation, but once the job is done the Game will be returned to its original state.
Definition at line 110 of file bot.h.
Referenced by bot_flood_fill_check(), and bot_flood_fill_mark().
| struct BotState* BotState::substate |
The link to the next recursive substate. Substates are allocated on demand by bot_enter_substate.
Definition at line 122 of file bot.h.
Referenced by bot_enter_substate(), and bot_state_free().
| int BotState::depth |
| volatile bool BotState::cancelled |
Can be set to true from another thread to cancel the move evaluation.
The volatile keyword stops the compiler from being too smart and overoptimizing stuff. For example, given this loop:
The compiler will think: "Well, the cancelled flag in the condition doesn't get changed inside the loop, isn't it? No point in constantly loading its value from memory!" and optimize this into:
The volatile keyword on the other hand ensures that every time the variable is used, the compiler doesn't optimize away (or reorder) the reads and writes to the memory, and they happen exactly in the way the programmer intended it in the code.
It, however, doesn't ensure synchronized access to the variable (or makes other guarantees) when it is used across multiple threads: for example, the changed value in memory might not be observed immediately by other processor cores (because of memory caches). Multithreading is not really the intended purpose of volatile and such use is generally frowned upon, but in our case its fine, since it isn't used for anything critical – the bot algorithm simply must be stopped eventually (the precise timing doesn't matter), doesn't require using compiler- or OS-specific thread synchronization facilities like mutexes or atomics (heard that C11 has those built-in), and a simple memory read of a value that almost never gets changed is generally faster than those.
| PossibleSteps* BotState::possible_steps |
| size_t BotState::fill_stack_cap |
Definition at line 192 of file bot.h.
Referenced by bot_flood_fill_alloc_stack().
| FillSpan* BotState::fill_stack |
Definition at line 193 of file bot.h.
Referenced by bot_flood_fill_alloc_stack().
|
related |
Constructs a BotState (similarly game_new).
Definition at line 42 of file bot.c.
Referenced by bot_enter_substate(), and run_autonomous_mode().
|
related |
Recursively destroys a BotState and its substates (similarly to game_free).
Definition at line 75 of file bot.c.
Referenced by run_autonomous_mode().
Allocates BotState::substate if necessary and returns it.
Definition at line 94 of file bot.c.
Referenced by bot_rate_move().
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 run_autonomous_mode().
Assigns a score to the placement at the given coordinates.
Evaluates the nearby tiles to determine how good the placement location is.
Definition at line 185 of file bot.c.
Referenced by bot_compute_placement().
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 run_autonomous_mode().
|
related |
Creates a list with all the possible moves (as penguin -> target pairs) of the provided penguins.
moves_count argument. Definition at line 330 of file bot.c.
Referenced by bot_compute_move(), and bot_rate_move().
Applies bot_rate_move to every move in the provided list and returns a pointer to the list of scores.
Definition at line 369 of file bot.c.
Referenced by bot_compute_move(), and bot_rate_move().
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.
Definition at line 433 of file bot.c.
Referenced by bot_rate_moves_list().
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.
Definition at line 565 of file bot.c.
Referenced by bot_rate_move(), and bot_rate_moves_list().
|
related |
Allocates a grid for use in bot_flood_fill_count_fish and fills it with zeroes.
Definition at line 620 of file bot.c.
Referenced by bot_rate_move(), and bot_rate_moves_list().
|
related |
See bot_flood_fill_count_fish and flood_fill.
Definition at line 638 of file bot.c.
Referenced by bot_flood_fill_count_fish().
|
related |
See bot_flood_fill_count_fish and flood_fill.
Definition at line 651 of file bot.c.
Referenced by bot_flood_fill_count_fish().
|
related |
See bot_flood_fill_count_fish and flood_fill.
Definition at line 661 of file bot.c.
Referenced by bot_flood_fill_count_fish().
|
related |
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.
Definition at line 677 of file bot.c.
Referenced by bot_rate_move(), and bot_rate_moves_list().
1.9.1