• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

APN-Pucky / tyrant_optimize / 20666674034

02 Jan 2026 09:05PM UTC coverage: 70.382% (+0.02%) from 70.364%
20666674034

Pull #103

github

APN-Pucky
no more need for std-17
Pull Request #103: [WIP] add `_DEBUG_STRAP`

35 of 48 new or added lines in 3 files covered. (72.92%)

2 existing lines in 2 files now uncovered.

4812 of 6837 relevant lines covered (70.38%)

9449982.62 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.04
/algorithms.cpp
1
#include <iostream>
2
#include <vector>
3

4
#include "algorithms_util.h"
5

6
using namespace tuo;
7

8
inline bool try_improve_deck(Deck* d1, unsigned from_slot, unsigned to_slot, const Card* card_candidate,
3,742 ✔
9
                const Card*& best_commander, const Card*& best_alpha_dominion, std::vector<const Card*>& best_cards,
10
                FinalResults<long double>& best_score, unsigned& best_gap, std::string& best_deck,
11
                std::unordered_map<std::string, EvaluatedResults>& evaluated_decks, EvaluatedResults& zero_results,
12
                unsigned long& skipped_simulations, Process& proc, bool print
13
#ifndef NQUEST
14
                , Quest & quest
15
#endif
16
        )
17
{
18
        unsigned deck_cost(0);
3,742 ✔
19
        std::vector<std::pair<signed, const Card *>> cards_out, cards_in;
3,742 ✔
20
        std::mt19937& re = proc.threads_data[0]->re;
3,742 ✔
21

22
        // setup best deck
23
        d1->commander = best_commander;
3,742 ✔
24
        d1->alpha_dominion = best_alpha_dominion;
3,742 ✔
25
        d1->cards = best_cards;
3,742 ✔
26

27
        // try to adjust the deck
28
        if (!adjust_deck(d1, from_slot, to_slot, card_candidate, fund, re, deck_cost, cards_out, cards_in))
3,742 ✔
29
        { return false; }
30

31
        // check gap
32
        unsigned new_gap = check_requirement(d1, requirement
2,793 ✔
33
#ifndef NQUEST
34
                        , quest
35
#endif
36
                        );
37
        if ((new_gap > 0) && (new_gap >= best_gap))
2,793 ✔
38
        { return false; }
39

40
        // check previous simulations
41
        auto && cur_deck = d1->hash();
2,793 ✔
42
        auto && emplace_rv = evaluated_decks.insert({cur_deck, zero_results});
5,586 ✔
43
        auto & prev_results = emplace_rv.first->second;
2,793 ✔
44
        if (!emplace_rv.second)
2,793 ✔
45
        {
46
                skipped_simulations += prev_results.second;
1,098 ✔
47
        }
48

49
        // Evaluate new deck
50
        auto compare_results = proc.compare(best_score.n_sims, prev_results, best_score);
2,793 ✔
51
        auto current_score = compute_score(compare_results, proc.factors);
2,793 ✔
52

53
        // Is it better ?
54
        if (new_gap < best_gap || current_score.points > best_score.points + min_increment_of_score)
2,793 ✔
55
        {
56
                // Then update best score/slot, print stuff
57
                if(print)std::cout << "Deck improved: " << d1->hash() << ": " << card_slot_id_names(cards_out) << " -> " << card_slot_id_names(cards_in) << ": ";
224 ✔
58
                best_gap = new_gap;
96 ✔
59
                best_score = current_score;
96 ✔
60
                best_deck = cur_deck;
96 ✔
61
                best_commander = d1->commander;
96 ✔
62
                best_alpha_dominion = d1->alpha_dominion;
96 ✔
63
                best_cards = d1->cards;
96 ✔
64
                if(print)print_score_info(compare_results, proc.factors);
96 ✔
65
                if(print)print_deck_inline(deck_cost, best_score, d1);
32 ✔
66
                return true;
96 ✔
67
        }
68

69
        return false;
70
}
3,742 ✔
71
//------------------------------------------------------------------------------
72
/*
73
 * Calc value of current set deck in d1 (proc.your_decks[0])
74
 */
75
inline FinalResults<long double> fitness(Deck* d1,
1,003 ✔
76
                FinalResults<long double>& best_score,
77
                std::unordered_map<std::string, EvaluatedResults>& evaluated_decks, EvaluatedResults& zero_results,
78
                unsigned long& skipped_simulations, Process& proc, bool compare = false)
79
{
80

81
        // check previous simulations
82
        auto && cur_deck = d1->hash();
1,003 ✔
83
        //std::cout << "Deck hash: " << d1->hash() << " with ";
84
        auto && emplace_rv = evaluated_decks.insert({cur_deck, zero_results});
2,006 ✔
85
        auto & prev_results = emplace_rv.first->second;
1,003 ✔
86
        if (!emplace_rv.second)
1,003 ✔
87
        {
88
                skipped_simulations += prev_results.second;
308 ✔
89
        }
90

91
        // Evaluate new deck
92
        if (compare) {
1,003 ✔
93
                auto compare_results= proc.compare(best_score.n_sims, prev_results,best_score);
720 ✔
94
                auto current_score = compute_score(compare_results, proc.factors);
720 ✔
95
                return current_score;
720 ✔
96
        }
720 ✔
97
        else
98
        {
99
                auto compare_results= proc.evaluate(best_score.n_sims, prev_results);
283 ✔
100
                auto current_score = compute_score(compare_results, proc.factors);
283 ✔
101

102
                //best_score = current_score;
103
                //auto best_deck = d1->clone();
104
                //print_score_info(compare_results, proc.factors);
105
                //print_deck_inline(get_deck_cost(best_deck), best_score, best_deck);
106
                return current_score;
283 ✔
107
        }
283 ✔
108
}
1,003 ✔
109
//------------------------------------------------------------------------------
110
Deck* filter_best_deck(std::vector<Deck*> your_decks, Deck* d1,
3 ✔
111
                FinalResults<long double>& best_score,
112
                std::unordered_map<std::string, EvaluatedResults>& evaluated_decks, EvaluatedResults& zero_results,
113
                unsigned long& skipped_simulations, Process& proc) {
114
        Deck * cur_return = your_decks[0];
3 ✔
115
        FinalResults<long double> cur_score;
3 ✔
116
        for(unsigned i=1;i < your_decks.size();++i) //start with 1 since first always is simmed already
3 ✔
117
        {
118
                copy_deck(your_decks[i],d1);
×
119
                cur_score = fitness(d1, best_score, evaluated_decks, zero_results, skipped_simulations, proc,true);
×
120
                if(cur_score.points > best_score.points)
×
121
                {
122
                        cur_return = your_decks[i];
×
123
                        best_score = cur_score;
×
124

125
                        std::cout << "Deck improved: " << d1->hash() <<":";
×
126
                        print_deck_inline(get_deck_cost(d1), best_score,d1);
×
127
                }
128
        }
129
        return cur_return;
3 ✔
130
}
131

132
//------------------------------------------------------------------------------
133
DeckResults hill_climbing(unsigned num_min_iterations, unsigned num_iterations, std::vector<Deck*> your_decks , Process& proc, Requirement & requirement
2 ✔
134
#ifndef NQUEST
135
                , Quest & quest
136
#endif
137
                )
