diff options
author | Tom Harley | 2019-01-24 12:10:15 +0000 |
---|---|---|
committer | Tom Harley | 2019-01-24 12:10:15 +0000 |
commit | 1ef39e9ba6ce1a622c53f38929d1e77b4f2518fc (patch) | |
tree | 7734126b8b4c2bd9f97d45137cf73c83fdf8c829 | |
parent | wow a thing that works (diff) | |
download | metasol-1ef39e9ba6ce1a622c53f38929d1e77b4f2518fc.tar.gz metasol-1ef39e9ba6ce1a622c53f38929d1e77b4f2518fc.zip |
It works with fortune’s favor
It seems to be consistently running to completion successfully! It’s been renamed to metasol
for now, since that’s a better name than test
. Next step will probably be eliminating the namespace pollution in metasol.cpp
.
-rw-r--r-- | .gitignore | 4 | ||||
-rw-r--r-- | Makefile | 25 | ||||
-rw-r--r-- | metasol.cpp | 1119 | ||||
-rw-r--r-- | src/main/api.cpp | 30 | ||||
-rw-r--r-- | src/main/api.h | 16 | ||||
-rw-r--r-- | src/main/game/search-state/game_state.cpp | 30 | ||||
-rw-r--r-- | src/main/game/search-state/game_state.h | 4 | ||||
-rw-r--r-- | src/main/solver/solver.cpp | 2 | ||||
-rw-r--r-- | test.cpp | 120 |
9 files changed, 1222 insertions, 128 deletions
@@ -1,3 +1,7 @@ +*.o +*.d +metasol + ######### # CLion # ######### diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..6602f8b --- /dev/null +++ b/Makefile @@ -0,0 +1,25 @@ +LINK.o = $(LINK.cc) +CXXFLAGS = -ggdb3 -O0 -pedantic -Wall -Werror #-DNOTHREAD +LDFLAGS = -ggdb3 -O0 -Lcmake-build-release #-DNOTHREAD + +OUTPUT_OPTION = -MMD -MP -o $@ +LDLIBS = -lapi -lpthread + +TRGT = metasol +SRC = metasol.cpp +OBJ = $(SRC:.cpp=.o) +DEP = $(SRC:.cpp=.d) + +.PHONY: default all run + +default: all +all: $(TRGT) +$(TRGT): $(OBJ) + +run: $(TRGT) + ./$< + +-include $(DEP) + +clean: + $(RM) $(TRGT) $(OBJ) $(DEP) diff --git a/metasol.cpp b/metasol.cpp new file mode 100644 index 0000000..822b948 --- /dev/null +++ b/metasol.cpp @@ -0,0 +1,1119 @@ +#include <algorithm> +#include <cstdint> +#include <cstdio> +#include <iostream> +#include <random> +#include <string> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/mman.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <unistd.h> +#include <math.h> +#include <pthread.h> + +#include "src/main/api.h" + +#ifndef NDEBUG +# define debug(...) fprintf(stderr, __VA_ARGS__) +#else +# define debug(...) +#endif + +enum build_policy_t { + NO_BUILD, BUILD_SAME_SUIT, BUILD_ALTERNATING, BUILD_ANY +}; + +sol_rules::build_policy convert_build_policy(build_policy_t bp) { + switch (bp) { + case NO_BUILD: return sol_rules::build_policy::NO_BUILD; + case BUILD_SAME_SUIT: return sol_rules::build_policy::SAME_SUIT; + case BUILD_ALTERNATING: return sol_rules::build_policy::RED_BLACK; + case BUILD_ANY: return sol_rules::build_policy::ANY_SUIT; + default: assert(false); + } +} + +enum spaces_policy_t { + NO_SPACE_FILL, KINGS_FILL_SPACE, ANY_FILL_SPACE, AUTO_RESERVE_THEN_WASTE, + AUTO_WASTE_THEN_STOCK +}; + +sol_rules::spaces_policy convert_spaces_policy(spaces_policy_t sp) { + switch (sp) { + case NO_SPACE_FILL: + return sol_rules::spaces_policy::NO_BUILD; + case KINGS_FILL_SPACE: + return sol_rules::spaces_policy::KINGS; + case ANY_FILL_SPACE: + return sol_rules::spaces_policy::ANY; + case AUTO_RESERVE_THEN_WASTE: + return sol_rules::spaces_policy::AUTO_RESERVE_THEN_WASTE; + case AUTO_WASTE_THEN_STOCK: + return sol_rules::spaces_policy::AUTO_WASTE_THEN_STOCK; + default: assert(false); + } +} + +enum accordion_policy_t { + ACCORDION_SAME_RANK, ACCORDION_SAME_SUIT, ACCORDION_ALTERNATE_COLOUR, + ACCORDION_ANY_SUIT +}; + +sol_rules::accordion_policy convert_accordion_policy(accordion_policy_t ap) { + switch (ap) { + case ACCORDION_SAME_RANK: + return sol_rules::accordion_policy::SAME_RANK; + case ACCORDION_SAME_SUIT: + return sol_rules::accordion_policy::SAME_SUIT; + case ACCORDION_ALTERNATE_COLOUR: + return sol_rules::accordion_policy::RED_BLACK; + case ACCORDION_ANY_SUIT: + return sol_rules::accordion_policy::ANY_SUIT; + default: assert(false); + } +} + +enum stock_deal_t { + STOCK_TO_WASTE, STOCK_TO_TABLEAU +}; + +sol_rules::stock_deal_type convert_stock_deal(stock_deal_t sd) { + switch (sd) { + case STOCK_TO_WASTE: return sol_rules::stock_deal_type::WASTE; + case STOCK_TO_TABLEAU: return sol_rules::stock_deal_type::TABLEAU_PILES; + default: assert(false); + } +} + +enum face_up_policy_t { + ALL_CARDS_FACE_UP, TOP_CARDS_FACE_UP +}; + +sol_rules::face_up_policy convert_face_up_policy(face_up_policy_t fup) { + switch (fup) { + case ALL_CARDS_FACE_UP: return sol_rules::face_up_policy::ALL; + case TOP_CARDS_FACE_UP: return sol_rules::face_up_policy::TOP_CARDS; + default: assert(false); + } +} + +enum direction_t { + LEFT, RIGHT, BOTH +}; + +sol_rules::direction convert_direction(direction_t d) { + switch (d) { + case LEFT: return sol_rules::direction::LEFT; + case RIGHT: return sol_rules::direction::RIGHT; + case BOTH: return sol_rules::direction::BOTH; + default: assert(false); + } +} + +enum built_group_t { + CAN_MOVE_BUILT_GROUP, CANNOT_MOVE_BUILT_GROUP, CAN_MOVE_WHOLE_PILE, + CAN_MOVE_MAXIMAL_GROUP +}; + +sol_rules::built_group_type convert_built_group(built_group_t bg) { + switch (bg) { + case CAN_MOVE_BUILT_GROUP: + return sol_rules::built_group_type::YES; + case CANNOT_MOVE_BUILT_GROUP: + return sol_rules::built_group_type::NO; + case CAN_MOVE_WHOLE_PILE: + return sol_rules::built_group_type::WHOLE_PILE; + case CAN_MOVE_MAXIMAL_GROUP: + return sol_rules::built_group_type::MAXIMAL_GROUP; + default: assert(false); + } +} + +enum foundations_init_t { + NO_FOUNDATION_INIT, ONE_FOUNDATION_INIT, ALL_FOUNDATIONS_INIT +}; + +sol_rules::foundations_init_type convert_foundations_init( + foundations_init_t fi) { + switch (fi) { + case NO_FOUNDATION_INIT: + return sol_rules::foundations_init_type::NONE; + case ONE_FOUNDATION_INIT: + return sol_rules::foundations_init_type::ONE; + case ALL_FOUNDATIONS_INIT: + return sol_rules::foundations_init_type::ALL; + default: assert(false); + } +} + +typedef card::suit_t card_suit; +typedef card::rank_t card_rank; + +typedef struct srules { + unsigned tableau_size; + build_policy_t build_policy; + spaces_policy_t spaces_policy; + built_group_t move_built_group; + build_policy_t built_group_policy; + unsigned deck_count; + unsigned max_rank; + bool hole_present; + bool foundations_present; + foundations_init_t foundations_init_cards; + bool specific_foundations_base; + card_rank foundations_base; + bool foundations_removable; + bool foundations_only_comp_piles; + bool diagonal_deal; + unsigned cells; + unsigned cells_pre_filled; + unsigned stock_size; + stock_deal_t stock_deal_method; + unsigned stock_deal_count; + bool stock_redeal; + unsigned reserve_size; + bool reserve_stacked; + face_up_policy_t face_up_policy; + unsigned sequence_count; + direction_t sequence_direction; + build_policy_t sequence_build_policy; + bool sequence_fixed_suit; + unsigned accordion_size; + std::vector<std::pair<direction_t, int>> accordion_moves; + std::vector<accordion_policy_t> accordion_policy; +} srules; + +sol_rules srules_rules(srules *sr) { + sol_rules r; + + r.tableau_pile_count = sr->tableau_size; + r.build_pol = convert_build_policy(sr->build_policy); + r.spaces_pol = convert_spaces_policy(sr->spaces_policy); + r.move_built_group = convert_built_group(sr->move_built_group); + r.built_group_pol = convert_build_policy(sr->built_group_policy); + r.max_rank = sr->max_rank; + r.hole = sr->hole_present; + r.foundations_present = sr->foundations_present; + r.foundations_init_cards = + convert_foundations_init(sr->foundations_init_cards); + r.foundations_removable = sr->foundations_removable; + r.foundations_only_comp_piles = sr->foundations_only_comp_piles; + r.diagonal_deal = sr->diagonal_deal; + r.cells = sr->cells; + r.cells_pre_filled = sr->cells_pre_filled; + r.stock_size = sr->stock_size; + r.stock_deal_t = convert_stock_deal(sr->stock_deal_method); + r.stock_deal_count = sr->stock_deal_count; + r.stock_redeal = sr->stock_redeal; + r.reserve_size = sr->reserve_size; + r.reserve_stacked = sr->reserve_stacked; + r.face_up = convert_face_up_policy(sr->face_up_policy); + r.sequence_count = sr->sequence_count; + r.sequence_direction = convert_direction(sr->sequence_direction); + r.sequence_build_pol = convert_build_policy(sr->sequence_build_policy); + r.sequence_fixed_suit = sr->sequence_fixed_suit; + r.accordion_size = sr->accordion_size; + + assert(sr->deck_count <= 2); + r.two_decks = sr->deck_count == 2; + + if (sr->specific_foundations_base) + r.foundations_base = sr->foundations_base; + else + r.foundations_base = boost::optional<card::rank_t>{}; + + for (auto &p : sr->accordion_moves) + r.accordion_moves.push_back(std::pair<sol_rules::direction, uint8_t> + (convert_direction(p.first), p.second)); + + for (auto &x : sr->accordion_policy) + r.accordion_pol.push_back(convert_accordion_policy(x)); + + return r; +} + +typedef struct scard { + card_suit suit; + card_rank rank; + bool hidden; +} scard; + +typedef std::vector<scard> scard_pile; + +typedef struct sgame_state { + std::vector<scard_pile> foundations; + scard_pile stock; + scard_pile waste; + std::vector<scard_pile> tableau; + scard_pile hole; + std::vector<scard_pile> cells; +} sgame_state; + +typedef struct smove { + bool stock; + scard_pile *to; + scard_pile *from; +} smove; + +typedef finished_state thoughtful_run_func_t(sgame_state *, + srules *, void *); +typedef finished_state run_func_t(sgame_state *, srules *, smove *, + unsigned, void *); + +typedef struct settings { + run_func_t *run_func; + thoughtful_run_func_t *thoughtful_run_func; + std::size_t move_size; + unsigned reserved_move_count; + void *user_data; +} settings; + +settings fetch_default_settings() { + settings s; + s.run_func = NULL; + s.thoughtful_run_func = NULL; + s.move_size = 0u; + s.reserved_move_count = 1u; + s.user_data = NULL; + return s; +} + +settings DEFAULT_SETTINGS = fetch_default_settings(); + +typedef std::vector<std::string> card_pile; + +std::string SUITS[4] = { "S", "C", "D", "H" }; +std::string RANKS[13] = { + "A", "2", "3", "4", "5", "6", "7", "8", "9", "X", "J", "Q", "K" +}; + +card_pile& make_deck(card_pile& space, int deck_count); +card_pile& make_deck(card_pile& space, int deck_count = 1) { + space.clear(); + for (int i = 0; i < deck_count; ++i) { + for (std::string suit : SUITS) { + for (std::string rank : RANKS) { + space.push_back(rank + suit); + } + } + } + return space; +} + +std::random_device rd; +auto rng = std::default_random_engine{rd()}; +card_pile& shuffle(card_pile& cards) { + std::shuffle(std::begin(cards), std::end(cards), rng); + return cards; +} + +std::vector<card_pile>& split(card_pile& in, std::vector<card_pile>& out, + std::vector<std::size_t> numbers) { + out.clear(); + out.resize(numbers.size()); + + std::size_t acc = 0; + auto i = 0; + for (auto& n : numbers) { + card_pile cp(in.begin() + acc, in.begin() + acc + n); + out[i] = cp; + acc += n; + ++i; + } + + assert(acc == in.size()); + return out; +} + +std::vector<card_pile>& split_even(card_pile& in, std::vector<card_pile>& out, + std::size_t n_piles); +std::vector<card_pile>& split_even(card_pile& in, std::vector<card_pile>& out, + std::size_t n_piles) { + std::vector<std::size_t> nums; + + auto t = in.size(); + for (int i = 0; i < (int)in.size(); ++i) { + auto w = t / (n_piles - i); + nums.push_back(w); + t -= w; + } + + return split(in, out, nums); +} + +card_rank char_rank(char c) { + switch (c) { + case 'A': case 'a': case '1': return 1u; + case '2': return 2u; + case '3': return 3u; + case '4': return 4u; + case '5': return 5u; + case '6': return 6u; + case '7': return 7u; + case '8': return 8u; + case '9': return 9u; + case 'X': case 'x': case 'T': case 't': case '0': return 10u; + case 'J': case 'j': return 11u; + case 'Q': case 'q': return 12u; + case 'K': case 'k': return 13u; + default: assert(false); + } +} + +card_suit char_suit(char c) { + switch (c) { + case 'H': case 'h': return card::suit::Hearts; + case 'S': case 's': return card::suit::Spades; + case 'C': case 'c': return card::suit::Clubs; + case 'D': case 'd': return card::suit::Diamonds; + default: assert(false); + } +} + +char rank_char(std::uint8_t rank) { + switch (rank) { + case 1: return 'A'; + case 2: return '2'; + case 3: return '3'; + case 4: return '4'; + case 5: return '5'; + case 6: return '6'; + case 7: return '7'; + case 8: return '8'; + case 9: return '9'; + case 10: return 'X'; + case 11: return 'J'; + case 12: return 'Q'; + case 13: return 'K'; + } + + assert(false); +} + +std::string rank_compat_str(card_rank rank) { + switch (rank) { + case 1: return "A"; + case 2: return "2"; + case 3: return "3"; + case 4: return "4"; + case 5: return "5"; + case 6: return "6"; + case 7: return "7"; + case 8: return "8"; + case 9: return "9"; + case 10: return "10"; + case 11: return "J"; + case 12: return "Q"; + case 13: return "K"; + } + + assert(false); +} + +char suit_char(card_suit s) { + if (s == card::suit::Hearts ) return 'H'; + else if (s == card::suit::Spades ) return 'S'; + else if (s == card::suit::Clubs ) return 'C'; + else if (s == card::suit::Diamonds) return 'D'; + + assert(false); +} + +scard str_scard(std::string str) { + scard card; + card.suit = char_suit(str[1]); + card.rank = char_rank(str[0]); + card.hidden = true; + return card; +} + +bool strs_scards(card_pile &cp, scard_pile &out) { + std::transform(cp.begin(), cp.end(), out.begin(), str_scard); + return true; +} + +std::string scard_compat_str(scard &c) { + std::string rank_str = rank_compat_str(c.rank); + char suit_c = suit_char(c.suit); + return rank_str + suit_c; +} + +int scard_str(scard *c, char *buf) { + char rank_c = rank_char(c->rank); + char suit_c = suit_char(c->suit); + buf[0] = rank_c; + buf[1] = suit_c; + buf[2] = '\0'; + return 0; +} + +void add_hidden(scard *c, std::vector<scard *> &cs) { + if (c->hidden) cs.push_back(c); +} + +/** + * Fills a vector with pointers to all hidden cards in the given game state. + */ +int get_hidden_cards(sgame_state *gs, std::vector<scard *> &cs) { + for (scard &c : gs->stock) add_hidden(&c, cs); + for (scard &c : gs->waste) add_hidden(&c, cs); + /* for (scard &c : gs->reserve) add_hidden(&c, cs); */ + + for (scard_pile &p : gs->foundations) + for (scard &c : p) + add_hidden(&c, cs); + for (auto &p : gs->tableau) + for (auto &c : p) + add_hidden(&c, cs); + + return cs.size(); +} + +bool moves_equal(move &a, move &b) { + bool res = a.from == b.from + && a.to == b.to + && a.count == b.count; + + if (res) { + // if the above values are the same, + // the following values are necessarily equal: + assert(a.reveal_move == b.reveal_move); + assert(a.flip_waste == b.flip_waste); + } + + return res; +} + +typedef std::vector<movelist> paths; +typedef std::vector<paths> grouped_paths; + +/* + * Returns false if no place to put new path + */ +bool add_group_by_first_move(grouped_paths &groups, movelist &path) { + assert(!path.empty()); + + bool found = false; + for (auto &group : groups) { + movelist first = group[0]; + assert(!first.empty()); + + if (group.empty() || moves_equal(path[0], first[0])) { + group.push_back(path); + found = true; + break; + } + } + + return found; +} + +char const *mtype_str(move::mtype t) { + switch (t) { + case move::mtype::regular: return "regular"; + case move::mtype::dominance: return "dominance"; + case move::mtype::built_group: return "built group"; + case move::mtype::stock_k_plus: return "stock k+"; + case move::mtype::stock_to_all_tableau: return "stock-tableau"; + case move::mtype::sequence: return "sequence"; + case move::mtype::accordion: return "accordion"; + case move::mtype::null: return "null(!)"; + default: assert(false); + } +} + +bool goes_through_stock(move *a) { + return a->type == move::mtype::stock_k_plus + && a->count != 0; +} + +void remove_cards(card_pile &cp, std::vector<std::string> cs) { + cp.erase(std::remove_if(cp.begin(), cp.end(), + [cs](std::string c){ + return std::find(cs.begin(), cs.end(), c) != cs.end(); + }), cp.end()); +} + +int sgs_pile(scard_pile &s, card_pile &p) { + p.resize(s.size()); + std::transform(s.begin(), s.end(), p.begin(), scard_compat_str); + + return 0; +} + +auto foundation_count(srules *r) { + if (r->foundations_present) { + return 4u * r->deck_count; + } else { + return 0u; + } +} + +auto total_pile_count(srules *r) { + return r->tableau_size + + (r->hole_present ? 1 : 0) + + foundation_count(r) + + r->cells + + (r->stock_size > 0 ? + (r->stock_deal_method == STOCK_TO_WASTE ? 2 : 1) : 0) + ; + + // TODO: I'm not sure how the reserve, sequence, or accordion work; + // research required! +} + +void do_pile(scard_pile *p, + std::vector<std::vector<card_suit>> *suits, + std::vector<std::vector<card_rank>> *ranks, + std::vector<std::vector<bool>> *face_down, + bool force_face_up = false) { + suits->push_back({}); + ranks->push_back({}); + face_down->push_back({}); + + for (auto &c : *p) { + suits->back().push_back(c.suit); + ranks->back().push_back(c.rank); + face_down->back().push_back(force_face_up ? false : c.hidden); + } +} + +void do_pile_set(std::vector<scard_pile> *set, + std::vector<std::vector<card_suit>> *suits, + std::vector<std::vector<card_rank>> *ranks, + std::vector<std::vector<bool>> *face_down, + bool force_face_up = false) { + for (auto &p : *set) { + do_pile(&p, suits, ranks, face_down, force_face_up); + } +} + +/* + * game_state pile creation order: + * 1. hole + * 2. 4 foundations (8 for two decks) + * 3. cell piles + * 4. stock + * 5. waste + * 6. reserve (maybe multiple?) + * 7. accordion piles + * 8. tableau piles + * 9. sequence piles + */ + +game_state sgs_gs(sgame_state *sgs, srules *r) { + std::vector<std::vector<card_suit>> suits; + std::vector<std::vector<card_rank>> ranks; + std::vector<std::vector<bool>> face_down; + + if (r->hole_present) { + do_pile(&sgs->hole, &suits, &ranks, &face_down); + } + + do_pile_set(&sgs->foundations, &suits, &ranks, &face_down); + do_pile_set(&sgs->cells, &suits, &ranks, &face_down); + if (r->stock_size) { + // solvitaire requires that the stock be entirely face-up + do_pile(&sgs->stock, &suits, &ranks, &face_down, true); + if (r->stock_deal_method == STOCK_TO_WASTE) { + do_pile(&sgs->waste, &suits, &ranks, &face_down); + } + } + // TODO: how does the reserve work? leaving empty for now + // TODO: how does the accordion work? leaving empty for now + do_pile_set(&sgs->tableau, &suits, &ranks, &face_down); + // TODO: how does the sequence work? leaving empty for now + + game_state gs(srules_rules(r), suits, ranks, face_down); + return gs; +} + +typedef struct user_data { + unsigned run_cache_size; + unsigned run_timeout; + unsigned thoughtful_run_timeout; +} user_data; + +void print_sgs(sgame_state *gs, srules *r) { + game_state solv_gs = sgs_gs(gs, r); + std::cerr << solv_gs << std::endl; +} + +int shuffle_hidden(sgame_state *gs) { + std::vector<scard *> hidden_card_pointers; + get_hidden_cards(gs, hidden_card_pointers); + + std::vector<scard> hidden_cards; + for (scard *p : hidden_card_pointers) + hidden_cards.push_back(*p); + + std::shuffle(hidden_cards.begin(), hidden_cards.end(), rng); + + for (typeof(hidden_cards.size()) i = 0; i < hidden_cards.size(); ++i) { + scard *cp = hidden_card_pointers[i]; + scard c = hidden_cards[i]; + *cp = c; + } + + return 0; +} + +bool is_dud_move(move *m) { + if (m->to == 255u && m->from == 255u) return true; + return false; +} + +scard_pile *get_pile_by_index(sgame_state *gs, uint8_t i) { + if (i < gs->foundations.size()) + return &gs->foundations[i]; + else + i -= gs->foundations.size(); + + if (i-- == 0) + return &gs->stock; + + if (i-- == 0) + return &gs->waste; + + assert (i < gs->tableau.size()); + return &gs->tableau[i]; +} + +int move_smove(sgame_state *gs, move *m, smove *sm) { + sm->stock = goes_through_stock(m); + + if (m->type == move::mtype::stock_k_plus) { + sm->from = &gs->waste; + } else { + sm->from = get_pile_by_index(gs, m->from); + } + + sm->to = get_pile_by_index(gs, m->to); + + return 0; +} + +/** + * The function that is called by every voter, to get its vote. + */ +finished_state run_single(sgame_state *gs, srules *r, + smove *first_move, unsigned move_count, void *data) { + // TODO: this function can't currently handle producing multiple moves at + // once + assert(move_count == 1u); + + user_data *d = (user_data *) data; + + game_state solv_gs = sgs_gs(gs, r); + + movelist ml; + finished_state result = get_moves(ml, solv_gs, d->run_cache_size, + d->run_timeout); + + if (result == SOLUTION_FOUND) { + if (!is_dud_move(&ml[0])) { + move_smove(gs, &ml[0], first_move); + } else { + move_smove(gs, &ml[1], first_move); + } + } + + return result; +} + +struct thread_info { + sgame_state *gs; + srules *r; + settings *s; + smove *move_buf; + finished_state *result; +}; + +void *run_thread(void *vargp) { + struct thread_info *ti = (struct thread_info *) vargp; + *ti->result = ti->s->run_func(ti->gs, ti->r, ti->move_buf, + ti->s->reserved_move_count, ti->s->user_data); + return NULL; +} + +// TODO: this shouldn't be implemented as an operator - it should be its own +// function. +bool operator< (const smove &a, const smove &b) { + // FIXME: if we want to group all moves that go through the stock together, + // it's necessary to make them "not less than" one another. + if (a.stock && b.stock) return false; + + if (a.from < b.from) return true; + if (a.from > b.from) return false; + if (a.to < b.to) return true; + return false; +} + +int intlen(int i) { + if (i == 0) return 1; + return floor(log10(abs(i))) + 1; +} + +void debug_pile(scard_pile *p) { + char buf[3]; + + for (auto c : *p) { + scard_str(&c, &buf[0]); + debug("%s ", &buf[0]); + } + + debug("\n"); +} + +char *debug_scard_buf(scard *c) { + static char buf[3]; + scard_str(c, &buf[0]); + return &buf[0]; +} + +int move_atop(scard_pile *f, scard_pile *t) { + scard c = f->back(); + debug("moving card %s\n", debug_scard_buf(&c)); + + f->pop_back(); + // XXX: I'm not 100% sure that face-down cards at the top of piles should be + // flipped face-up, but I'm going with it for now: + if (!f->empty()) + f->back().hidden = false; + + t->push_back(c); + + return 0; +} + +int go_through_stock(sgame_state *gs, int n) { + for (int i = 0; i < n; ++i) + move_atop(&gs->stock, &gs->waste); + + return 0; +} + +int make_move(sgame_state *gs, smove *m) { + if (m->stock) { + go_through_stock(gs, 1); + } else { + move_atop(m->from, m->to); + } + return 0; +} + +char const *finished_state_str(finished_state f) { + switch (f) { + case SOLUTION_FOUND: return "SOLUTION_FOUND"; + case NO_SOLUTION: return "NO_SOLUTION"; + case TIMEOUT: return "TIMEOUT"; + case SOLVER_OOM: return "SOLVER_OOM"; + case CANCELLED: return "CANCELLED"; + default: assert(false); + } +} + +const int MAX_VOTES = 100; +const int MIN_VOTES = 50; + +int total_piles(sgame_state *gs) { + int t = 0; + t += gs->foundations.size(); + t += 1; // stock + t += 1; // waste + t += gs->tableau.size(); + return t; +} + +void run_loop(sgame_state *gs, srules *r, settings *s, smove *votes, + finished_state *vote_results, pthread_t *votes_tid) { + struct thread_info t_infos[MAX_VOTES]; + +#ifdef NOTHREAD + for (int i = 0; i < MAX_VOTES; ++i) { + t_infos[i].gs = gs; + t_infos[i].r = r; + t_infos[i].s = s; + t_infos[i].move_buf = &votes[i]; + t_infos[i].result = &vote_results[i]; + + run_thread(&t_infos[i]); + } +#else + + for (int i = 0; i < MAX_VOTES; ++i) { + t_infos[i].gs = gs; + t_infos[i].r = r; + t_infos[i].s = s; + t_infos[i].move_buf = &votes[i]; + t_infos[i].result = &vote_results[i]; + + pthread_create(&votes_tid[i], NULL, &run_thread, &t_infos[i]); + } + + for (int i = 0; i < MAX_VOTES; ++i) + pthread_join(votes_tid[i], NULL); +#endif + + std::map<smove, int> tallied_votes; + for (int i = 0; i < MAX_VOTES; ++i) { + if (vote_results[i] == SOLUTION_FOUND) { + smove vote = votes[i]; + auto t = tallied_votes.find(vote); + if (t == tallied_votes.end()) { + tallied_votes[vote] = 1; + } else { + tallied_votes[vote] = t->second + 1; + } + } + } + + smove *max_move; + int max_votes = 0; + for (auto &v : tallied_votes) { + smove move = v.first; + int vote = v.second; + + if (vote > max_votes) { + max_move = &move; + max_votes = vote; + } + } + + if (max_votes == 0) { + debug("no votes cast!\n"); + std::map<finished_state, int> res; + + for (int i = 0; i < MAX_VOTES; ++i) { + finished_state f = vote_results[i]; + auto c = res.find(f); + res[f] = (c == res.end()) ? 1 : (c->second + 1); + } + + debug("results:\n"); + for (auto &p : res) { + debug("%s: %d\n", finished_state_str(p.first), p.second); + } + } else { + make_move(gs, max_move); + print_sgs(gs, r); + } +} + +bool solved(sgame_state *gs, srules *r) { + return sgs_gs(gs, r).is_solved(); +} + +finished_state thoughtful_run(sgame_state *gs, srules *r, + void *data) { + game_state solv_gs = sgs_gs(gs, r); + movelist ml; + return get_moves(ml, solv_gs, 1024u, 10000u); +} + +bool solvable(sgame_state *gs, srules *r, settings *s) { + finished_state fs = s->thoughtful_run_func(gs, r, s->user_data); + bool result = fs == SOLUTION_FOUND; + + if (result) { + debug("there is still a solution\n"); + } else { + debug("no solution left!\n"); + } + + return result; +} + +void run(sgame_state *gs, srules *r, settings *s) { + smove votes[MAX_VOTES]; + finished_state vote_results[MAX_VOTES]; + pthread_t votes_tid[MAX_VOTES]; + + while (!solved(gs, r)) { + if (s->thoughtful_run_func) { + if (!solvable(gs, r, s)) { + break; + } + } + + run_loop(gs, r, s, &votes[0], &vote_results[0], &votes_tid[0]); + } + print_sgs(gs, r); +} + +srules fetch_default_rules() { + srules dr; + + dr.tableau_size = 8u; + dr.build_policy = BUILD_ANY; + dr.spaces_policy = ANY_FILL_SPACE; + dr.diagonal_deal = false; + dr.move_built_group = CANNOT_MOVE_BUILT_GROUP; + dr.built_group_policy = dr.build_policy; + dr.face_up_policy = ALL_CARDS_FACE_UP; + dr.max_rank = 13u; + + dr.foundations_present = true; + dr.foundations_init_cards = NO_FOUNDATION_INIT; + dr.specific_foundations_base = true; + dr.foundations_base = 1u; + dr.foundations_removable = false; + dr.foundations_only_comp_piles = false; + + dr.hole_present = false; + + dr.cells = 0u; + + dr.stock_size = 0u; + dr.stock_deal_method = STOCK_TO_WASTE; + dr.stock_deal_count = 1u; + dr.stock_redeal = false; + + dr.reserve_size = 0u; + dr.reserve_stacked = false; + + dr.accordion_size = 0; + // dr.accordion_moves is an empty vector + // dr.accordion_policy is an empty vector + + return dr; +} + +srules DEFAULT_RULES = fetch_default_rules(); + +srules fortunes_favor() { + // default rules + srules r = DEFAULT_RULES; + + // rules specific to fortunes favor + r.tableau_size = 12u; + r.build_policy = BUILD_SAME_SUIT; + r.spaces_policy = AUTO_WASTE_THEN_STOCK; + r.foundations_init_cards = ALL_FOUNDATIONS_INIT; + r.stock_size = 36u; + + return r; +} + +settings get_settings(user_data *d) { + settings s = DEFAULT_SETTINGS; + + s.run_func = &run_single; + s.thoughtful_run_func = &thoughtful_run; + + s.move_size = sizeof(move); + s.reserved_move_count = 1u; + + s.user_data = d; + + return s; +} + +user_data get_user_data() { + user_data d; + + d.run_cache_size = 1024u; + d.run_timeout = 3000u; + d.thoughtful_run_timeout = 10000u; + + return d; +} + +int main() { + srules r = fortunes_favor(); + user_data d = get_user_data(); + settings s = get_settings(&d); + + card_pile cp; + make_deck(cp); + remove_cards(cp, { "AS", "AD", "AH", "AC" }); + shuffle(cp); + + sgame_state gs; + gs.foundations.resize(4); + gs.foundations[0].push_back(str_scard("AS")); + gs.foundations[1].push_back(str_scard("AD")); + gs.foundations[2].push_back(str_scard("AH")); + gs.foundations[3].push_back(str_scard("AD")); + + gs.tableau.resize(r.tableau_size); + + gs.stock.resize(cp.size()); + strs_scards(cp, gs.stock); + + // Aces and top stock card are face-up + for (auto &f : gs.foundations) + f.back().hidden = false; + gs.stock.back().hidden = false; + + run(&gs, &r, &s); +} + +/* int main() { */ +/* auto rules = rules_parser::from_preset("fortunes-favor"); */ +/* /1* auto rules = rules_parser::from_preset("canfield"); *1/ */ + +/* card_pile cp; */ +/* std::vector<card_pile> t; */ + +/* make_deck(cp); */ +/* shuffle(cp); */ + +/* remove_cards(cp, { "AS", "AD", "AH", "AC" }); */ + +/* piles ps = piles{ */ +/* {"AS"}, {"AD"}, {"AH"}, {"AC"}, // Foundations */ +/* { cp }, {}, // Stock-waste */ +/* {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {} // Tableau */ +/* }; */ + +/* movelist ml; */ + +/* game_state gs(rules, ps); */ +/* finished_state result = get_moves(ml, gs, 1024u, 3000u); */ + +/* printf("%d\n", result); */ + +/* switch (result) { */ +/* case SOLUTION_FOUND: { */ +/* printf("no. of moves: %d\n", ml.size()); */ + +/* size_t bufsize = 10; */ +/* char buf[bufsize]; */ +/* bool first = true; */ +/* for (auto &m : ml) { */ +/* int required = move_as_str(m, &buf[0], bufsize); */ +/* assert(required < bufsize); */ + +/* printf("%s\n", buf); */ + +/* if (!first) gs.make_move(m); */ +/* first = false; */ +/* } */ + +/* std::cerr << "Final layout:" << std::endl << gs << std::endl; */ +/* // printf("final layout:\n%s\n", gs.to_string()); */ +/* break; */ +/* } */ +/* case NO_SOLUTION: */ +/* printf("no solution\n"); */ +/* break; */ +/* case TIMEOUT: */ +/* printf("solver ran out of time\n"); */ +/* break; */ +/* case SOLVER_OOM: */ +/* printf("solver ran out of allocated memory\n"); */ +/* break; */ +/* case CANCELLED: */ +/* printf("solver was interrupted\n"); */ +/* break; */ +/* default: */ +/* assert(false); */ +/* } */ + +/* return 0; */ +/* } */ diff --git a/src/main/api.cpp b/src/main/api.cpp index fc3da3a..1709a49 100644 --- a/src/main/api.cpp +++ b/src/main/api.cpp @@ -1,14 +1,21 @@ #include <cstdint> + #include <vector> #include <string> +#include <stdio.h> + #include "game/move.h" #include "game/search-state/game_state.h" #include "solver/solver.h" -bool get_moves(std::vector<move>& moves, game_state& gs, +enum finished_state { + SOLUTION_FOUND, NO_SOLUTION, TIMEOUT, SOLVER_OOM, CANCELLED +}; + +finished_state get_moves(std::vector<move>& moves, game_state& gs, uint64_t cache_capacity, uint64_t timeout); -bool get_moves(std::vector<move>& moves, game_state& gs, +finished_state get_moves(std::vector<move>& moves, game_state& gs, uint64_t cache_capacity, uint64_t timeout) { moves.clear(); @@ -19,8 +26,21 @@ bool get_moves(std::vector<move>& moves, game_state& gs, for (auto &it : nodes) { moves.push_back(it.mv); } - return true; - } else { - return false; + } + + switch (res.sol_type) { + case solver::result::type::SOLVED: + return SOLUTION_FOUND; + case solver::result::type::UNSOLVABLE: + return NO_SOLUTION; + case solver::result::type::TIMEOUT: + return TIMEOUT; + case solver::result::type::MEM_LIMIT: + return SOLVER_OOM; + case solver::result::type::TERMINATED: + return CANCELLED; + default: + assert(false); + return NO_SOLUTION; } } diff --git a/src/main/api.h b/src/main/api.h index 86e3441..e454816 100644 --- a/src/main/api.h +++ b/src/main/api.h @@ -5,6 +5,7 @@ #include "game/move.h" #include "game/sol_rules.h" +#include "game/card.h" // just for now, until I construct my own rules stuff: #include "input-output/input/json-parsing/rules_parser.h" @@ -12,9 +13,20 @@ typedef std::vector<std::vector<std::string>> piles; typedef std::vector<move> movelist; +enum finished_state { + SOLUTION_FOUND, NO_SOLUTION, TIMEOUT, SOLVER_OOM, CANCELLED +}; + class game_state { public: game_state(const sol_rules&, piles); + game_state(const sol_rules&, + std::vector<std::vector<card::suit_t>>, + std::vector<std::vector<card::rank_t>>, + std::vector<std::vector<bool>>); + + bool is_solved() const; + enum class streamliner_options {NONE, AUTO_FOUNDATIONS, SUIT_SYMMETRY, BOTH}; void make_move(move); @@ -62,5 +74,5 @@ class game_state { * * Returns true if a solution was found; false otherwise. */ -bool get_moves(movelist& moves, game_state& gs, uint64_t cache_capacity, - uint64_t timeout); +finished_state get_moves(movelist& moves, game_state& gs, + uint64_t cache_capacity, uint64_t timeout); diff --git a/src/main/game/search-state/game_state.cpp b/src/main/game/search-state/game_state.cpp index a547f7e..6ea550c 100644 --- a/src/main/game/search-state/game_state.cpp +++ b/src/main/game/search-state/game_state.cpp @@ -306,6 +306,36 @@ game_state::game_state(const sol_rules& s_rules, } } +game_state::game_state(const sol_rules& s_rules, + std::vector<std::vector<card::suit_t>> suits, + std::vector<std::vector<card::rank_t>> ranks, + std::vector<std::vector<bool>> face_down) + : game_state(s_rules, sos::NONE) {pile::ref pr = 0; + assert(suits.size() == ranks.size()); + assert(ranks.size() == face_down.size()); + for (std::vector<std::vector<card::suit_t>>::size_type i = 0; + i < suits.size(); ++i) { + assert(suits[i].size() == ranks[i].size()); + assert(ranks[i].size() == face_down[i].size()); + for (std::vector<card::suit_t>::size_type j = 0; j < suits[i].size(); + ++j) { + card c(suits[i][j], ranks[i][j], face_down[i][j]); + place_card(pr, c); + } + pr++; + } + + // Sets foundations base appropriately + if (rules.foundations_present && rules.foundations_base == boost::none) { + for (auto f : foundations) { + if (!piles[f].empty()) { + foundations_base = piles[f].top_card().get_rank(); + return; + } + } + } +} + // Generates a randomly ordered vector of cards vector<card> game_state::gen_shuffled_deck(card::rank_t max_rank, bool two_decks, mt19937 rng) { diff --git a/src/main/game/search-state/game_state.h b/src/main/game/search-state/game_state.h index 9f8e3b9..1698122 100644 --- a/src/main/game/search-state/game_state.h +++ b/src/main/game/search-state/game_state.h @@ -41,6 +41,10 @@ public: game_state(const sol_rules&, std::initializer_list<std::initializer_list<std::string>>); // Does the same but with vectors game_state(const sol_rules&, std::vector<std::vector<std::string>>); + // Does the same but with lots of vectors + game_state(const sol_rules&, std::vector<std::vector<card::suit_t>>, + std::vector<std::vector<card::rank_t>>, + std::vector<std::vector<bool>>); /* Altering state */ diff --git a/src/main/solver/solver.cpp b/src/main/solver/solver.cpp index c4e8c84..e10396f 100644 --- a/src/main/solver/solver.cpp +++ b/src/main/solver/solver.cpp @@ -61,7 +61,7 @@ solver::node::node(const move m) solver::result solver::run(boost::optional<millisec> timeout) { // Set interrupt handler - signal(SIGINT, sigint_handler); + /* signal(SIGINT, sigint_handler); */ // Set timings const clock::time_point start_time = clock::now(); diff --git a/test.cpp b/test.cpp deleted file mode 100644 index de14630..0000000 --- a/test.cpp +++ /dev/null @@ -1,120 +0,0 @@ -#include <cstdint> -#include <iostream> -#include <algorithm> -#include <random> -#include <string> -#include <cstdio> - -#include "src/main/api.h" - -typedef std::vector<std::string> card_pile; - -card_pile& make_deck(card_pile& space, int deck_count); -card_pile& make_deck(card_pile& space, int deck_count = 1) { - space.clear(); - for (int i = 0; i < deck_count; ++i) { - for (std::string suit : { "S", "C", "D", "H" }) { - for (std::string rank : { "A", "2", "3", "4", "5", "6", "7", "8", - "9", "10", "J", "Q", "K" }) { - space.push_back(rank + suit); - } - } - } - return space; -} - -std::random_device rd; -auto rng = std::default_random_engine{rd()}; -card_pile& shuffle(card_pile& cards); -card_pile& shuffle(card_pile& cards) { - std::shuffle(std::begin(cards), std::end(cards), rng); - return cards; -} - -std::vector<card_pile>& split(card_pile& in, std::vector<card_pile>& out, - std::vector<std::size_t> numbers); -std::vector<card_pile>& split(card_pile& in, std::vector<card_pile>& out, - std::vector<std::size_t> numbers) { - out.clear(); - out.resize(numbers.size()); - - std::size_t acc = 0; - auto i = 0; - for (auto& n : numbers) { - card_pile cp(in.begin() + acc, in.begin() + acc + n); - out[i] = cp; - acc += n; - ++i; - } - - assert(acc == in.size()); - return out; -} - -std::vector<card_pile>& split_even(card_pile& in, std::vector<card_pile>& out, - std::size_t n_piles); -std::vector<card_pile>& split_even(card_pile& in, std::vector<card_pile>& out, - std::size_t n_piles) { - std::vector<std::size_t> nums; - - auto t = in.size(); - for (int i = 0; i < (int)in.size(); ++i) { - auto w = t / (n_piles - i); - nums.push_back(w); - t -= w; - } - - return split(in, out, nums); -} - -typedef struct scard { - enum class suit { - HEARTS, SPADES, CLUBS, DIAMONDS - } suit; - std::uint8_t rank; - bool hidden; -} scard; - -int main() { - auto rules = rules_parser::from_preset("canfield"); - - card_pile cp; - std::vector<card_pile> t; - - make_deck(cp); - shuffle(cp); - - std::cerr << cp.size(); - - split(cp, t, {13, 1, 1, 1, 1, 1, 34}); - - movelist ml; - - piles ps = piles{ - t[1],{},{},{}, // Foundations - t[6],{}, // Stock-waste - t[0], // Reserve - t[2],t[3],t[4],t[5] // Tableau - }; - - game_state gs(rules, ps); - - std::cerr << get_moves(ml, gs, 1024u, 102400u) << std::endl; - std::cerr << ml.size() << std::endl; - - bool first = true; - for (auto& m : ml) { - printf("%d->%d\n", m.from, m.to); - - if (!first) { - gs.make_move(m); - } - first = false; - } - - std::cerr << gs << std::endl; - - std::cerr << "woa" << std::endl; - - return 0; -} |