#include <array>
#include <cstdlib>
#include <cstring>
#include <QLoggingCategory>
#include "player.h"
#include "shared.h"
#include "city.h"
#include "game.h"
#include "government.h"
#include "map.h"
#include "specialist.h"
#include "cm.h"
#include "specvec.h"

Include dependency graph for cm.cpp:

Classes
struct	cm_fitness

struct	cm_tile
	A tile. More...

struct	cm_tile_type
	A tile type. More...

struct	partial_solution
	A partial solution. More...

struct	cm_state
	State of the search. More...

Macros
#define	CM_MAX_LOOP 25000

#define	CPUHOG_CM_MAX_LOOP (CM_MAX_LOOP * 4)

#define	PRINT_TIME_STATS_EVERY_QUERY

#define	LOG_TIME_STATS LOG_DEBUG

#define	LOG_CM_STATE LOG_DEBUG

#define	LOG_LATTICE LOG_DEBUG

#define	LOG_REACHED_LEAF LOG_DEBUG

#define	LOG_BETTER_LEAF LOG_DEBUG

#define	LOG_PRUNE_BRANCH LOG_DEBUG

#define	SPECVEC_TAG tile

#define	SPECVEC_TYPE struct cm_tile

#define	SPECVEC_TAG tile_type

#define	SPECVEC_TYPE struct cm_tile_type *

#define	tile_type_vector_iterate(vector, var)

#define	tile_type_vector_iterate_end

#define	print_tile_type(loglevel, ptype, prefix)

#define	print_lattice(loglevel, lattice)

#define	print_partial_solution(loglevel, soln, state)

Functions
static int	num_types (const struct cm_state *state)
	Return the number of different tile types. More...

static void	cm_result_copy (std::unique_ptr< cm_result > &result, const struct city pcity, bool workers_map)
	Copy the city's current setup into the cm result structure. More...

static double	estimate_fitness (const struct cm_state *state, const int production[])
	Estimate the fitness of a tile. More...

static bool	choice_is_promising (struct cm_state *state, int newchoice, bool negative_ok)
	A choice is unpromising if isn't better than the best in at least one way. More...

void	cm_init ()
	Initialize the CM data at the start of each game. More...

void	cm_init_citymap ()
	Initialize the CM citymap data. More...

void	cm_free ()
	Called at the end of a game to free any CM data. More...

std::unique_ptr< cm_result >	cm_result_new (struct city *pcity)
	Create a new cm_result. More...

static void	tile_type_init (struct cm_tile_type *type)
	Set all production to zero and initialize the vectors for this tile type. More...

static struct cm_tile_type *	tile_type_dup (const struct cm_tile_type *oldtype)
	Duplicate a tile type, except for the vectors - the vectors of the new tile type will be empty. More...