138
{
139
        Deck * d1 = proc.your_decks[0];
2 ✔
140
        EvaluatedResults zero_results = { EvaluatedResults::first_type(proc.enemy_decks.size()), 0 };
2 ✔
141
        std::string best_deck = d1->hash();
2 ✔
142
        std::unordered_map<std::string, EvaluatedResults> evaluated_decks{{best_deck, zero_results}};
6 ✔
143
        EvaluatedResults& results = proc.evaluate(num_min_iterations, evaluated_decks.begin()->second);
2 ✔
144
        print_score_info(results, proc.factors);
2 ✔
145
        FinalResults<long double> best_score = compute_score(results, proc.factors);
2 ✔
146
        unsigned long skipped_simulations = 0;
2 ✔
147

148
        // use the best deck from all passed decks
149
        copy_deck(filter_best_deck(your_decks, d1, best_score, evaluated_decks, zero_results, skipped_simulations, proc),d1);
2 ✔
150

151
        // update freezed_cards
152
        freezed_cards = std::min<unsigned>(opt_freezed_cards, d1->cards.size());
2 ✔
153
        const Card* best_commander = d1->commander;
2 ✔
154
        const Card* best_alpha_dominion = d1->alpha_dominion;
2 ✔
155
        std::vector<const Card*> best_cards = d1->cards;
2 ✔
156
        unsigned deck_cost = get_deck_cost(d1);
2 ✔
157
        fund = std::max(fund, deck_cost);
2 ✔
158
        print_deck_inline(deck_cost, best_score, d1,true);
2 ✔
159
        std::mt19937& re = proc.threads_data[0]->re;
2 ✔
160
        unsigned best_gap = check_requirement(d1, requirement
2 ✔
161
#ifndef NQUEST
162
                        , quest
163
#endif
164
                        );
2 ✔
165
        bool is_random = (d1->strategy == DeckStrategy::random) || (d1->strategy == DeckStrategy::flexible);
2 ✔
166
        bool deck_has_been_improved = true;
2 ✔
167
        std::vector<const Card*> commander_candidates;
2 ✔
168
        std::vector<const Card*> alpha_dominion_candidates;
2 ✔
169
        std::vector<const Card*> card_candidates;
2 ✔
170

171
        auto mixed_candidates = get_candidate_lists(proc);
2 ✔
172
        commander_candidates = mixed_candidates.at(0);
2 ✔
173
        alpha_dominion_candidates = mixed_candidates.at(1);
2 ✔
174
        card_candidates = mixed_candidates.at(2);
2 ✔
175
        // add current alpha dominion to candidates if necessary
176
        // or setup first candidate into the deck if no alpha dominion defined
177
        if (use_owned_dominions)
2 ✔
178
        {
179
                if (best_alpha_dominion)
2 ✔
180
                {
181
                        if (!std::count(alpha_dominion_candidates.begin(), alpha_dominion_candidates.end(), best_alpha_dominion))
×
182
                        {
183
                                alpha_dominion_candidates.emplace_back(best_alpha_dominion);
×
184
                        }
185
                }
186
                else if (!alpha_dominion_candidates.empty())
2 ✔
187
                {
188
                        best_alpha_dominion = d1->alpha_dominion = alpha_dominion_candidates[0];
2 ✔
189
                }
190
                if (debug_print > 0)
2 ✔
191
                {
192
                        for (const Card* dom_card : alpha_dominion_candidates)
×
193
                        {
194
                                std::cout << " ** next Alpha Dominion candidate: " << dom_card->m_name
×
195
                                        << " ($: " << alpha_dominion_cost(dom_card) << ")" << std::endl;
×
196
                        }
197
                }
198
                if (!best_alpha_dominion && owned_alpha_dominion)
2 ✔
199
                {
200
                        best_alpha_dominion = owned_alpha_dominion;
×
201
                        std::cout << "Setting up owned Alpha Dominion into a deck: " << best_alpha_dominion->m_name << std::endl;
×
202
                }
203
        }
204
        //std::reverse(card_candidates.begin(), card_candidates.end());
205

206

207

208
        // << main climbing loop >>
209
        for (unsigned from_slot(freezed_cards), dead_slot(freezed_cards); ;
2 ✔
210
                        from_slot = std::max(freezed_cards, (from_slot + 1) % std::min<unsigned>(max_deck_len, best_cards.size() + 1)))
30 ✔
211
        {
212
                if(is_timeout_reached()){ break;}
32 ✔
213
                if (deck_has_been_improved)
32 ✔
214
                {
215
                        dead_slot = from_slot;
216
                        deck_has_been_improved = false;
217
                }
218
                else if (from_slot == dead_slot || best_score.points - target_score > -1e-9)
15 ✔
219
                {
220
                        if (best_score.n_sims >= num_iterations || best_gap > 0)
4 ✔
221
                        { break; } // exit main climbing loop
222
                        auto & prev_results = evaluated_decks[best_deck];
2 ✔
223
                        skipped_simulations += prev_results.second;
2 ✔
224
                        // Re-evaluate the best deck
225
                        d1->commander = best_commander;
2 ✔
226
                        d1->alpha_dominion = best_alpha_dominion;
2 ✔
227
                        d1->cards = best_cards;
2 ✔
228
                        auto evaluate_result = proc.evaluate(std::min(prev_results.second * iterations_multiplier, num_iterations), prev_results);
2 ✔
229
                        best_score = compute_score(evaluate_result, proc.factors);
2 ✔
230
                        print_score_info(evaluate_result, proc.factors);
2 ✔
231
                        dead_slot = from_slot;
2 ✔
232
                }
2 ✔
233
                if (best_score.points - target_score > -1e-9)
30 ✔
234
                { continue; }
3 ✔
235

236
                // commander
237
                if (requirement.num_cards.count(best_commander) == 0)
27 ✔
238
                {
239
                        // << commander candidate loop >>
240
                        for (const Card* commander_candidate: commander_candidates)
264 ✔
241
                        {
242
                                if (best_score.points - target_score > -1e-9)
238 ✔
243
                                { break; }
244
                                if (commander_candidate == best_commander)
237 ✔
245
                                { continue; }
23 ✔
246
                                deck_has_been_improved |= try_improve_deck(d1, -1, -1, commander_candidate,
214 ✔
247
                                                best_commander, best_alpha_dominion, best_cards, best_score, best_gap, best_deck,
248
                                                evaluated_decks, zero_results, skipped_simulations, proc,true
249
#ifndef NQUEST
250
                        , quest
251
#endif
252
                        );
253
                        }
254
                        // Now that all commanders are evaluated, take the best one
255
                        d1->commander = best_commander;
27 ✔
256
                        d1->alpha_dominion = best_alpha_dominion;
27 ✔
257
                        d1->cards = best_cards;
27 ✔
258
                }
259

260
                // alpha dominion
261
                if (use_owned_dominions && !alpha_dominion_candidates.empty())
27 ✔
262
                {
263
                        // << alpha dominion candidate loop >>
264
                        for (const Card* alpha_dominion_candidate: alpha_dominion_candidates)
105 ✔
265
                        {
266
                                if (best_score.points - target_score > -1e-9)
79 ✔
267
                                { break; }
268
                                if (alpha_dominion_candidate == best_alpha_dominion)
78 ✔
269
                                { continue; }
26 ✔
270
                                deck_has_been_improved |= try_improve_deck(d1, -1, -1, alpha_dominion_candidate,
52 ✔
271
                                                best_commander, best_alpha_dominion, best_cards, best_score, best_gap, best_deck,
272
                                                evaluated_decks, zero_results, skipped_simulations, proc,true
273
#ifndef NQUEST
274
                        , quest
275
#endif
276
                        );
277
                        }
278
                        // Now that all alpha dominions are evaluated, take the best one
279
                        d1->commander = best_commander;
27 ✔
280
                        d1->alpha_dominion = best_alpha_dominion;
27 ✔
281
                        d1->cards = best_cards;
27 ✔
282
                }
283

284
                // shuffle candidates
285
                std::shuffle(card_candidates.begin(), card_candidates.end(), re);
27 ✔
286

287
                // << card candidate loop >>
288
                //for (const Card* card_candidate: card_candidates)
289
                for (auto it = card_candidates.begin(); it != card_candidates.end();++it)
603 ✔
290
                {
291
                        const Card* card_candidate = *it;
579 ✔
292
                        for (unsigned to_slot(is_random ? from_slot : card_candidate ? freezed_cards : (best_cards.size() - 1));
1,158 ✔
293
                                        to_slot < (is_random ? (from_slot + 1) : (best_cards.size() + (from_slot < best_cards.size() ? 0 : 1)));
1,158 ✔
294
                                        ++ to_slot)
295
                        {
296
                                if (card_candidate ?
579 ✔
297
                                                (from_slot < best_cards.size() && (from_slot == to_slot && card_candidate == best_cards[to_slot])) // 2 Omega -> 2 Omega
555 ✔
298
                                                :
299
                                                (from_slot == best_cards.size())) // void -> void
24 ✔
300
                                { continue; }
15 ✔
301
                                deck_has_been_improved |= try_improve_deck(d1, from_slot, to_slot, card_candidate,
564 ✔
302
                                                best_commander, best_alpha_dominion, best_cards, best_score, best_gap, best_deck,
303
                                                evaluated_decks, zero_results, skipped_simulations, proc,true
304
#ifndef NQUEST
305
                        , quest
306
#endif
307
                        );
308
                        }
309
                        if (best_score.points - target_score > -1e-9)
579 ✔
310
                        { break; }
311

312
                }
313
        }
30 ✔
314
        d1->commander = best_commander;
2 ✔
315
        d1->alpha_dominion = best_alpha_dominion;
2 ✔
316
        d1->cards = best_cards;
2 ✔
317
        unsigned simulations = 0;
2 ✔
318
        for (auto evaluation: evaluated_decks)
922 ✔
319
        { simulations += evaluation.second.second; }
920 ✔
320
        std::cout << "Evaluated " << evaluated_decks.size() << " decks (" << simulations << " + " << skipped_simulations << " simulations)." << std::endl;
2 ✔
321
        print_sim_card_values(d1,proc,num_iterations);
2 ✔
322
        std::cout << "Optimized Deck: ";
2 ✔
323
        print_deck_inline(get_deck_cost(d1), best_score, d1,true);
2 ✔
324
        print_upgraded_cards(d1);
2 ✔
325
        return std::make_pair(d1->clone(),best_score);
2 ✔
326
}
4 ✔
327

