aboutsummaryrefslogtreecommitdiff
path: root/metasol.hpp
blob: 57c6dfbdd4b743eab7fedcd7aac191ec0c7df362 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
/**
 * @file metasol.hpp
 * @author Tom Harley
 *
 * A header file exposing the API information for `metasol`, a system for using
 * solitaire solvers that can see all cards to solve games without knowing where
 * the face-down cards are.
 *
 * Using `metasol` typically requires creating a few callback functions, putting
 * together one @ref ms_game_state , one @ref ms_rules , and one
 * @ref ms_settings , and passing them to @ref ms_run .
 */

#ifndef METASOL_H
#define METASOL_H

#include <list>
#include <vector>
#include <random>

#include <stdint.h>
#include <string.h>

#include "ctpl/ctpl_stl.h"

/**
 * Rule describing how the stock is used.
 */
enum stock_deal_t {

    /**
     * Cards are taken from the stock and placed into the waste.
     */
    STOCK_TO_WASTE,

    /**
     * A card is taken from the stock and placed on the top of each tableau
     * pile.
     */
    STOCK_TO_TABLEAU,

    /**
     * Cards are taken from the stock and placed into the hole.
     */
    STOCK_TO_HOLE
};

/**
 * Converts a string to a stock deal method.
 *
 * @param str The string to convert.
 * @returns A stock deal method represented by the given string.
 */
stock_deal_t str_stock_deal(char *str);

/**
 * Converts a build policy to its string representation.
 *
 * @param sd The build policy to convert.
 * @returns The string representation of the given build policy.
 */
const char *stock_deal_str(stock_deal_t sd);

/**
 * Rule to describe which cards are face-up at the beginning of the game.
 */
enum face_up_policy_t {

    /**
     * All cards on the tableau are face-up.
     */
    ALL_CARDS_FACE_UP,

    /**
     * Only the top cards of tableau piles are face-up.
     */
    TOP_CARDS_FACE_UP
};

/**
 * Converts a string to a face-up policy.
 *
 * @param str The string to convert.
 * @returns A face-up policy represented by the given string.
 */
face_up_policy_t str_face_up_policy(char *str);

/**
 * Converts a face-up policy to its string representation.
 *
 * @param fup The face-up policy to convert.
 * @returns The string representation of the given face-up policy.
 */
const char *face_up_policy_str(face_up_policy_t fup);

/**
 * Rule describing how many foundations piles start with a initial card.
 */
enum foundations_init_t {

    /**
     * No foundations start with cards.
     */
    NO_FOUNDATION_INIT,

    /**
     * Only one foundation starts with a card.
     */
    ONE_FOUNDATION_INIT,

    /**
     * All foundations start with one card each.
     */
    ALL_FOUNDATIONS_INIT
};

/**
 * Converts a string to a foundation initialisation policy.
 *
 * @param str The string to convert.
 * @returns A foundation initialisation policy represented by the given string.
 */
foundations_init_t str_foundations_init(char *str);

/**
 * Converts a foundation initialisation policy to its string
 * representation.
 *
 * @param fip The foundation initialisation policy to convert.
 * @returns The string representation of the given foundation initialisation
 * policy.
 */
const char *foundations_init_str(foundations_init_t fip);

/**
 * The different card suits.
 */
enum card_suit {
    HEARTS,
    SPADES,
    CLUBS,
    DIAMONDS
};

/**
 * An array containing the different card suits.
 */
extern card_suit SUITS[4];

/**
 * The different card ranks.
 */
typedef uint8_t card_rank;

/**
 * Convert the character representation of a card's rank to its data
 * representation.
 *
 * @param r The card's rank as a character.
 * @returns The card's rank as type `card_rank`.
 */
card_rank char_rank(char r);

/**
 * A collection of rules that together describe a solitaire game.
 */