static void	tile_type_destroy (struct cm_tile_type *type)
	Free all the storage in the tile type (but don't free the type itself). More...

static void	tile_type_vector_free_all (struct tile_type_vector *vec)
	Destroy and free all types in the vector, and the vector itself. More...

static bool	tile_type_equal (const struct cm_tile_type a, const struct cm_tile_type b)
	Return TRUE iff all categories of the two types are equal. More...

static bool	tile_type_better (const struct cm_tile_type a, const struct cm_tile_type b)
	Return TRUE if tile a is better or equal to tile b in all categories. More...

static int	tile_type_vector_find_equivalent (const struct tile_type_vector vec, const struct cm_tile_type ptype)
	If there is a tile type in the vector that is equivalent to the given type, return its index. More...

static int	tile_type_num_tiles (const struct cm_tile_type *type)
	Return the number of tiles of this type that can be worked. More...

static int	tile_type_num_prereqs (const struct cm_tile_type *ptype)
	Return the number of tile types that are better than this type. More...

static const struct cm_tile_type *	tile_type_get (const struct cm_state *state, int type)
	Retrieve a tile type by index. More...

static const struct cm_tile *	tile_get (const struct cm_tile_type *ptype, int j)
	Retrieve a tile of a particular type by index. More...

static bool	fitness_better (struct cm_fitness a, struct cm_fitness b)
	Return TRUE iff fitness A is strictly better than fitness B. More...

static struct cm_fitness	worst_fitness ()
	Return a fitness struct that is the worst possible result we can represent. More...

static struct cm_fitness	compute_fitness (const int surplus[], bool disorder, bool happy, const struct cm_parameter *parameter)
	Compute the fitness of the given surplus (and disorder/happy status) according to the weights and minimums given in the parameter. More...

static void	init_partial_solution (struct partial_solution *into, int ntypes, int idle, bool negative_ok)
	Allocate and initialize an empty solution. More...

static void	destroy_partial_solution (struct partial_solution *into)
	Free all storage associated with the solution. More...

static void	copy_partial_solution (struct partial_solution dst, const struct partial_solution src, const struct cm_state *state)
	Copy the source solution into the destination one (the destination solution must already be allocated). More...

static void	apply_solution (struct cm_state state, const struct partial_solution soln)
	Evaluating a completed solution. More...

static void	get_city_surplus (const struct city pcity, int surplus[], bool disorder, bool *happy)
	Convert the city's surplus numbers into an array. More...

static struct cm_fitness	evaluate_solution (struct cm_state state, const struct partial_solution soln)
	Compute the fitness of the solution. More...

static void	convert_solution_to_result (struct cm_state state, const struct partial_solution soln, std::unique_ptr< cm_result > &result)
	Convert the solution into a cm_result. More...

static int	compare_tile_type_by_lattice_order (const struct cm_tile_type a, const struct cm_tile_type b)
	Compare functions to allow sorting lattice vectors. More...

static int	compare_tile_type_by_fitness (const void va, const void vb)
	Sort by fitness. More...

static int	compare_tile_type_by_stat (const void va, const void vb)
	Compare by the production of type compare_key. More...

static void	compute_tile_production (const struct city pcity, const struct tile ptile, bool is_celebrating, struct cm_tile_type *out)
	Compute the tile-type lattice. More...

static void	tile_type_lattice_add (struct tile_type_vector lattice, const struct cm_tile_type newtype, int tindex)
	Add the tile [x,y], with production indicated by type, to the tile-type lattice. More...

static void	init_specialist_lattice_nodes (struct cm_state state, const struct city pcity)
	Create lattice nodes for each type of specialist. More...

static void	top_sort_lattice (struct tile_type_vector *lattice)
	Topologically sort the lattice. More...

static void	clean_lattice (struct tile_type_vector lattice, const struct city pcity)
	Remove unreachable lattice nodes to speed up processing later. More...

static void	sort_lattice_by_fitness (const struct cm_state state, struct tile_type_vector lattice)
	Determine the estimated_fitness fields, and sort by that. More...

static void	init_tile_lattice (struct city pcity, struct cm_state state)
	Create the lattice. More...

static bool	choice_stack_empty (struct cm_state *state)
	Handling the choice stack for the bb algorithm. More...

static int	last_choice (struct cm_state *state)
	Return the last choice in the stack. More...

static void	add_workers (struct partial_solution soln, int itype, int number, const struct cm_state state)
	Update the solution to assign 'number' more workers on to tiles of the given type. More...

static void	add_worker (struct partial_solution soln, int itype, const struct cm_state state)
	Add just one worker to the solution. More...

static void	remove_worker (struct partial_solution soln, int itype, const struct cm_state state)
	Remove just one worker from the solution. More...

static void	pop_choice (struct cm_state *state)
	Remove a worker from the current solution, and pop once off the choice stack. More...

static bool	prereqs_filled (const struct partial_solution soln, int type, const struct cm_state state)
	True if all tiles better than this type have been used. More...

static int	next_choice (struct cm_state *state, int oldchoice, bool negative_ok)
	Return the next choice to make after oldchoice. More...

static bool	take_sibling_choice (struct cm_state *state, bool negative_ok)
	Pick a sibling choice to the last choice. More...

static bool	take_child_choice (struct cm_state *state, bool negative_ok)
	Go down from the current branch, if we can. More...

static void	complete_solution (struct partial_solution soln, const struct cm_state state, const struct tile_type_vector *lattice)
	Complete the solution by choosing tiles in order off the given tile lattice. More...

static int	specialists_in_solution (const struct cm_state state, const struct partial_solution soln)
	Return number of specialists used in partial solution. More...

static void	compute_max_stats_heuristic (const struct cm_state state, const struct partial_solution soln, int production[], int check_choice, bool negative_ok)
	The heuristic: A partial solution cannot produce more food than the amount of food it currently generates plus then placing all its workers on the best food tiles. More...

static void	init_min_production (struct cm_state *state)
	Initialize minimal production needed to be sufficient. More...

static void	get_tax_rates (const struct player *pplayer, int rates[])
	Get the national budget, see city.c. More...

static bool	bb_next (struct cm_state *state, bool negative_ok)
	The high-level algorithm is: More...

static struct cm_state *	cm_state_init (struct city pcity, const cm_parameter param, bool negative_ok)
	Initialize the state for the branch-and-bound algorithm. More...

static int	min_food_surplus_for_fastest_growth (struct cm_state *state)
	Find the minimum food surplus needed to grow in the fewest number of turns. More...

static void	begin_search (struct cm_state state, const struct cm_parameter parameter, bool negative_ok)
	Set the parameter for the state. More...

static void	end_search (struct cm_state *state)
	Clean up after a search. More...

static void	cm_state_free (struct cm_state *state)
	Release all the memory allocated by the state. More...

static void	cm_find_best_solution (struct cm_state state, const struct cm_parameter const parameter, std::unique_ptr< cm_result > &result, bool negative_ok)
	Run B&B until we find the best solution. More...

void	cm_query_result (struct city pcity, const struct cm_parameter param, std::unique_ptr< cm_result > &result, bool negative_ok)
	Wrapper that actually runs the branch & bound, and returns the best solution. More...

bool	operator== (const struct cm_parameter &p1, const struct cm_parameter &p2)

void	cm_copy_parameter (struct cm_parameter dest, const struct cm_parameter const src)
	Copy the parameter from the source to the destination field. More...

void	cm_init_parameter (struct cm_parameter *dest)
	Initialize the parameter to sane default values. More...

void	cm_init_emergency_parameter (struct cm_parameter *dest)
	Initialize the parameter to sane default values that will always produce a result. More...

int	cm_result_workers (const std::unique_ptr< cm_result > &result)
	Count the total number of workers in the result. More...

int	cm_result_specialists (const std::unique_ptr< cm_result > &result)
	Count the total number of specialists in the result. More...

int	cm_result_citizens (const std::unique_ptr< cm_result > &result)
	Count the total number of citizens in the result. More...

void	cm_result_from_main_map (std::unique_ptr< cm_result > &result, const struct city *pcity)
	Copy the city's current setup into the cm result structure. More...

void	cm_print_city (const struct city *pcity)
	Debugging routines. More...

void	cm_print_result (const std::unique_ptr< cm_result > &result)
	Print debugging information about a full CM result. More...

Variables
static Output_type_id	compare_key

static double	compare_key_trade_bonus

Detailed Description

Terms used

Stats: food, shields, trade, luxury, science, and gold. Production: amount of stats you get directly from farming tiles or having specialists. Surplus: amount of stats you get, taking buildings, taxes, disorder, and any other effects into account.

Happy State: disorder (unhappy), content (!unhappy && !happy) and happy (happy)

Tile type: usually, many tiles produce the same f/s/t. So we bin the tiles into tile types. Specialists are also a 'tile type.'

Unlike the original CM code, which used a dynamic programming approach, this code uses a branch-and-bound approach. The DP approach allowed cacheing, but it was hard to guarantee the correctness of the cache, so it was usually tossed and recomputed.

The B&B approach also allows a very simple greedy search, whereas the DP approach required a lot of pre-computing. And, it appears to be very slightly faster. It evaluates about half as many solutions, but each candidate solution is more expensive due to the lack of cacheing.

We use highly specific knowledge about how the city computes its stats in two places:

setting the min_production array. Ideally the city should tell us.
computing the weighting for tiles. Ditto.

Definition in file cm.cpp.

Macro Definition Documentation

◆ CM_MAX_LOOP

#define CM_MAX_LOOP 25000

Definition at line 72 of file cm.cpp.

◆ CPUHOG_CM_MAX_LOOP

#define CPUHOG_CM_MAX_LOOP (CM_MAX_LOOP * 4)

Definition at line 74 of file cm.cpp.

◆ LOG_BETTER_LEAF

#define LOG_BETTER_LEAF LOG_DEBUG

Definition at line 88 of file cm.cpp.

◆ LOG_CM_STATE

#define LOG_CM_STATE LOG_DEBUG

Definition at line 85 of file cm.cpp.

◆ LOG_LATTICE

#define LOG_LATTICE LOG_DEBUG

Definition at line 86 of file cm.cpp.

◆ LOG_PRUNE_BRANCH

#define LOG_PRUNE_BRANCH LOG_DEBUG

Definition at line 89 of file cm.cpp.

◆ LOG_REACHED_LEAF

#define LOG_REACHED_LEAF LOG_DEBUG

Definition at line 87 of file cm.cpp.

◆ LOG_TIME_STATS

#define LOG_TIME_STATS LOG_DEBUG

Definition at line 84 of file cm.cpp.

◆ print_lattice

#define print_lattice	(	loglevel,
		lattice
	)