328

329

330

331
inline long double acceptanceProbability(long double old_score, long double new_score, long double temperature)
128 ✔
332
{
333
        if(new_score > old_score)
128 ✔
334
        {
335
                return 1;
336
        }
337
        //100/max_score normalizes the acceptance probability with the used mode/score-range
338
        //1000 is factor to set the temperature lower (can be changed indirect by setting begin-temperature and its decrease)
339
        return exp(((new_score-old_score)/temperature*1000*100)/max_possible_score[(size_t)optimization_mode]);
112 ✔
340
}
341

342
DeckResults simulated_annealing(unsigned num_min_iterations, unsigned num_iterations, std::vector<Deck*> your_decks, Process& proc, Requirement & requirement
1 ✔
343
#ifndef NQUEST
344
                , Quest & quest
345
#endif
346
                )
347
{
348
        Deck* cur_deck = proc.your_decks[0];
1 ✔
349
        EvaluatedResults zero_results = { EvaluatedResults::first_type(proc.enemy_decks.size()), 0 };
1 ✔
350
        //std::string best_deck = d1->hash();
351
        std::unordered_map<std::string, EvaluatedResults> evaluated_decks{{cur_deck->hash(), zero_results}};
4 ✔
352
        EvaluatedResults& results = proc.evaluate(num_min_iterations, evaluated_decks.begin()->second);
1 ✔
353
        print_score_info(results, proc.factors);
1 ✔
354
        FinalResults<long double> best_score = compute_score(results, proc.factors);
1 ✔
355
        //const Card* best_commander = d1->commander;
356
        //const Card* best_alpha_dominion = cur_deck->alpha_dominion;
357
        //std::vector<const Card*> best_cards = cur_deck->cards;
358
        unsigned long skipped_simulations = 0;
1 ✔
359

360

361
        // use the best deck from all passed decks
362
        copy_deck(filter_best_deck(your_decks, cur_deck, best_score, evaluated_decks, zero_results, skipped_simulations, proc),cur_deck);
1 ✔
363

364
        // update freezed_cards
365
        freezed_cards = std::min<unsigned>(opt_freezed_cards, cur_deck->cards.size());
1 ✔
366

367
        unsigned deck_cost = get_deck_cost(cur_deck);
1 ✔
368
        fund = std::max(fund, deck_cost);
1 ✔
369
        print_deck_inline(deck_cost, best_score, cur_deck,true);
1 ✔
370
        std::mt19937& re = proc.threads_data[0]->re;
1 ✔
371
        unsigned cur_gap = check_requirement(cur_deck, requirement
1 ✔
372
#ifndef NQUEST
373
                        , quest
374
#endif
375
                        );
376

377
        bool is_random = (cur_deck->strategy == DeckStrategy::random) || (cur_deck->strategy == DeckStrategy::flexible);
1 ✔
378
        std::vector<const Card*> all_candidates;
1 ✔
379

380
        auto mixed_candidates = get_candidate_lists(proc);
1 ✔
381
        all_candidates.reserve(mixed_candidates.at(0).size()+mixed_candidates.at(1).size()+mixed_candidates.at(2).size());
1 ✔
382
        all_candidates.insert(all_candidates.end(), std::make_move_iterator(mixed_candidates.at(0).begin()),std::make_move_iterator(mixed_candidates.at(0).end()));
1 ✔
383
        all_candidates.insert(all_candidates.end(), std::make_move_iterator(mixed_candidates.at(1).begin()),std::make_move_iterator(mixed_candidates.at(1).end()));
1 ✔
384
        all_candidates.insert(all_candidates.end(), std::make_move_iterator(mixed_candidates.at(2).begin()),std::make_move_iterator(mixed_candidates.at(2).end()));
1 ✔
385
        //clear
386
        mixed_candidates.at(0).clear(); mixed_candidates.at(0).shrink_to_fit();
2 ✔
387
        mixed_candidates.at(1).clear(); mixed_candidates.at(1).shrink_to_fit();
2 ✔
388
        mixed_candidates.at(2).clear(); mixed_candidates.at(2).shrink_to_fit();
2 ✔
389
        mixed_candidates.clear();mixed_candidates.shrink_to_fit();
2 ✔
390

391
        // add current alpha dominion to candidates if necessary
392
        // or setup first candidate into the deck if no alpha dominion defined
393
        if (use_owned_dominions)
1 ✔
394
        {
395
                if (cur_deck->alpha_dominion)
1 ✔
396
                {
397
                        if (!std::count(all_candidates.begin(), all_candidates.end(), cur_deck->alpha_dominion))
×
398
                        {
399
                                all_candidates.emplace_back(cur_deck->alpha_dominion);
×
400
                        }
401
                }
402
                if (!cur_deck->alpha_dominion && owned_alpha_dominion)
1 ✔
403
                {
404
                        cur_deck->alpha_dominion = owned_alpha_dominion;
1 ✔
405
                        std::cout << "Setting up owned Alpha Dominion into a deck: " << cur_deck->alpha_dominion->m_name << std::endl;
1 ✔
406
                }
407
        }
408

409
        Deck* prev_deck = cur_deck->clone();
1 ✔
410
        Deck* best_deck = cur_deck->clone();
1 ✔
411

412
        FinalResults<long double> prev_score = best_score;
1 ✔
413
        FinalResults<long double> cur_score = best_score;
1 ✔
414

415
        unsigned best_gap = cur_gap;
1 ✔
416

417
        deck_cost = 0;
1 ✔
418

419
        unsigned from_slot(freezed_cards);
1 ✔
420
        unsigned from_slot_tmp(freezed_cards);
1 ✔
421
        unsigned to_slot(1);
1 ✔
422

423
        if(debug_print >0)std::cout << "Starting Anneal" << std::endl;
1 ✔
424
        while(temperature > 1 && !(best_score.points - target_score > -1e-9 || is_timeout_reached()))
195 ✔
425
        {
426
                cur_deck->commander = prev_deck->commander;
194 ✔
427
                cur_deck->alpha_dominion = prev_deck->alpha_dominion;
194 ✔
428
                cur_deck->cards = prev_deck->cards;
194 ✔
429
                from_slot = std::max(freezed_cards, (from_slot+1) % std::min<unsigned>(max_deck_len, cur_deck->cards.size() +1));
194 ✔
430
                const Card* candidate = all_candidates.at(std::uniform_int_distribution<unsigned>(0,all_candidates.size()-1)(re));
194 ✔
431

432

433
                if((!candidate || (candidate->m_category == CardCategory::normal && candidate->m_type != CardType::commander && candidate->m_category != CardCategory::dominion_alpha)))
194 ✔
434
                {
435

436
                        to_slot = std::uniform_int_distribution<unsigned>(is_random ? from_slot : candidate ? freezed_cards : (cur_deck->cards.size() -1),(is_random ? (from_slot+1) : (cur_deck->cards.size() + ( from_slot < cur_deck->cards.size() ? 0 : 1)))-1)(re);
142 ✔
437
                        if(candidate ?
142 ✔
438
                                        (from_slot < cur_deck->cards.size() && (from_slot == to_slot && candidate == cur_deck->cards[to_slot]))
141 ✔
439
                                        :
440
                                        (from_slot == cur_deck->cards.size()))
1 ✔
441
                        {
442
                                continue;
66 ✔
443
                        }
444
                        from_slot_tmp = from_slot;
445
                }
446
                else if(candidate->m_type == CardType::commander && requirement.num_cards.count(cur_deck->commander) == 0)
52 ✔
447
                {
448
                        cur_deck->commander = candidate;
39 ✔
449
                        from_slot_tmp = -1;
39 ✔
450
                        to_slot = -1;
39 ✔
451
                }
452
                else if(candidate->m_category == CardCategory::dominion_alpha && use_owned_dominions)
13 ✔
453
                {
454
                        cur_deck->alpha_dominion = candidate;
13 ✔
455
                        from_slot_tmp = -1;
13 ✔
456
                        to_slot = -1;
13 ✔
457
                }
458
                else{
459
                        continue;
×
460
                }
461

462
                std::vector<std::pair<signed, const Card * >> cards_out, cards_in;
185 ✔
463
                if (!adjust_deck(cur_deck, from_slot_tmp, to_slot, candidate, fund, re, deck_cost, cards_out, cards_in))
185 ✔
464
                { continue;}
50 ✔
465
                cur_gap = check_requirement(cur_deck, requirement
135 ✔
466
#ifndef NQUEST
467
                                , quest
468
#endif
469
                                );
470
                if ((cur_gap > 0) && (cur_gap >= best_gap))
135 ✔
471
                { continue; }
×
472

473
                //same deck skip
474
                if(cur_deck->hash().compare(prev_deck->hash())==0)continue;
135 ✔
475

476

477

478
                cur_score = fitness(cur_deck, best_score, evaluated_decks, zero_results, skipped_simulations, proc);
128 ✔
479

480
                if(acceptanceProbability(prev_score.points, cur_score.points , temperature) > std::uniform_real_distribution<double>(0,1)(re))
128 ✔
481
                {
482
                        if(cur_score.points > best_score.points)
25 ✔
483
                        {
484
                                best_score = cur_score;
15 ✔
485
                                best_deck = cur_deck->clone();
15 ✔
486
                                best_gap = cur_gap;
15 ✔
487
                                std::cout << "Deck improved: " << best_deck->hash() << ": (temp=" << temperature << ") :";
30 ✔
488
                                print_deck_inline(get_deck_cost(best_deck), best_score, best_deck);
15 ✔
489
                        }
490
                        if(debug_print>0)std::cout << "UPDATED DECK: " << cur_deck->hash() << ": (temp=" << temperature << ") :";
25 ✔
491
                        if(debug_print>0)print_deck_inline(get_deck_cost(cur_deck), cur_score, cur_deck);
25 ✔
492
                        prev_score = cur_score;
25 ✔
493
                        prev_deck = cur_deck->clone();
25 ✔
494
                }
495
                temperature *=1-coolingRate;
128 ✔
496
        }
185 ✔
497
        unsigned simulations = 0;
1 ✔
498
        for (auto evaluation: evaluated_decks)
239 ✔
499
        { simulations += evaluation.second.second; }
238 ✔
500
        std::cout << "Evaluated " << evaluated_decks.size() << " decks (" << simulations << " + " << skipped_simulations << " simulations)." << std::endl;
1 ✔
501
        print_sim_card_values(best_deck,proc,num_iterations);
1 ✔
502
        std::cout << "Optimized Deck: ";
1 ✔
503
        print_deck_inline(get_deck_cost(best_deck), best_score, best_deck,true);
1 ✔
504
        print_upgraded_cards(best_deck);
1 ✔
505
        return std::make_pair(best_deck->clone(),best_score);
1 ✔
506
}
2 ✔
507