typedef struct {

    /**
     * The number of piles in the tableau (`0` if no tableau).
     */
    unsigned tableau_size;

    /**
     * The number of decks used for dealing.
     */
    unsigned deck_count;

    /**
     * The highest rank of card included in the deck(s).
     *
     * A standard set of French playing cards includes up to rank 13 (kings).
     */
    unsigned max_rank;

    /**
     * Whether or not a "hole" pile is used in the game.
     */
    bool hole_present;

    /**
     * Whether or not foundations are used in the game.
     *
     * The number of foundations is always set to `4 * deck_count`.
     */
    bool foundations_present;

    /**
     * How to initialise the foundations.
     */
    foundations_init_t foundations_init_cards;

    /**
     * Whether or not foundations have a set base rank that is always used.
     */
    bool specific_foundations_base;

    /**
     * The base rank for foundations.
     *
     * Only used if `specific_foundations_base` is `true`.
     */
    card_rank foundations_base;

    /**
     * Whether or not the tableau should be dealt as a digonal deal.
     *
     * If set to `false`, all piles in the tableau are dealt to equal sizes.
     * Diagonal deals are the default in games such as Klondike.
     */
    bool diagonal_deal;

    /**
     * The number of cell piles in this game.
     */
    unsigned cells;

    /**
     * The number of cells that start containing a card.
     */
    unsigned cells_pre_filled;

    /**
     * The number of cards in the stock at the start of the game.
     */
    unsigned stock_size;

    /**
     * The stock deal method.
     */
    stock_deal_t stock_deal_method;

    /**
     * The number of cards dealt from the stock at a time.
     *
     * Only takes effect when using an appropriate stock deal method.
     */
    unsigned stock_deal_count;

    /**
     * Whether or not the waste can be emptied into the stock once the stock is
     * empty.
     *
     * Also controls whether or not the stock contains hidden cards: if the
     * stock can be redealt, its cards can be searched through at the start of
     * the game, and so its contents are not hidden.
     */
    bool stock_redeal;

    /**
     * The number of cards in the reserve at the start of the game.
     */
    unsigned reserve_size;

    /**
     * Whether or not the reserve is stacked.
     */
    bool reserve_stacked;

    /**
     * The face-up policy for revealing cards at the start of the game.
     */
    face_up_policy_t face_up_policy;

    /**
     * The number of sequences.
     */
    unsigned sequence_count;

    /**
     * The number of cards in the accordion at the beginning of the game.
     */
    unsigned accordion_size;

} ms_rules;

/**
 * Representation of a card.
 */
typedef struct {

    /**
     * The card's suit.
     */
    card_suit suit;

    /**
     * The card's rank.
     */
    card_rank rank;

    /**
     * Whether the card is face-up (revealed) or face-down (hidden).
     */
    bool hidden;

} ms_card;

/**
 * Representation of a pile or list of cards.
 */
typedef std::vector<ms_card> ms_card_pile;

/**
 * Convert a string to a card.
 *
 * @param str The string to convert.
 * @param fd Whether or not the card is face-down.
 * @returns The card represented by the given string.
 */
ms_card ms_str_card(char *str, bool fd);

/**
 * Representation of a move.
 *
 * Stock moves are treated differently from regular moves.
 */
typedef struct {

    /**
     * Whether or not the move is a stock move.
     */
    bool stock;

    /**
     * The index of the pile that this move places cards in.
     */
    unsigned to;

    /**
     * The index of the pile that this move takes cards from.
     */
    unsigned from;

    /**
     * The number of cards to move.
     *
     * A value above `1` indicates a built group move.
     */
    unsigned size;

} ms_move;

/**
 * Representation of a deal-in-progress.
 *
 * Basically just the exact status of each pile.
 */
typedef struct {
    std::vector<ms_card_pile> foundations;
    ms_card_pile stock;
    ms_card_pile waste;
    std::vector<ms_card_pile> tableau;
    ms_card_pile hole;
    std::vector<ms_card_pile> cells;
    ms_card_pile reserve;
    std::list<ms_card> accordion;

    /**
     * The seed used for random generation of the game-state.
     */
    long seed;

    /**
     * The moves made in order to get to this game-state.
     */
    std::vector<ms_move> moves_made;

} ms_game_state;

/**
 * The reported status of a voter after a run.
 */
enum finished_state {

    /**
     * The voter found a solution to the game-state it was given.
     */
    SOLUTION_FOUND,

    /**
     * The voter exhausted all possible moves and could not find a solution to
     * the game-state it was given.
     */
    NO_SOLUTION,

    /**
     * The voter was unable to find a solution _or_ exhaust all options before
     * stopping for some other reason.
     */
    CANCELLED

};

/**
 * A collection of information pertaining to a single vote by a voter.
 */
typedef struct {

    /**
     * How the vote concluded.
     */
    finished_state result;

    /**
     * The moves the voter took to reach its solution.
     */
    std::vector<ms_move> moves;

} vote;

/**
 * The type for the _thoughtful run_ callback.
 *
 * This type of callback is used to check if a solution can be found for the
 * deal in its current game-state - if there's no solution when the face-down
 * cards are known, then there is no point to continue running voters.
 *
 * @param game_state The current game-state of the game.
 * @param rules The rules used in this game.
 * @param user_data A pointer to data given to `metasol` by the user.
 * @returns How the thoughtful run concluded.
 */
typedef finished_state thoughtful_run_func_t(ms_game_state *game_state,
        ms_rules *rules, void *user_data);

/**
 * The type for the _voter run_ callback.
 *
 * This type of callback is used to run a voter once.
 *
 * @param game_state The current game-state of the game.
 * @param rules The rules used in this game.
 * @param move_buffer Where to put the moves the voter used to reach a solution.
 * @param requested_moves The number of moves to put in the buffer. This is only
 * a guideline - the buffer should accept any number of moves. If set to `0`. no
 * guideline is given: as many moves as possible should be placed in the buffer.
 * @param user_data A pointer to the data given to `metasol` by the user.
 * @returns How the voter run concluded.
 */
