A Collectible Card Game (CCG) Deck Recommender just for fun.
The paper is available on arxiv: Q-DeckRec: A Fast Deck Recommendation System for Collectible Card Games
All deck recommendation codes are available under combinatorial_search directory.
Overview
The paper tries to solve the following combinatorial optimization problem:
We mainly have three models: "rl_prtr" refers to Q-DeckRec, 'sl' refers to the ad-hoc baseline using Monte-Carlo simulations, and "ga" refers to Genetic Algorithm.
We prepare two sets of problem instances: "synthetic neural network"and "deck recommendation". The latter is the real problem on which we conduct experiments in the paper.
All commands below are assumed to be executed under the combinatorial_search directory.
Synthetic Neural Network Problems
The synthetic neural network problem assumes f() is a function parameterized by a neural network. It also assumes x_o is fixed in all problem instances. Therefore, Q-DeckRec will learn a search policy to find the best x_p against the fixed x_o, while x_p is initialized randomly. This problem is the best starting point to experiment Q-DeckRec and other algorithms before moving to real deck recommendation problems.
Generate problems
# generate a problem where there are 20 total cards and deck size is 6
# the problem will be serialized in test_probs folder
# pv=0 means the index of the problem instance is 0. You can change
# this index to create different problem instances.
python3.6 problem_generator.py --k=20 --d=6 --env=env_nn --pv=0 --env_seed=303
Before test rl_prtr, we need to generate a pre-training RL model
# the model will be saved in prtr_models/
python3.6 Q_comb_search.py --env_name="env_nn" --k=20 --d=6 --test_period=100 --load=0 --fixed_xo=1 --env_dir="test_probs/prob_env_nn_pv0_envseed303" --learn_wall_time_limit=5000 --root_dir="prtr_models"
# use tensorboard to check progress
tensorboard --logdir=prtr_models/rl_prtr_env_nn_k20_d6_t5000/
What you will see in tensorboard is:
x axis represents learning episode and y axis represents the win rate of x_p^d against x_o. The learned search policy will be more and more stable to approach the best x_p.
Test different methods
# final results will be stored in test_result.csv in the problem folder
python3.6 experimenter.py --method="rl_prtr" --prob_env_dir="test_probs/prob_env_nn_pv0_envseed303" --prtr_model_dir="prtr_models/rl_prtr_env_nn_k20_d6_t5000/optimizer_model_fixedxoTrue/qlearning"
python3.6 experimenter.py --method="ga" --wall_time_limit=5 --prob_env_dir="test_probs/prob_env_nn_pv0_envseed303"
Deck Recommendation Using MetaStone + GreedyMove AI
Generate problems
# the environment name is "env_greedymove"
# you can also refer to the script combinatorial_search/commands/env_greedymove/prob_generate.bash
python3.6 problem_generator.py --k=312 --d=15 --env=env_greedymove --pv=0 --env_seed=303
Genetic Algorithm
# time limit 25 min (1500 seconds)
python experimenter.py --method="ga" --wall_time_limit=1500 --prob_env_dir="test_probs/prob_env_greedymove_pv0_envseed303"
Q-DeckRec
# collect samples and train a neural network model as described in the paper
# model will be saved in prtr_models/rl_prtr_env_greedymove_k312_d15_t259200
python Q_comb_search.py --env_name="env_greedymove" --k=312 --d=15 --test_period=99999999 --load=0 --env_dir="test_probs/prob_env_greedymove_pv0_envseed303" --learn_wall_time_limit=259200 --root_dir="prtr_models"
# test
python experimenter.py --method="rl_prtr" --prob_env_dir="test_probs/prob_env_greedymove_pv0_envseed303" --prtr_model_dir="prtr_models/rl_prtr_env_greedymove_k312_d15_t259200/optimizer_model_fixedxoFalse/qlearning"
MC-simulation baseline
# collect training data. x: pairs of randomly generated (x_o, x_p), y: win rate
# --load=0 or 1 decides whether to load an existing dataset or not
# data collection will continues until reaching wall time limit (in seconds)
python3.6 supervise_learning.py --env_name="env_greedymove" --k=312 --d=15 --load=0 --wall_time_limit=259200
# test it and results will be stored in test_result.csv in the problem folder
python3.6 experimenter.py --method="sl" --prob_env_dir="test_probs/prob_env_greedymove_pv0_envseed303" --prtr_model_dir="prtr_models/sl_env_greedymove_k312_d15_t259200" --wall_time_limit=259200 --sl_num_trial=67
Report results
python3.6 report.py --env=env_greedymove
The following table shows test results. Some numbers might be slightly different than the paper due to different randomness.
| Average Win Rate | |
|---|---|
| Genetic Algorithm 25 min | 0.95 |
| Monte Carlo 67K | 0.84 |
| Q-DeckRec 3 days | 0.93 |
File Structure in combinatorial_search directory
commands
slurm commands to run experiments
environment
Combinatorial Optimization environment set up. shadow.jar is the simulator for simulating Hearthstone matches controlled by greedy-based AI.
See https://github.com/czxttkl/metastone for how shadow.jar is generated.
GA
Contains an example implemented by DEAP library
prioritized_exp
A folder which contains all needed functions for prioritized experience replay (together with prioritized_memory.py)
prtr_models
Not checked in the repository. But this directory stores all trained models.
resource
Record what cards included in the simulator
slurm
Slurm outputs files for debugging
test_probs
Serialized test problems and test results
experimenter.py
A helper to evaluate different algorithms on test problem instances.
experimenter_cpu_time.py
A helper to evaluate CPU time usage of experimenter.py
genetic_algorithm.py
Helper code to implement genetic algorithm's mutate and crossover operators
logger.py
A logger helper to log test statistics on files.
Q_comb_search.py
A helper to kick off QLearning training. It allows the tuning of various hyperparamters.
QLearning.py
Implement Q-Learning with MLP-based function approximator. It has two main functions: collect_samples keeps trying different x_o vs. x_p and store experiences (s, a, r, s', a') into a prioritized experience replay; learn keeps using the stored experiences to update MLP paramters.
random_search.py
Randomly search for decks (each random deck needs a win-rate evaluation, which is costly)
report.py
Report tool. For example, you can use python3.6 report.py --env=env_greedymove to check the current results for the experiment in our paper.
supervise_learning.py
Learn a win-rate predictor and then use Monte Carlo simulation to sample random decks and pick the one with the highest predicted win rate
supervise_learning_cpu_time.py
Only for measuring CPU time of supervise_learning.py
tfboard.py
Tensorboard helper
Requirement
Python 3.6. Please also see requirements.txt
Java 1.8
Credits to https://github.com/jleclanche/fireplace