508

509

510

511
void crossover(Deck* src1,Deck* src2, Deck* cur_deck, std::mt19937& re,unsigned best_gap,std::unordered_map<std::string, EvaluatedResults>& evaluated_decks
310 ✔
512
#ifndef NQUEST
513
                , Quest & quest
514
#endif
515
)
516
{
517
        cur_deck->commander = std::uniform_int_distribution<unsigned>(0, 1)(re)?src1->commander:src2->commander;
310 ✔
518
        cur_deck->alpha_dominion = std::uniform_int_distribution<unsigned>(0, 1)(re)?src1->alpha_dominion:src2->alpha_dominion;
310 ✔
519
        bool finished = false;
310 ✔
520
        unsigned itr = 0;
310 ✔
521
        while(!finished && itr < 100) //todo opt
12,307 ✔
522
        {
523
                itr++;
11,997 ✔
524
                cur_deck->cards.clear();
11,997 ✔
525
                for(unsigned it =0; it < std::max(src1->cards.size(),src2->cards.size());it++)
131,967 ✔
526
                {
527
                        if(src1->cards.size() <=it)
119,970 ✔
UNCOV
528
                        {cur_deck->cards.push_back(src2->cards[it]);}
×
529
                        else if(src2->cards.size() <=it)
119,970 ✔
530
                        {cur_deck->cards.push_back(src1->cards[it]);}
9,100 ✔
531
                        else
532
                        {
533
                                cur_deck->cards.push_back(std::uniform_int_distribution<unsigned>(0, 1)(re)?src1->cards[it]:src2->cards[it]);
110,870 ✔
534
                        }
535
                }
536
                if(!valid_deck(cur_deck)) {continue;} //repeat
11,997 ✔
537

538
                if(evaluated_decks.count(cur_deck->hash())){continue;} // deck already simmed
17,286 ✔
539
                unsigned cur_gap = check_requirement(cur_deck, requirement
212 ✔
540
#ifndef NQUEST
541
                                , quest
542
#endif
543
                                );
544
                if ((cur_gap > 0) && (cur_gap >= best_gap))
212 ✔
545
                { continue; }
×
546
                finished = true; // exit while
547
        }
548
        if(!finished) copy_deck(std::uniform_int_distribution<unsigned>(0, 1)(re)?src1:src2,cur_deck);
357 ✔
549
}
310 ✔
550

551
void mutate(Deck* src, Deck* cur_deck, std::vector<const Card*> all_candidates, std::mt19937& re,unsigned best_gap,std::unordered_map<std::string, EvaluatedResults>& evaluated_decks
690 ✔
552
#ifndef NQUEST
553
                , Quest & quest
554
#endif
555
)
556
{
557
        copy_deck(src,cur_deck);
690 ✔
558

559
        bool is_random = (cur_deck->strategy == DeckStrategy::random) || (cur_deck->strategy == DeckStrategy::flexible); //should be same for all decks from input!?
690 ✔
560

561
        unsigned deck_cost = 0;
690 ✔
562

563
        unsigned from_slot(freezed_cards);
690 ✔
564
        unsigned from_slot_tmp(freezed_cards);
690 ✔
565
        unsigned to_slot(1);
690 ✔
566

567
        bool finished = false;
690 ✔
568
        unsigned itr=0;
690 ✔
569
        while(!finished && itr < 100) // todo opt
1,906 ✔
570
        {
571
                itr++;
1,216 ✔
572
                copy_deck(src,cur_deck);
1,216 ✔
573

574
                from_slot = std::uniform_int_distribution<unsigned>(1,std::min<unsigned>(max_deck_len-1, cur_deck->cards.size()))(re);
1,216 ✔
575

576
                const Card* candidate = all_candidates.at(std::uniform_int_distribution<unsigned>(0,all_candidates.size()-1)(re));
1,216 ✔
577

578

579
                if((!candidate || (candidate->m_category == CardCategory::normal && candidate->m_type != CardType::commander && candidate->m_category != CardCategory::dominion_alpha)))
1,216 ✔
580
                {
581

582
                        to_slot = std::uniform_int_distribution<unsigned>(is_random ? from_slot : candidate ? freezed_cards : (cur_deck->cards.size() -1),(is_random ? (from_slot+1) : (cur_deck->cards.size() + ( from_slot < cur_deck->cards.size() ? 0 : 1)))-1)(re);
793 ✔
583
                        if(candidate ?
793 ✔
584
                                        (from_slot < cur_deck->cards.size() && (from_slot == to_slot && candidate == cur_deck->cards[to_slot]))
767 ✔
585
                                        :
586
                                        (from_slot == cur_deck->cards.size()))
26 ✔
587
                        {
588
                                continue;
526 ✔
589
                        }
590
                        from_slot_tmp = from_slot;
591
                }
592
                else if(candidate->m_type == CardType::commander && requirement.num_cards.count(cur_deck->commander) == 0)
423 ✔
593
                {
594
                        cur_deck->commander = candidate;
330 ✔
595
                        from_slot_tmp = -1;
330 ✔
596
                        to_slot = -1;
330 ✔
597
                }
598
                else if(candidate->m_category == CardCategory::dominion_alpha && use_owned_dominions)
93 ✔
599
                {
600
                        cur_deck->alpha_dominion = candidate;
93 ✔
601
                        from_slot_tmp = -1;
93 ✔
602
                        to_slot = -1;
93 ✔
603
                }
604
                else{
605
                        continue;
×
606
                }
607

608
                std::vector<std::pair<signed, const Card * >> cards_out, cards_in;
1,187 ✔
609
                if (!adjust_deck(cur_deck, from_slot_tmp, to_slot, candidate, fund, re, deck_cost, cards_out, cards_in))
1,187 ✔
610
                { continue;}
300 ✔
611

612
                if(evaluated_decks.count(cur_deck->hash()))
1,774 ✔
613
                {continue;} // deck already simmed
197 ✔
614
                if(!valid_deck(cur_deck)) {continue;} //repeat
690 ✔
615
                unsigned cur_gap = check_requirement(cur_deck, requirement
690 ✔
616
#ifndef NQUEST
617
                                , quest
618
#endif
619
                                );
620
                if ((cur_gap > 0) && (cur_gap >= best_gap))
690 ✔
621
                { continue; }
×
622
                finished = true; // exit while
690 ✔
623
        }
1,187 ✔
624
        if(!finished) copy_deck(src,cur_deck);
690 ✔
625
}
690 ✔
626
DeckResults genetic_algorithm(unsigned num_min_iterations, unsigned num_iterations, std::vector<Deck*> your_decks, Process& proc, Requirement & requirement
1 ✔
627
#ifndef NQUEST
628
                , Quest & quest
629
#endif
630
                )