typedef finished_state run_func_t(ms_game_state *game_state, ms_rules *rules,
        std::vector<ms_move> *move_buffer, unsigned requested_moves,
        void *user_data);

/**
 * The type for the _solved_ callback.
 *
 * This type of callback is used to check if the game-state is a solution to the
 * deal.
 *
 * @param game_state The current game-state of the game.
 * @param rules The rules used in this game.
 * @param user_data A pointer to the data given to `metasol` by the user.
 * @returns `true` if the given game-state is a solution to the game described
 * by the given rules; `false` otherwise.
 */
typedef bool solved_func_t(ms_game_state *, ms_rules *, void *);

/**
 * A collection of settings used by `metasol`.
 */
typedef struct {

    /**
     * The _voter run_ callback function.
     */
    run_func_t *run_func;

    /**
     * The _thoughtful run_ callback function.
     */
    thoughtful_run_func_t *thoughtful_run_func;

    /**
     * The _solved_ callback function.
     */
    solved_func_t *solved_func;

    /**
     * The number of moves to request for the move buffer.
     */
    unsigned reserved_move_count;

    /**
     * User-specified data that is passed as a final argument to all callback
     * functions.
     */
    void *user_data;

    /**
     * The maximum number of threads to run concurrently.
     *
     * This works best when set to the number of cores on the system.
     */
    unsigned max_concurrent_threads;

    /**
     * How many games to run in parallel.
     */
    unsigned max_concurrent_games;

    /**
     * How many voters are initially used to determine the next move.
     */
    unsigned initial_vote_count;

    /**
     * The number of voters to add to the voting pool each time voters are
     * added.
     */
    unsigned vote_increase_step;

    /**
     * The magnitude with which to increase the number of voters being used each
     * time voters are added.
     *
     * Applied after @ref vote_increase_step.
     */
    unsigned vote_increase_magnitude;

    /**
     * The maximum number of voters to use when determining the next move.
     */
    unsigned max_vote_count;

    /**
     * The ratio of votes required for a satisfying vote. This is honoured
     * unless the max voter count has already been reached.
     */
    unsigned agree_ratio;

    /**
     * The seed used when shuffling face-down cards around.
     */
    unsigned long seed;

    /**
     * The random generator used when shuffling face-down cards around.
     */
    std::mt19937 rng;

    /**
     * `true` when running infinitely.
     */
    bool forever;

} ms_settings;

/**
 * Get the number of foundations in the game.
 *
 * @param rules The rules describing the game.
 * @returns The number of foundation piles used in the game described by the
 * given rules.
 */
unsigned foundation_count(ms_rules *rules);

/**
 * Get the total number of piles in the game.
 *
 * @param rules The rules describing the game.
 * @returns The total number of piles used in the game described by the given
 * rules.
 */
unsigned total_pile_count(ms_rules *rules);

/**
 * Get a pile from its index.
 *
 * @param game_state The game-state to get the pile from.
 * @param index The index of the pile.
 * @returns The pile referred to by the given index in the given game-state.
 */
ms_card_pile *get_pile_by_index(ms_game_state *game_state, uint8_t index);

/**
 * Get some default rules to build on to make a game.
 *
 * Sensible entries here reduces the number of rules that have to be listed
 * explicitly in a rules file.
 *
 * @returns Some default rules.
 */
ms_rules fetch_default_rules();

/**
 * Get some default settings.
 *
 * @returns Some default settings.
 */
ms_settings fetch_default_settings();

/**
 * Generates an initial game-state based on a generator seed.
 *
 * @param seed The seed to use when generating the deal.
 * @param rules The rules to follow when generating the deal.
 * @returns A game-state from the game described in the given rules.
 */
ms_game_state random_game_state(long seed, ms_rules *rules);

/**
 * Runs `metasol`.
 *
 * @param game_state The game-state to solve from.
 * @param rules The rules describing the game.
 * @param settings The settings to use when running.
 * @param thpool The thread pool to use.
 */
int ms_run(ms_game_state *game_state, ms_rules *rules, ms_settings *settings,
        ctpl::thread_pool *thpool);

/**
 * Constructs and attempts to solve a single game-state.
 *
 * @param rules The rules of the game-state to create.
 * @param settings The settings to run the solver with.
 * @param seed The seed for generating the game-state.
 */
int ms_run_single(ms_rules *rules, ms_settings *settings, unsigned long seed);

/**
 * Constructs and plays games until terminated.
 *
 * @param rules The rules of the game-state to create.
 * @param settings The settings to run the solvers with.
 * @returns 0.
 */
int ms_run_many(ms_rules *rules, ms_settings *settings);

int ms_run_from_file(ms_rules *rules, ms_settings *settings,
        const char *filename, ctpl::thread_pool *tp);

#endif /* METASOL_H */