jkomoros / boardgame

An in-progress framework in golang to easily build boardgame Progressive Web Apps
Apache License 2.0
31 stars 4 forks source link

Improve performance of moveProgressionChecks #640

Open jkomoros opened 6 years ago

jkomoros commented 6 years ago

As of fixing #633 they're pretty expensive because we redo each one per move, which mainly duplicates the logic.

Will get worse after fixing #627

jkomoros commented 6 years ago

Also consider memoizing Name, IsFixUp and others if that's a performance bottleneck

jkomoros commented 4 years ago

The move progression logic is redone, form scratch, for each and every move that's in a progression, constantly. Ideally in the same run we'd be able to reuse the same logic for moves that are strictly later in the progression.

Conceptually for each FixUp run (or other mass legal check), you want to run each larger move progression group ONCE and detect which move names would be legal next in that group right now, and reject everything that's not in that set.

This is much easier if we do #761 by the way because then that logic will be factored out of an imperative legal method and exposed in a declarative way so we can know for sure that it's not doing extra or weird logic.

jkomoros commented 4 years ago

AddOrderedForPhase already creates a single implied move progression and shares it with all moves in that progression.

We could even do something silly simple (and hacky) like memoizing the next legal names in the move progression, and storing it based on the current state pointer, and throwing out and regenerating the result when the state pointer doesn't match.

... Although that would thrash and fail in cases where there were multiple active games, since it's tied to the game type, not the game. You could just store n cached results in a LRU cache, but that's also a hack. States themselves could have a place to stash data that is not persisted to signal to other users of that state, which is a bit weird...

Before committing this, benchmark it and see how much faster it is to see if the complication is worth it

jkomoros commented 4 years ago

One way to do this is for the move group, when the state is not yet having its results cached, try proposing every single move name in the group and seeing which ones are legal and cahcing that. That's basically equivalent to the current way, just with the calculation all front loaded to the first move in the progression to be tested.

The other approach is to provide the existing tape, read up until it's consumed, and then query the move progression group about what move names might be legal next. This would require modifying the signature of MoveProgressionGroup to not be Satisfied but rather nextLegalMoveNames []string. But hmmm that's not right, because some move progression groups are nested inside of larger ones and would be fully satisfied and done.

The signature would be `Satisfied(tape MoveGroupHistoryItem) (rest MoveGroupHistoryItem, legalNextNames []string, error). If rest is nil, then legalNextNames says which moves it would consider legal (which should be zero-len if there are no names it would accept itself). if rest is non-nil, then that means there's more tape to consume and this group can't consume it.

Hmm, this logic is hard: imagine a sub-group that is fully consumed on the tape, that could take one more of the last move thatw as applied (it's allowMultipleInProgression), but also the next sibling group could accept moves, too. So you need some way to say "I could take more of these moves named FOO, or not, whatever" as well as "I must have at least some of foo". If the latter, don't ask the next move group sibling. If the former, DO ask the next move sibling for what moves it would accept if given an empty tape, and combine the two sets.