631
{
632
        //std::cerr << "START GENETIC" << std::endl;
633
        if(pool_size==0){
1 ✔
634
                if(your_decks.size()>min_pool_size) { //
1 ✔
635
                        pool_size = your_decks.size();
×
636
                }
637
                else {
638
                        pool_size = min_pool_size;
1 ✔
639
                }
640
        }
641
        unsigned pool_cross = pool_size*opt_pool_cross/(opt_pool_mutate+opt_pool_cross+opt_pool_keep);
1 ✔
642
        unsigned pool_keep = pool_size*opt_pool_keep/(opt_pool_mutate+opt_pool_cross+opt_pool_keep);
1 ✔
643
        unsigned pool_mutate = pool_size-pool_cross-pool_keep;
1 ✔
644

645
        //your_decks.size();
646
        std::vector<std::pair<Deck*,FinalResults<long double>>> pool;
1 ✔
647
        Deck* cur_deck = proc.your_decks[0];
1 ✔
648

649

650

651
        EvaluatedResults zero_results = { EvaluatedResults::first_type(proc.enemy_decks.size()), 0 };
1 ✔
652

653
        std::unordered_map<std::string, EvaluatedResults> evaluated_decks{{cur_deck->hash(), zero_results}};
4 ✔
654
        EvaluatedResults& results = proc.evaluate(num_min_iterations, evaluated_decks.begin()->second);
1 ✔
655
        print_score_info(results, proc.factors);
1 ✔
656
        FinalResults<long double> best_score = compute_score(results, proc.factors); //init sim, todo remove
1 ✔
657

658
        unsigned deck_cost = get_deck_cost(cur_deck);
1 ✔
659
        fund = std::max(fund, deck_cost);
1 ✔
660
        print_deck_inline(deck_cost, best_score, cur_deck,true);
1 ✔
661
        std::mt19937& re = proc.threads_data[0]->re;
1 ✔
662
        unsigned cur_gap = check_requirement(cur_deck, requirement
1 ✔
663
#ifndef NQUEST
664
                        , quest
665
#endif
666
                        );
667

668
        unsigned long skipped_simulations = 0;
1 ✔
669
        std::vector<const Card*> all_candidates;
1 ✔
670

671
        auto mixed_candidates = get_candidate_lists(proc);
1 ✔
672
        all_candidates.reserve(mixed_candidates.at(0).size()+mixed_candidates.at(1).size()+mixed_candidates.at(2).size());
1 ✔
673
        all_candidates.insert(all_candidates.end(), std::make_move_iterator(mixed_candidates.at(0).begin()),std::make_move_iterator(mixed_candidates.at(0).end()));
1 ✔
674
        all_candidates.insert(all_candidates.end(), std::make_move_iterator(mixed_candidates.at(1).begin()),std::make_move_iterator(mixed_candidates.at(1).end()));
1 ✔
675
        all_candidates.insert(all_candidates.end(), std::make_move_iterator(mixed_candidates.at(2).begin()),std::make_move_iterator(mixed_candidates.at(2).end()));
1 ✔
676
        //clear
677
        mixed_candidates.at(0).clear(); mixed_candidates.at(0).shrink_to_fit();
2 ✔
678
        mixed_candidates.at(1).clear(); mixed_candidates.at(1).shrink_to_fit();
2 ✔
679
        mixed_candidates.at(2).clear(); mixed_candidates.at(2).shrink_to_fit();
2 ✔
680
        mixed_candidates.clear();mixed_candidates.shrink_to_fit();
2 ✔
681

682
        // add current alpha dominion to candidates if necessary
683
        // or setup first candidate into the deck if no alpha dominion defined
684

685
        for( auto tmp_deck : your_decks) // check all decks for owned dominions
2 ✔
686
        {
687
                if (use_owned_dominions)
1 ✔
688
                {
689
                        if (tmp_deck->alpha_dominion)
1 ✔
690
                        {
691
                                if (!std::count(all_candidates.begin(), all_candidates.end(), tmp_deck->alpha_dominion))
×
692
                                {
693
                                        all_candidates.emplace_back(tmp_deck->alpha_dominion);
×
694
                                }
695
                        }
696
                        if (!tmp_deck->alpha_dominion && owned_alpha_dominion)
1 ✔
697
                        {
698
                                tmp_deck->alpha_dominion = owned_alpha_dominion;
1 ✔
699
                                std::cout << "Setting up owned Alpha Dominion into a deck: " << tmp_deck->alpha_dominion->m_name << std::endl;
1 ✔
700
                        }
701
                }
702
        }
703
        Deck* best_deck = cur_deck->clone();
1 ✔
704
        FinalResults<long double> cur_score = best_score;
1 ✔
705
        unsigned best_gap = cur_gap;
1 ✔
706

707
        //fill pool
708
        if(your_decks.size()>pool_size) your_decks.resize(pool_size); //TODO this drops potential better overflowing decks?!
1 ✔
709
        for ( unsigned it =your_decks.size(); it < pool_size;it++)
20 ✔
710
        {
711
                unsigned j = std::uniform_int_distribution<unsigned>(0,your_decks.size()-1)(re);
19 ✔
712
                unsigned i = std::uniform_int_distribution<unsigned>(0,your_decks.size()-1)(re);
19 ✔
713
                Deck* nxt = your_decks[j]->clone();
19 ✔
714
                if(std::uniform_int_distribution<unsigned>(0,1)(re))
19 ✔
715
                {
716
                        mutate(your_decks[i],nxt,all_candidates,re,best_gap,evaluated_decks
9 ✔
717
#ifndef NQUEST
718
                                        , quest
719
#endif
720
            );
721
                }
722
                else
723
                {
724
                        crossover(your_decks[i],your_decks[j],nxt,re,best_gap,evaluated_decks
10 ✔
725
#ifndef NQUEST
726
                                        , quest
727
#endif
728
            );
729
                }
730
                your_decks.push_back(nxt);
19 ✔
731
        }
732
        //sim pool
733
        for( auto i_deck :your_decks)
21 ✔
734
        {
735
                copy_deck(i_deck,cur_deck);
20 ✔
736
                cur_score = fitness(cur_deck, best_score, evaluated_decks, zero_results, skipped_simulations, proc,true);
20 ✔
737
                pool.push_back(std::make_pair(i_deck,cur_score));
20 ✔
738
                if(cur_score.points > best_score.points)
20 ✔
739
                {
740
                        best_score = cur_score;
4 ✔
741
                        best_deck = cur_deck->clone();
4 ✔
742
                        best_gap = check_requirement(cur_deck, requirement
4 ✔
743
#ifndef NQUEST
744
                                        , quest
745
#endif
746
                                        );
747
                        std::cout << "Deck improved: " << best_deck->hash() <<":";
8 ✔
748
                        print_deck_inline(get_deck_cost(best_deck), best_score, best_deck);
4 ✔
749
                }
750
        }
751

752
        for( unsigned gen= 0; gen< generations && !is_timeout_reached() ;gen++ )
51 ✔
753
        {
754
                std::cout << "GENERATION: " << gen << std::endl;
50 ✔
755

756
                //sort
757
                auto sort = [](std::pair<Deck*,FinalResults<long double>> l,std::pair<Deck*,FinalResults<long double>> r) {return l.second.points > r.second.points;};
4,654 ✔
758
                std::sort(pool.begin(),pool.end(),sort);
50 ✔
759
                //breed
760
                //cross
761
                for ( unsigned it = 0; it < pool_cross;it++)
350 ✔
762
                {
763
                        unsigned i = std::uniform_int_distribution<unsigned>(0,pool_keep-1)(re);
300 ✔
764
                        unsigned j = std::uniform_int_distribution<unsigned>(pool_keep,pool_size-pool_mutate)(re);
300 ✔
765
                        //unsigned  k= std::uniform_int_distribution<unsigned>(0,pool_size-pool_mutate)(re);
766
                        unsigned k = -1;
300 ✔
767
                        while (k >= pool_size-pool_mutate)
632 ✔
768
                                k=std::geometric_distribution<unsigned>(0.2)(re); //prefer crossover with strong decks
332 ✔
769
                        crossover(pool[i].first,pool[k].first,pool[j].first,re,best_gap, evaluated_decks
300 ✔
770
#ifndef NQUEST
771
                                        , quest
772
#endif
773
            );
774
                        //crossover(pool[it+pool_size/4*2].first,pool[it+pool_size/4*3].first,pool[it+pool_size/4*3].first,re,best_gap, evaluated_decks);
775
                        //crossover(pool[it].first,pool[(it+pool_size/8)%(pool_size/4)].first,pool[it+pool_size/4*2].first,re,best_gap, evaluated_decks);
776
                        //mutate(pool[it].first,pool[it+pool_size/4*3].first,all_candidates,re,best_gap, evaluated_decks);
777
                }
778
                //mutate pool_keep to replace lowest scores
779
                for ( unsigned it = pool_size-pool_mutate; it < pool_size;it++)
450 ✔
780
                {
781
                        unsigned i = std::uniform_int_distribution<unsigned>(0,pool_keep-1)(re);
400 ✔
782
                        //unsigned j = std::uniform_int_distribution<unsigned>(pool_keep,pool_size-1)(re);
783
                        mutate(pool[i].first,pool[it].first,all_candidates,re,best_gap, evaluated_decks
400 ✔
784
#ifndef NQUEST
785
                                        , quest
786
#endif
787
            );
788
                }
789
                //mutate duplicates
790
                for ( unsigned it = 0; it < pool_size;it++)
1,050 ✔
791
                {
792
                        for (unsigned i = it+1; i < pool_size;i++)
10,500 ✔
793
                        {
794
                                if(pool[it].first->alpha_dominion && pool[i].first->alpha_dominion && pool[it].first->hash().substr(8)==pool[i].first->hash().substr(8)) //ignore commander + dominion
47,500 ✔
795
                                {
796
                                        mutate(pool[i].first->clone(),pool[i].first,all_candidates,re,best_gap, evaluated_decks
277 ✔
797
#ifndef NQUEST
798
                                        , quest
799
#endif
800
                    );
801

802
                                        FinalResults<long double> nil{0, 0, 0, 0, 0, 0, 1};
277 ✔
803
                                        pool[i].second = nil; //lowest score approx Null
277 ✔
804
                                }
805
                        }
806
                }
807
                //calc fitness
808
                for (unsigned it = pool_keep; it < pool_size; it++)
750 ✔
809
                {
810
                        copy_deck(pool[it].first,cur_deck);
700 ✔
811
                        cur_score = fitness(cur_deck, best_score, evaluated_decks, zero_results, skipped_simulations, proc,true);
700 ✔
812
                        pool[it].second = cur_score;
700 ✔
813
                        if(cur_score.points > best_score.points)
700 ✔
814
                        {
815
                                best_score = cur_score;
6 ✔
816
                                best_deck = cur_deck->clone();
6 ✔
817
                                best_gap = check_requirement(cur_deck, requirement
6 ✔
818
#ifndef NQUEST
819
                                                , quest
820
#endif
821
                                                );
822
                                if(it < pool_size-pool_mutate)
6 ✔
823
                                {
824
                                        if (debug_print >= 0)
3 ✔
825
                                                std::cout << "Crossover: " <<std::endl;
3 ✔
826
                                        std::cout << "Deck improved: " << best_deck->hash() <<":";
9 ✔
827
                                }
828
                                else
829
                                {
830
                                        if (debug_print >= 0)
3 ✔
831
                                                std::cout << "Mutation: " <<std::endl;
3 ✔
832
                                        std::cout << "Deck improved: " << best_deck->hash() <<":";
9 ✔
833
                                }
834

835
                                print_deck_inline(get_deck_cost(best_deck), best_score, best_deck);
6 ✔
836
                        }
837
                }
838
#ifndef NDEBUG
839
                if (debug_print >= 0)
50 ✔
840
                {
841
                        std::cout << "---------------POOL---------------" << std::endl;
50 ✔
842
                        for (unsigned it =0; it < pool.size();++it)
1,050 ✔
843
                        {
844
                                if(it==0)std::cout << "---------------KEEP---------------" << std::endl;
1,000 ✔
845
                                if(it==pool_keep)std::cout << "---------------CROSS--------------" << std::endl;
1,000 ✔
846
                                if(it==pool_keep+pool_cross)std::cout << "---------------MUTATE-------------" << std::endl;
1,000 ✔
847
                                auto a = pool[it];
1,000 ✔
848
                                print_deck_inline(get_deck_cost(a.first),a.second,a.first);
1,000 ✔
849
                        }
850
                        std::cout << "---------------PEND---------------" << std::endl;
50 ✔
851
                }
852
#endif
853
        }
854

855
        unsigned simulations = 0;
1 ✔
856
        for (auto evaluation: evaluated_decks)
1,149 ✔
857
        { simulations += evaluation.second.second; }
1,148 ✔
858
        std::cout << "Evaluated " << evaluated_decks.size() << " decks (" << simulations << " + " << skipped_simulations << " simulations)." << std::endl;
1 ✔
859
        print_sim_card_values(best_deck,proc,num_iterations);
1 ✔
860
        std::cout << "Optimized Deck: ";
1 ✔
861
        print_deck_inline(get_deck_cost(best_deck), best_score, best_deck,true);
1 ✔
862
        print_upgraded_cards(best_deck);
1 ✔
863
        return std::make_pair(best_deck->clone(),best_score);
2 ✔
864
}
2 ✔
865