Definition at line 271 of file cm.cpp.

◆ print_partial_solution

#define print_partial_solution	(	loglevel,
		soln,
		state
	)

Definition at line 272 of file cm.cpp.

◆ print_tile_type

#define print_tile_type	(	loglevel,
		ptype,
		prefix
	)

Definition at line 270 of file cm.cpp.

◆ PRINT_TIME_STATS_EVERY_QUERY

#define PRINT_TIME_STATS_EVERY_QUERY

Definition at line 82 of file cm.cpp.

◆ SPECVEC_TAG [1/2]

#define SPECVEC_TAG tile

Definition at line 134 of file cm.cpp.

◆ SPECVEC_TAG [2/2]

#define SPECVEC_TAG tile_type

Definition at line 134 of file cm.cpp.

◆ SPECVEC_TYPE [1/2]

#define SPECVEC_TYPE struct cm_tile

Definition at line 135 of file cm.cpp.

◆ SPECVEC_TYPE [2/2]

#define SPECVEC_TYPE struct cm_tile_type *

Definition at line 135 of file cm.cpp.

◆ tile_type_vector_iterate

#define tile_type_vector_iterate	(	vector,
		var
	)

Value:

  {                                                                         \
    struct cm_tile_type *var;                                               \
    TYPED_VECTOR_ITERATE(struct cm_tile_type *, vector, var##p)             \
    {                                                                       \
      var = *var##p;                                                        \
      {

Definition at line 137 of file cm.cpp.

◆ tile_type_vector_iterate_end

#define tile_type_vector_iterate_end

Value:

  }                                                                         \
  }                                                                         \
  VECTOR_ITERATE_END;                                                       \
  }

Definition at line 144 of file cm.cpp.

Function Documentation

◆ add_worker()

static void add_worker	(	struct partial_solution *	soln,
		int	itype,
		const struct cm_state *	state
	)

static

Add just one worker to the solution.

Definition at line 1340 of file cm.cpp.

Referenced by compute_max_stats_heuristic(), take_child_choice(), and take_sibling_choice().

◆ add_workers()

static void add_workers	(	struct partial_solution *	soln,
		int	itype,
		int	number,
		const struct cm_state *	state
	)

static

Update the solution to assign 'number' more workers on to tiles of the given type.

'number' may be negative, in which case we're removing workers. We do lots of sanity checking, since many bugs can get caught here.

Definition at line 1283 of file cm.cpp.

Referenced by add_worker(), complete_solution(), and remove_worker().

◆ apply_solution()

static void apply_solution	(	struct cm_state *	state,
		const struct partial_solution *	soln
	)

static

Evaluating a completed solution.

Apply the solution to state->workers_map.

Definition at line 655 of file cm.cpp.

Referenced by convert_solution_to_result().

◆ bb_next()

static bool bb_next	(	struct cm_state *	state,
		bool	negative_ok
	)

static

The high-level algorithm is:

for each idle worker, non-deterministically choose a position for the idle worker to use

To implement this, we keep a stack of the choices we've made. When we want the next node in the tree, we see if there are any idle workers left. We push an idle worker, and make it take the first field in the lattice. If there are no idle workers left, then we pop out until we can make another choice.

Definition at line 1805 of file cm.cpp.

Referenced by cm_find_best_solution().

◆ begin_search()

static void begin_search	(	struct cm_state *	state,
		const struct cm_parameter *	parameter,
		bool	negative_ok
	)

static

Set the parameter for the state.

This is the first step in actually solving anything.

Definition at line 1991 of file cm.cpp.

Referenced by cm_find_best_solution().

◆ choice_is_promising()

static bool choice_is_promising	(	struct cm_state *	state,
		int	newchoice,
		bool	negative_ok
	)

static

A choice is unpromising if isn't better than the best in at least one way.

A choice is also unpromising if any of the stats is less than the absolute minimum (in practice, this matters a lot more).

Definition at line 1634 of file cm.cpp.

Referenced by next_choice().

◆ choice_stack_empty()

static bool choice_stack_empty ( struct cm_state * state )

static

Handling the choice stack for the bb algorithm.

Return TRUE iff the stack is empty.

Definition at line 1252 of file cm.cpp.

Referenced by bb_next(), last_choice(), and pop_choice().

◆ clean_lattice()

static void clean_lattice	(	struct tile_type_vector *	lattice,
		const struct city *	pcity
	)

static

Remove unreachable lattice nodes to speed up processing later.

This doesn't reduce the number of evaluations we do, it just reduces the number of times we loop over and reject tile types we can never use.

A node is unreachable if there are fewer available workers than are needed to fill up all predecessors. A node at depth two needs three workers to be reachable, for example (two to fill the predecessors, and one for the tile). We remove a node if its depth is equal to the city size, or larger.

We could clean up the tile arrays in each type (if we have two workers, we can use only the first tile of a depth 1 tile type), but that wouldn't save us anything later.

Definition at line 1119 of file cm.cpp.

Referenced by init_tile_lattice().

◆ cm_copy_parameter()

void cm_copy_parameter	(	struct cm_parameter *	dest,
		const struct cm_parameter *const	src
	)

Copy the parameter from the source to the destination field.

Definition at line 2163 of file cm.cpp.

Referenced by auto_arrange_workers(), begin_search(), cmafec_get_fe_parameter(), cmafec_preset_add(), handle_city_manager(), and package_city().

◆ cm_find_best_solution()

static void cm_find_best_solution	(	struct cm_state *	state,
		const struct cm_parameter *const	parameter,
		std::unique_ptr< cm_result > &	result,
		bool	negative_ok
	)

static

Run B&B until we find the best solution.

Definition at line 2063 of file cm.cpp.

Referenced by cm_query_result().

◆ cm_free()

void cm_free ( )

Called at the end of a game to free any CM data.

Definition at line 315 of file cm.cpp.

Referenced by game_free().

◆ cm_init()

void cm_init ( )

Initialize the CM data at the start of each game.

Note the citymap indices will not have been initialized yet (cm_init_citymap is called when they are).

Definition at line 288 of file cm.cpp.

Referenced by game_init().

◆ cm_init_citymap()

void cm_init_citymap ( )

Initialize the CM citymap data.

This function is called when the city map indices are generated (basically when the topology is set, shortly after the start of the game).

Definition at line 307 of file cm.cpp.

Referenced by generate_city_map_indices().

◆ cm_init_emergency_parameter()

void cm_init_emergency_parameter ( struct cm_parameter * dest )

Initialize the parameter to sane default values that will always produce a result.

Definition at line 2192 of file cm.cpp.

Referenced by auto_arrange_workers().

◆ cm_init_parameter()

void cm_init_parameter ( struct cm_parameter * dest )

Initialize the parameter to sane default values.

Definition at line 2172 of file cm.cpp.

Referenced by auto_arrange_workers(), cmafec_get_fe_parameter(), dai_manage_taxes(), and cma_yoloswag::get_parameter().

◆ cm_print_city()

void cm_print_city ( const struct city * pcity )

Debugging routines.

Print debugging information about one city.

Definition at line 2432 of file cm.cpp.

Referenced by cma_yoloswag::apply_result_on_server(), auto_arrange_workers(), and cma_yoloswag::result_came_from_server().

◆ cm_print_result()

void cm_print_result ( const std::unique_ptr< cm_result > & result )

Print debugging information about a full CM result.

Definition at line 2472 of file cm.cpp.

Referenced by cma_yoloswag::apply_result_on_server(), auto_arrange_workers(), and cma_yoloswag::result_came_from_server().

◆ cm_query_result()

void cm_query_result	(	struct city *	pcity,
		const struct cm_parameter *	param,
		std::unique_ptr< cm_result > &	result,
		bool	negative_ok
	)

Wrapper that actually runs the branch & bound, and returns the best solution.

Definition at line 2115 of file cm.cpp.

Referenced by auto_arrange_workers(), dai_manage_taxes(), and cma_yoloswag::handle_city().

◆ cm_result_citizens()

int cm_result_citizens ( const std::unique_ptr< cm_result > & result )

Count the total number of citizens in the result.

Definition at line 2246 of file cm.cpp.

Referenced by cma_yoloswag::apply_result_on_server().

◆ cm_result_copy()

static void cm_result_copy	(	std::unique_ptr< cm_result > &	result,
		const struct city *	pcity,
		bool *	workers_map
	)

static

Copy the city's current setup into the cm result structure.

'workers_map' is a bool array with the size city_map_tiles_from_city(pcity). It is TRUE for tiles worked by the city.

Definition at line 2266 of file cm.cpp.

Referenced by cm_result_from_main_map(), and convert_solution_to_result().

◆ cm_result_from_main_map()

void cm_result_from_main_map	(	std::unique_ptr< cm_result > &	result,
		const struct city *	pcity
	)

Copy the city's current setup into the cm result structure.

Wrapper for cm_result_main().

Definition at line 2255 of file cm.cpp.

Referenced by cma_yoloswag::apply_result_on_server(), and cma_yoloswag::result_came_from_server().

◆ cm_result_new()

std::unique_ptr<cm_result> cm_result_new ( struct city * pcity )

Create a new cm_result.

Definition at line 330 of file cm.cpp.

Referenced by cma_yoloswag::apply_result_on_server(), auto_arrange_workers(), dai_manage_taxes(), cma_yoloswag::handle_city(), and cma_yoloswag::result_came_from_server().

◆ cm_result_specialists()

int cm_result_specialists ( const std::unique_ptr< cm_result > & result )

Count the total number of specialists in the result.

Definition at line 2233 of file cm.cpp.

Referenced by cm_result_citizens().

◆ cm_result_workers()

int cm_result_workers ( const std::unique_ptr< cm_result > & result )

Count the total number of workers in the result.

Definition at line 2211 of file cm.cpp.

Referenced by cm_print_result(), and cm_result_citizens().

◆ cm_state_free()

static void cm_state_free ( struct cm_state * state )

static

Release all the memory allocated by the state.

Definition at line 2041 of file cm.cpp.

Referenced by cm_query_result().

◆ cm_state_init()

static struct cm_state* cm_state_init	(	struct city *	pcity,
		const cm_parameter *	param,
		bool	negative_ok
	)

static

Initialize the state for the branch-and-bound algorithm.

Definition at line 1842 of file cm.cpp.

Referenced by cm_query_result().

◆ compare_tile_type_by_fitness()

static int compare_tile_type_by_fitness	(	const void *	va,
		const void *	vb
	)

static

Sort by fitness.

Since fitness is monotone in the production, if a has higher fitness than b, then a cannot be a child of b, so this respects the partial order – unless a and b have equal fitness. In that case, use compare_tile_type_by_lattice_order.

Definition at line 835 of file cm.cpp.

Referenced by sort_lattice_by_fitness().

◆ compare_tile_type_by_lattice_order()

static int compare_tile_type_by_lattice_order	(	const struct cm_tile_type *	a,
		const struct cm_tile_type *	b
	)

static

Compare functions to allow sorting lattice vectors.

All the sorting in this code needs to respect the partial order in the lattice: if a is a parent of b, then a must sort before b. This routine enforces that relatively cheaply (without looking through the worse_types vectors of a and b), but requires that lattice_depth has already been computed.

Definition at line 803 of file cm.cpp.

Referenced by compare_tile_type_by_fitness(), and compare_tile_type_by_stat().

◆ compare_tile_type_by_stat()

static int compare_tile_type_by_stat	(	const void *	va,
		const void *	vb
	)

static

Compare by the production of type compare_key.

If a produces more food than b, then a cannot be a child of b, so this respects the partial order – unless a and b produce equal food. In that case, use compare_tile_type_by_lattice_order.

Definition at line 867 of file cm.cpp.

Referenced by cm_state_init().

◆ complete_solution()

static void complete_solution	(	struct partial_solution *	soln,
		const struct cm_state *	state,
		const struct tile_type_vector *	lattice
	)

static

Complete the solution by choosing tiles in order off the given tile lattice.

Definition at line 1488 of file cm.cpp.

Referenced by compute_max_stats_heuristic().

◆ compute_fitness()

static struct cm_fitness compute_fitness	(	const int	surplus[],
		bool	disorder,
		bool	happy,
		const struct cm_parameter *	parameter
	)

static

Compute the fitness of the given surplus (and disorder/happy status) according to the weights and minimums given in the parameter.

Definition at line 541 of file cm.cpp.

Referenced by convert_solution_to_result().

◆ compute_max_stats_heuristic()

static void compute_max_stats_heuristic	(	const struct cm_state *	state,
		const struct partial_solution *	soln,
		int	production[],
		int	check_choice,
		bool	negative_ok
	)

static

The heuristic: A partial solution cannot produce more food than the amount of food it currently generates plus then placing all its workers on the best food tiles.

Similarly with all the other stats. If we take the max along each production, and it's not better than the best in at least one stat, the partial solution isn't worth anything.

This function computes the max-stats produced by a partial solution.

Definition at line 1568 of file cm.cpp.

Referenced by choice_is_promising().

◆ compute_tile_production()

static void compute_tile_production	(	const struct city *	pcity,
		const struct tile *	ptile,
		bool	is_celebrating,
		struct cm_tile_type *	out
	)

static

Compute the tile-type lattice.

Compute the production of tile [x,y] and stuff it into the tile type. Doesn't touch the other fields.

Definition at line 905 of file cm.cpp.

Referenced by init_tile_lattice().

◆ convert_solution_to_result()

static void convert_solution_to_result	(	struct cm_state *	state,
		const struct partial_solution *	soln,
		std::unique_ptr< cm_result > &	result
	)

static

Convert the solution into a cm_result.

This is a fairly expensive operation.

Definition at line 768 of file cm.cpp.

Referenced by cm_find_best_solution().

◆ copy_partial_solution()

static void copy_partial_solution	(	struct partial_solution *	dst,
		const struct partial_solution *	src,
		const struct cm_state *	state
	)

static

Copy the source solution into the destination one (the destination solution must already be allocated).

Definition at line 636 of file cm.cpp.

Referenced by bb_next(), and compute_max_stats_heuristic().

◆ destroy_partial_solution()

static void destroy_partial_solution ( struct partial_solution * into )

static

Free all storage associated with the solution.

This is basically the opposite of init_partial_solution().

Definition at line 626 of file cm.cpp.

Referenced by begin_search(), cm_state_free(), and compute_max_stats_heuristic().

◆ end_search()

static void end_search ( struct cm_state * state )

static

Clean up after a search.

Currently, does nothing except stop the timer and output.

Definition at line 2024 of file cm.cpp.

Referenced by cm_find_best_solution().

◆ estimate_fitness()

static double estimate_fitness	(	const struct cm_state *	state,
		const int	production[]
	)

static

Estimate the fitness of a tile.

Tiles are put into the lattice in fitness order, so that we start off choosing better tiles. The estimate MUST be monotone in the inputs; if it isn't, then the BB algorithm will fail.

The only fields of the state used are the city and parameter.

Definition at line 1747 of file cm.cpp.

Referenced by sort_lattice_by_fitness().

◆ evaluate_solution()

static struct cm_fitness evaluate_solution	(	struct cm_state *	state,
		const struct partial_solution *	soln
	)

static

Compute the fitness of the solution.

This is a fairly expensive operation.

Definition at line 714 of file cm.cpp.

Referenced by bb_next().

◆ fitness_better()

static bool fitness_better	(	struct cm_fitness	a,
		struct cm_fitness	b
	)

static

Return TRUE iff fitness A is strictly better than fitness B.

Definition at line 541 of file cm.cpp.

Referenced by bb_next().

◆ get_city_surplus()

static void get_city_surplus	(	const struct city *	pcity,
		int	surplus[],
		bool *	disorder,
		bool *	happy
	)

static

Convert the city's surplus numbers into an array.

Get the happy/disorder values, too. This fills in the surplus array and disorder and happy values based on the city's data.

Definition at line 714 of file cm.cpp.

Referenced by cm_result_copy().

◆ get_tax_rates()

static void get_tax_rates	(	const struct player *	pplayer,
		int	rates[]
	)

static

Get the national budget, see city.c.

Definition at line 1717 of file cm.cpp.

Referenced by cm_state_init(), and estimate_fitness().

◆ init_min_production()

static void init_min_production ( struct cm_state * state )

static

Initialize minimal production needed to be sufficient.

Definition at line 1699 of file cm.cpp.

Referenced by begin_search().

◆ init_partial_solution()

static void init_partial_solution	(	struct partial_solution *	into,
		int	ntypes,
		int	idle,
		bool	negative_ok
	)

static

Allocate and initialize an empty solution.

Definition at line 607 of file cm.cpp.

Referenced by begin_search(), cm_state_init(), and compute_max_stats_heuristic().

◆ init_specialist_lattice_nodes()

static void init_specialist_lattice_nodes	(	struct cm_state *	state,
		const struct city *	pcity
	)

static

Create lattice nodes for each type of specialist.

This adds a new tile_type for each specialist type.

Definition at line 976 of file cm.cpp.

Referenced by init_tile_lattice().

◆ init_tile_lattice()

static void init_tile_lattice	(	struct city *	pcity,
		struct cm_state *	state
	)

static

Create the lattice.

Definition at line 1201 of file cm.cpp.

Referenced by cm_state_init().

◆ last_choice()

static int last_choice ( struct cm_state * state )

static

Return the last choice in the stack.

Definition at line 1260 of file cm.cpp.

Referenced by pop_choice(), take_child_choice(), and take_sibling_choice().

◆ min_food_surplus_for_fastest_growth()

static int min_food_surplus_for_fastest_growth ( struct cm_state * state )

static

Find the minimum food surplus needed to grow in the fewest number of turns.

Definition at line 1938 of file cm.cpp.

Referenced by begin_search().

◆ next_choice()

static int next_choice	(	struct cm_state *	state,
		int	oldchoice,
		bool	negative_ok
	)

static

Return the next choice to make after oldchoice.

A choice can be made if:

we haven't used all the tiles
we've used up all the better tiles
using that choice, we have a hope of doing better than the best solution so far. If oldchoice == -1 then we return the first possible choice.

Definition at line 1387 of file cm.cpp.

Referenced by take_child_choice(), and take_sibling_choice().

◆ num_types()

static int num_types ( const struct cm_state * state )

static

Return the number of different tile types.

There is one tile type for each type specialist, plus one for each distinct (different amounts of production) citymap tile.

Definition at line 1272 of file cm.cpp.

Referenced by apply_solution(), begin_search(), complete_solution(), compute_max_stats_heuristic(), copy_partial_solution(), next_choice(), specialists_in_solution(), take_child_choice(), and take_sibling_choice().

◆ operator==()

bool operator==	(	const struct cm_parameter &	p1,
		const struct cm_parameter &	p2
	)

Definition at line 2129 of file cm.cpp.

◆ pop_choice()

static void pop_choice ( struct cm_state * state )

static

Remove a worker from the current solution, and pop once off the choice stack.

Definition at line 1359 of file cm.cpp.

Referenced by bb_next().

◆ prereqs_filled()

static bool prereqs_filled	(	const struct partial_solution *	soln,
		int	type,
		const struct cm_state *	state
	)

static

True if all tiles better than this type have been used.

Definition at line 1369 of file cm.cpp.

Referenced by complete_solution(), and next_choice().

◆ remove_worker()

static void remove_worker	(	struct partial_solution *	soln,
		int	itype,
		const struct cm_state *	state
	)

static

Remove just one worker from the solution.

Definition at line 1349 of file cm.cpp.

Referenced by pop_choice(), and take_sibling_choice().

◆ sort_lattice_by_fitness()

static void sort_lattice_by_fitness	(	const struct cm_state *	state,
		struct tile_type_vector *	lattice
	)

static

Determine the estimated_fitness fields, and sort by that.

estimate_fitness is later, in a section of code that isolates much of the domain-specific knowledge.

Definition at line 1173 of file cm.cpp.

Referenced by begin_search().

◆ specialists_in_solution()

static int specialists_in_solution	(	const struct cm_state *	state,
		const struct partial_solution *	soln
	)

static

Return number of specialists used in partial solution.

Definition at line 1542 of file cm.cpp.

Referenced by choice_is_promising().

◆ take_child_choice()

static bool take_child_choice	(	struct cm_state *	state,
		bool	negative_ok
	)

static

Go down from the current branch, if we can.

Thanks to the fact that the lattice is sorted by depth, we can keep the choice stack sorted – that is, we can start our next choice as last_choice - 1. This keeps us from trying out all permutations of the same combination.

Definition at line 1454 of file cm.cpp.

Referenced by bb_next().

◆ take_sibling_choice()

static bool take_sibling_choice	(	struct cm_state *	state,
		bool	negative_ok
	)

static

Pick a sibling choice to the last choice.

This works down the branch to see if a choice that actually looks worse may actually be better.

Definition at line 1426 of file cm.cpp.

Referenced by bb_next().

◆ tile_get()

static const struct cm_tile* tile_get	(	const struct cm_tile_type *	ptype,
		int	j
	)

static

Retrieve a tile of a particular type by index.

For a given tile type there are a certain number of tiles (1 or more), which may be iterated over using this function for index. Don't call this for is_specialist types. See also tile_type_num_tiles().

Definition at line 524 of file cm.cpp.

Referenced by apply_solution().

◆ tile_type_better()

static bool tile_type_better	(	const struct cm_tile_type *	a,
		const struct cm_tile_type *	b
	)

static

Return TRUE if tile a is better or equal to tile b in all categories.

Specialists are considered better than workers (all else being equal) since we have an unlimited number of them.

Definition at line 433 of file cm.cpp.

Referenced by tile_type_lattice_add().

◆ tile_type_destroy()

static void tile_type_destroy ( struct cm_tile_type * type )

static

Free all the storage in the tile type (but don't free the type itself).

Definition at line 382 of file cm.cpp.

Referenced by tile_type_vector_free_all().

◆ tile_type_dup()

static struct cm_tile_type* tile_type_dup ( const struct cm_tile_type * oldtype )

static

Duplicate a tile type, except for the vectors - the vectors of the new tile type will be empty.

Definition at line 367 of file cm.cpp.

Referenced by tile_type_lattice_add().

◆ tile_type_equal()

static bool tile_type_equal	(	const struct cm_tile_type *	a,
		const struct cm_tile_type *	b
	)

static

Return TRUE iff all categories of the two types are equal.

This means all production outputs are equal and the is_specialist fields are also equal.

Definition at line 413 of file cm.cpp.

Referenced by tile_type_vector_find_equivalent().

◆ tile_type_get()

static const struct cm_tile_type* tile_type_get	(	const struct cm_state *	state,
		int	type
	)

static

Retrieve a tile type by index.

For a given state there are a certain number of tile types, which may be iterated over using this function as a lookup.

Definition at line 508 of file cm.cpp.

Referenced by add_workers(), apply_solution(), compute_max_stats_heuristic(), next_choice(), prereqs_filled(), and specialists_in_solution().

◆ tile_type_init()

static void tile_type_init ( struct cm_tile_type * type )

static

Set all production to zero and initialize the vectors for this tile type.

Definition at line 355 of file cm.cpp.

Referenced by init_specialist_lattice_nodes(), and init_tile_lattice().

◆ tile_type_lattice_add()

static void tile_type_lattice_add	(	struct tile_type_vector *	lattice,
		const struct cm_tile_type *	newtype,
		int	tindex
	)

static

Add the tile [x,y], with production indicated by type, to the tile-type lattice.

'newtype' can be on the stack. x/y are ignored if the type is a specialist. If the type is new, it is linked in and the lattice_index set. The lattice_depth is not set.

Definition at line 924 of file cm.cpp.

Referenced by init_specialist_lattice_nodes(), and init_tile_lattice().

◆ tile_type_num_prereqs()

static int tile_type_num_prereqs ( const struct cm_tile_type * ptype )

static

Return the number of tile types that are better than this type.

Note this isn't the same as the number of tiles that are better. There may be more than one tile of each type (see tile_type_num_tiles).

Definition at line 498 of file cm.cpp.

Referenced by add_workers(), prereqs_filled(), and top_sort_lattice().

◆ tile_type_num_tiles()

static int tile_type_num_tiles ( const struct cm_tile_type * type )

static

Return the number of tiles of this type that can be worked.

For is_specialist types this will always be infinite but for other types of tiles it is limited by what's available in the citymap.

Definition at line 483 of file cm.cpp.

Referenced by add_workers(), complete_solution(), and top_sort_lattice().

◆ tile_type_vector_find_equivalent()

static int tile_type_vector_find_equivalent	(	const struct tile_type_vector *	vec,
		const struct cm_tile_type *	ptype
	)

static

If there is a tile type in the vector that is equivalent to the given type, return its index.

If not, return -1.

Equivalence is defined in tile_type_equal().

Definition at line 464 of file cm.cpp.

Referenced by tile_type_lattice_add().

◆ tile_type_vector_free_all()

static void tile_type_vector_free_all ( struct tile_type_vector * vec )

static

Destroy and free all types in the vector, and the vector itself.

This will free all memory associated with the vector.

Definition at line 395 of file cm.cpp.

Referenced by clean_lattice(), and cm_state_free().

◆ top_sort_lattice()

static void top_sort_lattice ( struct tile_type_vector * lattice )

static

Topologically sort the lattice.

Sets the lattice_depth field. Important assumption in this code: we've computed the transitive closure of the lattice. That is, better_types includes all types that are better.

Definition at line 1014 of file cm.cpp.

Referenced by init_tile_lattice().

◆ worst_fitness()

static struct cm_fitness worst_fitness ( )

static

Return a fitness struct that is the worst possible result we can represent.

Definition at line 541 of file cm.cpp.

Referenced by begin_search(), and cm_state_init().

Variable Documentation

◆ compare_key

Output_type_id compare_key

static

Definition at line 858 of file cm.cpp.

Referenced by cm_state_init(), and compare_tile_type_by_stat().

◆ compare_key_trade_bonus

double compare_key_trade_bonus

static

Definition at line 859 of file cm.cpp.

Referenced by cm_state_init(), and compare_tile_type_by_stat().

Classes

Macros

Functions

Variables

Detailed Description

Terms used

Macro Definition Documentation

◆ CM_MAX_LOOP

◆ CPUHOG_CM_MAX_LOOP

◆ LOG_BETTER_LEAF

◆ LOG_CM_STATE

◆ LOG_LATTICE

◆ LOG_PRUNE_BRANCH

◆ LOG_REACHED_LEAF

◆ LOG_TIME_STATS

◆ print_lattice

◆ print_partial_solution

◆ print_tile_type

◆ PRINT_TIME_STATS_EVERY_QUERY

◆ SPECVEC_TAG [1/2]

◆ SPECVEC_TAG [2/2]

◆ SPECVEC_TYPE [1/2]

◆ SPECVEC_TYPE [2/2]

◆ tile_type_vector_iterate

◆ tile_type_vector_iterate_end

Function Documentation

◆ add_worker()

◆ add_workers()

◆ apply_solution()

◆ bb_next()

◆ begin_search()

◆ choice_is_promising()

◆ choice_stack_empty()

◆ clean_lattice()

◆ cm_copy_parameter()

◆ cm_find_best_solution()

◆ cm_free()

◆ cm_init()

◆ cm_init_citymap()

◆ cm_init_emergency_parameter()

◆ cm_init_parameter()

◆ cm_print_city()

◆ cm_print_result()

◆ cm_query_result()

◆ cm_result_citizens()

◆ cm_result_copy()

◆ cm_result_from_main_map()

◆ cm_result_new()

◆ cm_result_specialists()

◆ cm_result_workers()

◆ cm_state_free()

◆ cm_state_init()

◆ compare_tile_type_by_fitness()

◆ compare_tile_type_by_lattice_order()

◆ compare_tile_type_by_stat()

◆ complete_solution()

◆ compute_fitness()

◆ compute_max_stats_heuristic()

◆ compute_tile_production()

◆ convert_solution_to_result()

◆ copy_partial_solution()

◆ destroy_partial_solution()

◆ end_search()

◆ estimate_fitness()

◆ evaluate_solution()

◆ fitness_better()

◆ get_city_surplus()

◆ get_tax_rates()

◆ init_min_production()

◆ init_partial_solution()

◆ init_specialist_lattice_nodes()

◆ init_tile_lattice()

◆ last_choice()

◆ min_food_surplus_for_fastest_growth()

◆ next_choice()

◆ num_types()

◆ operator==()

◆ pop_choice()

◆ prereqs_filled()

◆ remove_worker()