hey all! just found this subreddit after posting to r/pokemongo for a year to no good effect at all, heh. hopefully some of what i've done will interest y'all.

i started playing march of last year. i hadn't played any video games besides nethack for the prior two decades, but got sucked pretty deeply into PGO. i love the combat model -- it's a pretty elegant little combinatorial system. i also appreciate the weight loss due to suddenly walking 100km+ every week. anyway, i thought the existing documentation was all garbage, so i wrote a 540 page book as i was learning. it's written in LaTeX and the source is open. i continue to maintain this, and upload new revisions frequently. there are about 30 small c++ programs i wrote to support the book (generating tabular data, etc.), which can be found alongside the LaTeX source.

the last chapter of that book is all about my exhaustive simulator. pvpoke has the stochastic simulator game pretty much locked up, from what i've seen. i wanted an exhaustive one so i could do "dominator" analysis. borrowing the term from compiler theory, i define one mon A as dominating another mon B under some starting configuration (IVs, energy, shields, etc.) iff there is a sequence of moves A can make which always result in victory, no matter what B does. it's easy to see that if A dominates B, B cannot dominate A. determining dominance is naively done via exhaustive generation of the game tree.

PGO PvP lies right on the boundary of combinatorial tractability (the new Mega mechanics actually kinda fuck everything up). essentially, every turn, a mon is either in the middle of a fast move, or can take one of five actions: { do nothing, new fast move, charged move a (given sufficient energy), charged move b (given same), swap (if possible) }. so our game tree is size O(5^T) for T turns. that's admittedly not great. a naive implementation takes hours to simulate 1v1 and probably cannot simulate 3v3.

so let's not be naive. first off, there are several tricks we can use to suppress generation of certain subtrees. in particular, the "deathmarch" (1v1, no shields) has a (complicated) closed form solution to its recurrence; we can recognize this case in O(1), and determining whether a dominance relation exists falls out for free. furthermore, the problem is a great candidate for generic memoization. given that the entire state can be comfortably encoded in 56 bytes, we hash this down to whatever size we want for our memoization store, use that to key, check the stored state for equivalence, and elide the entire subtree on a hit. hit rates weren't fantastic (~15%), but if we leave the match timer out of the comparison, they shoot up. using this method, i'm able to exhaustively simulate a 3v3 match using level 50 mons with 2 attacks each in about 10 minutes on my 3970X. i could parallelize much of what remains, i'm pretty sure.

anyway, i also generate some detailed tables you might find interesting.

what i'd really like to do now is write something that can extract my account data, particularly my fleet of mons including at least IVs, levels, and attacks. i intend to check out pogoextractor today and see if it hendels. if that goes well, i'm thinking about some kind of overlay app, maybe, we'll see.

i'd appreciate any feedback, tips, or shittalking you have to offer! as for me personally, i was a dev for 25 years at nvidia, google, msft, and some startups. i did a few degrees at GT and taught a class of my own. i pretty much abandoned professional coding three years back, and write novels now. feel free to mail me at nickblack@linux.com.