866

867
unsigned factorial(unsigned n)
×
868
{
869
        unsigned retval = 1;
×
870
        for (int i = n; i > 1; --i)
×
871
                retval *= i;
×
872
        return retval;
×
873
}
874

875
void recursion(unsigned num_iterations, std::vector<unsigned> used, unsigned pool, std::vector<const Card*> forts,Process&proc, FinalResults<long double>& best_score,std::vector<const Card*> & best_forts,std::unordered_map<std::string,EvaluatedResults> & evaluated_decks, EvaluatedResults& zero_results, unsigned long& skipped_simulations)
×
876
{
877
        if(used.size()==pool)
×
878
        {
879
                for(auto your_deck : proc.your_decks)
×
880
                {
881
                        your_deck->fortress_cards.clear();
×
882
                        for(unsigned i = 0; i < pool;++i)
×
883
                        {
884
                                your_deck->fortress_cards.emplace_back(forts[used[i]]);
×
885
                        }
886
                }
887
                //sim
888
                std::stringstream ios;
×
889
                encode_deck_ext_b64(ios,proc.your_decks[0]->fortress_cards);
×
890
                auto hash = ios.str();
×
891
                auto && emplace_rv = evaluated_decks.insert({hash,zero_results});
×
892
                auto & prev_results = emplace_rv.first->second;
×
893
                if(!emplace_rv.second)
×
894
                {
895
                        skipped_simulations += prev_results.second;
×
896
                }
897
                auto compare_results= proc.evaluate(num_iterations, prev_results);
×
898
                auto current_score = compute_score(compare_results, proc.factors);
×
899

900
                if(current_score.points > best_score.points+min_increment_of_score) {
×
901
                        best_score = current_score;
×
902
                        std::vector<const Card*> copy_forts(proc.your_decks[0]->fortress_cards);
×
903
                        best_forts = copy_forts;
×
904
                        std::cout << "Forts improved: " << hash << " : ";
×
905
                        print_score_info(compare_results, proc.factors);
×
906
                        print_score_inline(best_score);
×
907
                        std::cout << ": ";
×
908
                        print_cards_inline(best_forts);
×
909
                }
×
910
                used.clear();
×
911
                used.shrink_to_fit();
×
912
        }
×
913
        else
914
        {
915
                for(unsigned i =0;i < forts.size();++i)
×
916
                {
917
                        if(std::find(used.begin(),used.end(),i)==used.end()) //not contained
×
918
                        {
919
                                std::vector<unsigned> tmp_used (used);
×
920
                                tmp_used.emplace_back(i);
×
921
                                recursion(num_iterations,tmp_used,pool,forts,proc,best_score,best_forts,evaluated_decks,zero_results,skipped_simulations);
×
922
                        }
×
923
                }
924
        }
925
}
×
926

