DEV: optimizations on Game class

pwyq / Fill-Game

Two Player (Adversarial) Version of Fillomino | (Depth-First) Proof Number Search, Monte Carlo Tree Search, Minimax, Negamax, Alpha-beta pruning

GNU General Public License v3.0

2 stars 0 forks source link

DEV: optimizations on Game class #56

Closed pwyq closed 1 year ago

pwyq commented 1 year ago

simplify if-condition in getPossibleMove !(!A and B) -> !(!A) or !B -> A or !B -> A (the last transition is because is_expanded_ has the same effect as possible_moves_.empty()
combine getEmptyPositions and getFilledPositions
early return for flood fill (for size > value case)
remove valid game string checking upon game creation
- only check at the very first
major data structure change: std::unordered_map<Pos, std::vector<uint8_t>> to std::vector<Pos, uint8_t> for sorting 695f96d6e8a07770e22600eea3ec89278d54633c. we examine the smallest value first

close #25

pwyq commented 1 year ago

new: new old: old

This is on a medium test case. In order: nega-ab-tt, dfpn, mini-ab-tt, pns. The memory usage increased 4.6%, 2.7%, 15.6% and 13.7% respectively. The time usage decreased 9.2%, 8.9%, 6.5% and 10.5% respectively.

>>> (4317-4124)/4124
0.0467992240543162
>>> (3744-3644)/3644
0.027442371020856202
>>> (9988-8639)/8639
0.15615233244588494
>>> (21696-19072)/19072
0.13758389261744966
>>>
>>>
>>> (132.032-119.896)/132.032
0.09191711100339318
>>> (167.53-152.577)/167.53
0.08925565570345612
>>> (446.487-417.723)/446.487
0.06442292832714057
>>> (439.069-392.88)/439.069
0.10519758853392068

pwyq commented 1 year ago

Figure_3

latest result with move ordering changed. notable change: PNS memory usage cut in half; huge time improvement for alpha-beta based algos. BAD: time increased for PN-based algos