927
DeckResults forts_climbing(unsigned num_iterations, Process& proc) {
×
928
        EvaluatedResults zero_results = { EvaluatedResults::first_type(proc.enemy_decks.size()*proc.your_decks.size()), 0 };
×
929
        unsigned pool = std::get<0>(proc.your_decks[0]->variable_forts[0]);
×
930
        std::vector<const Card*> forts(std::get<2>(proc.your_decks[0]->variable_forts[0]));
×
931
        for(unsigned i =0; i < proc.your_decks.size();++i)
×
932
        {
933
                proc.your_decks[i]->variable_forts.clear();
×
934
        }
935
        std::vector<unsigned> used;
×
936
        used.reserve(pool);
×
937
        std::vector<const Card*> best_forts{pool};
×
938
        FinalResults<long double> best_score{0, 0, 0, 0, 0, 0, 0};
×
939
        unsigned long skipped_simulations{0};
×
940
        std::unordered_map<std::string,EvaluatedResults> evaluated_decks{{"",zero_results}};
×
941
        recursion(num_iterations,used,pool,forts, proc,best_score,best_forts,evaluated_decks,zero_results,skipped_simulations);
×
942
        unsigned simulations = 0;
×
943
        for (auto evaluation: evaluated_decks)
×
944
        { simulations += evaluation.second.second; }
×
945
        std::cout << "Evaluated " << evaluated_decks.size() << " decks (" << simulations << " + " << skipped_simulations << " simulations)." << std::endl;
×
946
        std::cout << "Optimized Deck: ";
×
947
        print_cards_inline(best_forts);
×
948
        Deck* tmp = proc.your_decks[0]->clone();
×
949
        tmp->commander = nullptr;
×
950
        tmp->alpha_dominion = nullptr;
×
951
        tmp->cards = best_forts; // return forts
×
952
        return std::make_pair(tmp,best_score);
×
953
}
×
954

955
inline bool contains(std::multimap<FinalResults<long double>, Deck*, std::greater<FinalResults<long double>>> best,Deck* d)
69 ✔
956
{
957
                for(auto it = best.begin();it!=best.end();it++)
374 ✔
958
                {
959
                        if(it->second->hash().compare(d->hash())==0) return true;
374 ✔
960
                }
961
                return false;
962
}
963

964
inline void check_and_update(std::multimap<FinalResults<long double>, Deck*, std::greater<FinalResults<long double>>>& best,Deck* cur_deck,bool & deck_has_been_improved, FinalResults<long double>& best_score )
64 ✔
965
{
966
        auto tmp_result = (best.size()<pool_size)?0.:(std::next(best.begin(),pool_size))->first.points;
64 ✔
967
        //std::cout << "IMP CMD" << std::endl;
968
        if(best_score.points > tmp_result && !contains(best,cur_deck))
192 ✔
969
        {
970
                        deck_has_been_improved = true;
58 ✔
971
                        if(best_score > best.begin()->first){
58 ✔
972
                                        std::cout << "Deck improved: " << cur_deck->hash() <<":" << std::endl;
24 ✔
973
                                        print_deck_inline(get_deck_cost(cur_deck), best_score, cur_deck);
12 ✔
974
                        }
975
                        best.insert(std::make_pair(best_score,cur_deck->clone()));
58 ✔
976
                        if(best.size()==pool_size+1)best.erase(std::prev(best.end(),1));
58 ✔
977
        }
978
}
64 ✔
979

980
DeckResults beam_climb(unsigned num_min_iterations, unsigned num_iterations, std::vector<Deck*> your_decks, Process& proc, Requirement & requirement
1 ✔
981
#ifndef NQUEST
982
                , Quest & quest
983
#endif
984
                )
985
{
986
        if(pool_size==0){
1 ✔
987
                        pool_size = min_beam_size;
1 ✔
988
        }
989

990
        //your_decks.size();
991
        //std::vector<std::pair<Deck*,FinalResults<long double>>> pool;
992

993
        //auto sort = [](FinalResults<long double> l,FinalResults<long double> r) {return l.points > r.points;};
994
        std::multimap<FinalResults<long double>, Deck*, std::greater<FinalResults<long double>>> best;
1 ✔
995
        Deck* cur_deck = proc.your_decks[0];
1 ✔
996

997

998
        EvaluatedResults zero_results = { EvaluatedResults::first_type(proc.enemy_decks.size()), 0 };
1 ✔
999

1000
        std::unordered_map<std::string, EvaluatedResults> evaluated_decks{{cur_deck->hash(), zero_results}};
4 ✔
1001
        EvaluatedResults& results = proc.evaluate(num_min_iterations, evaluated_decks.begin()->second);
1 ✔
1002
        print_score_info(results, proc.factors);
1 ✔
1003
        FinalResults<long double> best_score = compute_score(results, proc.factors); //init sim, todo remove
1 ✔
1004

1005
        unsigned deck_cost = get_deck_cost(cur_deck);
1 ✔
1006
        fund = std::max(fund, deck_cost);
1 ✔
1007
        print_deck_inline(deck_cost, best_score, cur_deck,true);
1 ✔
1008
        std::mt19937& re = proc.threads_data[0]->re;
1 ✔
1009
        unsigned cur_gap = check_requirement(cur_deck, requirement
1 ✔
1010
#ifndef NQUEST
1011
                        , quest
1012
#endif
1013
                        );
1 ✔
1014

1015
        unsigned long skipped_simulations = 0;
1 ✔
1016

1017
        bool is_random = (cur_deck->strategy == DeckStrategy::random) || (cur_deck->strategy == DeckStrategy::flexible);
1 ✔
1018
        bool deck_has_been_improved = true;
1 ✔
1019

1020
        std::vector<const Card*> commander_candidates;
1 ✔
1021
        std::vector<const Card*> alpha_dominion_candidates;
1 ✔
1022
        std::vector<const Card*> card_candidates;
1 ✔
1023

1024
        auto mixed_candidates = get_candidate_lists(proc);
1 ✔
1025
        commander_candidates = mixed_candidates.at(0);
1 ✔
1026
        alpha_dominion_candidates = mixed_candidates.at(1);
1 ✔
1027
        card_candidates = mixed_candidates.at(2);
1 ✔
1028
        // add current alpha dominion to candidates if necessary
1029
        // or setup first candidate into the deck if no alpha dominion defined
1030
        if (use_owned_dominions)
1 ✔
1031
        {
1032
                for(auto i_deck : your_decks) //add all alpha doms
2 ✔
1033
                {
1034
                        if (i_deck->alpha_dominion)
1 ✔
1035
                        {
1036
                                if (!std::count(alpha_dominion_candidates.begin(), alpha_dominion_candidates.end(),i_deck->alpha_dominion))
×
1037
                                {
1038
                                        alpha_dominion_candidates.emplace_back(i_deck->alpha_dominion);
×
1039
                                }
1040
                        }
1041
                }
1042
                if (debug_print > 0)
1 ✔
1043
                {
1044
                        for (const Card* dom_card : alpha_dominion_candidates)
×
1045
                        {
1046
                                std::cout << " ** next Alpha Dominion candidate: " << dom_card->m_name
×
1047
                                        << " ($: " << alpha_dominion_cost(dom_card) << ")" << std::endl;
×
1048
                        }
1049
                }
1050
        }
1051

1052
        //Deck* best_deck = cur_deck->clone();
1053
        //FinalResults<long double> cur_score = best_score;
1054
        //unsigned best_gap = cur_gap;
1055

1056

1057

1058
        //if(your_decks.size()>pool_size) your_decks.resize(pool_size);
1059
        Deck * best_deck = cur_deck->clone();
1 ✔
1060
        auto best_decks = your_decks;
1 ✔
1061
        std::string best_hash = cur_deck->hash();
1 ✔
1062
        unsigned from_slot;
1 ✔
1063
        unsigned count_slot=0; //count iterations
1 ✔
1064
        unsigned dead_slot=0; //last deck improvement
1 ✔
1065
        unsigned mod_permute = 10*9*8*7*6*5*4*3*2*1;
1 ✔
1066
        //FinalResults<long double> tmp_result;
1067
        FinalResults<long double> nil{0, 0, 0, 0, 0, 0, num_min_iterations};
1 ✔
1068
        //sim passed decks
1069
        for(auto ii : your_decks){
2 ✔
1070
                        auto tdeck = ii->clone();
1 ✔
1071
                        copy_deck(tdeck,cur_deck);
1 ✔
1072
                        auto tscore = fitness(cur_deck,nil,evaluated_decks,zero_results,skipped_simulations,proc);
1 ✔
1073
                        if(!contains(best,cur_deck))best.insert(std::make_pair(tscore,tdeck));
1 ✔
1074
                        if(best.size()==pool_size+1)best.erase(std::prev(best.end(),1));
1 ✔
1075
        }
1076
        //fill remaining
1077
        while(best.size()<pool_size){
5 ✔
1078
                unsigned j = std::uniform_int_distribution<unsigned>(0,your_decks.size()-1)(re);
4 ✔
1079
                unsigned i = std::uniform_int_distribution<unsigned>(0,your_decks.size()-1)(re);
4 ✔
1080
                Deck* nxt = your_decks[j]->clone();
4 ✔
1081
                mutate(your_decks[i],nxt,card_candidates,re,cur_gap,evaluated_decks
4 ✔
1082
#ifndef NQUEST
1083
                                        , quest
1084
#endif
1085
        ); //no crossovers here only fill with mutations
1086
                copy_deck(nxt,cur_deck);
4 ✔
1087
                auto tscore = fitness(cur_deck,nil,evaluated_decks,zero_results,skipped_simulations,proc);
4 ✔
1088
                if(!contains(best,nxt)){best.insert(std::make_pair(tscore,nxt));}
4 ✔
1089
        }
1090

1091
        while(true)
31 ✔
1092
        {
1093

1094
#ifndef NDEBUG
1095
                if (debug_print >= 0)
31 ✔
1096
                {
1097
                        std::cout << "---------------BEST---------------" << std::endl;
31 ✔
1098
                        for (auto it = best.begin(); it != best.end();++it)
186 ✔
1099
                        {
1100
                                print_deck_inline(get_deck_cost(it->second),it->first,it->second);
155 ✔
1101
                        }
1102
                        std::cout << "---------------BEND---------------" << std::endl;
31 ✔
1103
                }
1104
#endif
1105
                count_slot = (count_slot+1)%(mod_permute); //TODO Modulo here? % 10*9*8*7*6*5*4*3*2*1
31 ✔
1106
                if(is_timeout_reached()){break;}
31 ✔
1107
                if (deck_has_been_improved)
31 ✔
1108
                {
1109
                        dead_slot = count_slot;
13 ✔
1110
                        deck_has_been_improved = false;
13 ✔
1111
                }
1112
                else if((dead_slot<count_slot && count_slot-dead_slot>=10 )||(count_slot<dead_slot && count_slot+mod_permute-dead_slot>=10 )) // nothing improved for 10 cycles
18 ✔
1113
                {
1114
                        break; // done climbing
1115
                        //TODO climbex like beam climb here
1116
                }
1117

1118
                // get new best decks:
1119
                best_decks.clear();
30 ✔
1120
                for(auto it = best.begin();it!=best.end();it++)
180 ✔
1121
                {
1122
                        best_decks.push_back(it->second);
150 ✔
1123
                }
1124
                //sim deck
1125
                for( auto i_deck :best_decks)
180 ✔
1126
                {
1127
                        copy_deck(i_deck->clone(),cur_deck);
150 ✔
1128
                        best_deck = i_deck->clone();
150 ✔
1129
                        //copy_deck(i_deck,best_deck);
1130
                        best_score = fitness(cur_deck,nil,evaluated_decks,zero_results,skipped_simulations,proc); // grab from stored results or sim it
150 ✔
1131
                        from_slot = std::max(freezed_cards, (count_slot) % std::min<unsigned>(max_deck_len, best_deck->cards.size() + 1));
192 ✔
1132
                        //climb + save best ones to best
1133

1134
                        // commander
1135
                if (requirement.num_cards.count(best_deck->commander) == 0)
150 ✔
1136
                {
1137
                        // << commander candidate loop >>
1138
                        for (const Card* commander_candidate: commander_candidates)
942 ✔
1139
                        {
1140
                                if (best_score.points - target_score > -1e-9)
854 ✔
1141
                                { break; }
1142
                                if (commander_candidate == best_deck->commander)
792 ✔
1143
                                {continue;}
82 ✔
1144
                                //std::cout << "TRY CMD" << std::endl;
1145
                                if(try_improve_deck(cur_deck, -1, -1, commander_candidate,
710 ✔
1146
                                                best_deck->commander, best_deck->alpha_dominion, best_deck->cards, best_score, cur_gap, best_hash,
710 ✔
1147
                                                evaluated_decks, zero_results, skipped_simulations, proc,false
1148
#ifndef NQUEST
1149
                        , quest
1150
#endif
1151
                        ))
1152
                                                {
1153
                                                                check_and_update(best,cur_deck,deck_has_been_improved,best_score);
11 ✔
1154
                                                }
1155
                        }
1156
                        copy_deck(best_deck,cur_deck);
150 ✔
1157
                }
1158

1159
                // alpha dominion
1160
                if (use_owned_dominions && !alpha_dominion_candidates.empty())
150 ✔
1161
                {
1162
                        // << alpha dominion candidate loop >>
1163
                        for (const Card* alpha_dominion_candidate: alpha_dominion_candidates)
414 ✔
1164
                        {
1165
                                if (best_score.points - target_score > -1e-9)
326 ✔
1166
                                { break; }
1167
                                if (alpha_dominion_candidate == best_deck->alpha_dominion)
264 ✔
1168
                                { continue; }
82 ✔
1169
                                if(try_improve_deck(cur_deck, -1, -1, alpha_dominion_candidate,
182 ✔
1170
                                                best_deck->commander, best_deck->alpha_dominion, best_deck->cards, best_score, cur_gap, best_hash,
182 ✔
1171
                                                evaluated_decks, zero_results, skipped_simulations, proc,false
1172
#ifndef NQUEST
1173
                        , quest
1174
#endif
1175
                        ))
1176
                                                {
1177
                                                                check_and_update(best,cur_deck,deck_has_been_improved,best_score);
16 ✔
1178
                                                }
1179
                        }
1180
                        copy_deck(best_deck,cur_deck);
150 ✔
1181
                }
1182

1183
                // shuffle candidates
1184
                std::shuffle(card_candidates.begin(), card_candidates.end(), re);
150 ✔
1185

1186
                // << card candidate loop >>
1187
                //for (const Card* card_candidate: card_candidates)
1188
                for (auto it = card_candidates.begin(); it != card_candidates.end();++it)
2,177 ✔
1189
                {
1190
                        const Card* card_candidate = *it;
2,094 ✔
1191
                        for (unsigned to_slot(is_random ? from_slot : card_candidate ? freezed_cards : (best_deck->cards.size() - 1));
4,188 ✔
1192
                                        to_slot < (is_random ? (from_slot + 1) : (best_deck->cards.size() + (from_slot < best_deck->cards.size() ? 0 : 1)));
4,188 ✔
1193
                                        ++ to_slot)
1194
                        {
1195
                                if (card_candidate ?
2,094 ✔
1196
                                                (from_slot < best_deck->cards.size() && (from_slot == to_slot && card_candidate == best_deck->cards[to_slot])) // 2 Omega -> 2 Omega
2,008 ✔
1197
                                                :
1198
                                                (from_slot == best_deck->cards.size())) // void -> void
86 ✔
1199
                                { continue; }
74 ✔
1200

1201
                                //std::cout << "TRY" << std::endl;
1202
                                //print_deck_inline(get_deck_cost(best_deck),best_score,best_deck);
1203
                                if(try_improve_deck(cur_deck, from_slot, to_slot, card_candidate,
2,020 ✔
1204
                                                best_deck->commander, best_deck->alpha_dominion, best_deck->cards, best_score, cur_gap, best_hash,
2,020 ✔
1205
                                                evaluated_decks, zero_results, skipped_simulations, proc,false
1206
#ifndef NQUEST
1207
                        , quest
1208
#endif
1209
                        ))
1210
                                                {
1211
                                                                check_and_update(best,cur_deck,deck_has_been_improved,best_score);
37 ✔
1212
                                                }
1213
                                //print_deck_inline(get_deck_cost(best_deck),best_score,best_deck);
1214
                        }
1215
                        if (best_score.points - target_score > -1e-9)
2,094 ✔
1216
                        { break; }
1217

1218
                        }
1219
                }
1220
}
1221

1222
        best_deck = best.begin()->second;
1 ✔
1223
        best_score = best.begin()->first;
1 ✔
1224

1225
        unsigned simulations = 0;
1 ✔
1226
        for (auto evaluation: evaluated_decks)
2,485 ✔
1227
        { simulations += evaluation.second.second; }
2,484 ✔
1228
        std::cout << "Evaluated " << evaluated_decks.size() << " decks (" << simulations << " + " << skipped_simulations << " simulations)." << std::endl;
1 ✔
1229
        print_sim_card_values(best_deck,proc,num_iterations);
1 ✔
1230
        std::cout << "Optimized Deck: ";
1 ✔
1231
        print_deck_inline(get_deck_cost(best_deck), best_score, best_deck,true);
1 ✔
1232
        print_upgraded_cards(best_deck);
1 ✔
1233
        return std::make_pair(best_deck->clone(),best_score);
1 ✔
1234
}
2 ✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc