Hiii! i'm making a bot for "Virus War" (Война Вирусов), a pencil-and-paper game played by students at St Petersburg University in the 1980s. Eventually I'm going to implement monte-carlo tree search, but for now I'm just getting a feel for the size of the search space.
I'm running into some weird behavior when compiling deeply nested iterator s: they compile really slowly!
The long and short of it is that the following code takes 1.87 hours to compile on my M1 MacBook Pro (2021). Here's a link to the full main library.
import main
var
b = board(9,9)
c = 0
for triplets in b.possibleMoveTriplesFor(Player.A):
var b2: Board = b.withPlays(triplets, Player.A)
for triplets2 in b2.possibleMoveTriplesFor(Player.B):
var b3: Board = b2.withPlays(triplets, Player.B)
for triplets3 in b3.possibleMoveTriplesFor(Player.A):
c += 1
echo "play and reply has ", c, " possible moves"
While this sample takes 6 seconds to compile:
import main
var
b = board(9,9)
c = 0
for triplets in b.possibleMoveTriplesFor(Player.A):
var b2: Board = b.withPlays(triplets, Player.A)
for triplets2 in b2.possibleMoveTriplesFor(Player.B):
c += 1
echo "play and reply has ", c, " possible moves"
And this last sample takes 500ms to compile:
import main
var
b = board(9,9)
c = 0
for triplets in b.possibleMoveTriplesFor(Player.A):
c += 1
echo "play and reply has ", c, " possible moves"
Runtime isn't an issue; they take 2s, 70ms, and 2ms to run respectively. Binary sizes range from 90kb to 180kb, so I don't think macros are generating tons of code. Compiling in debug and release doesn't make a difference. It feels like some static analysis pass taking a while.
I'll reduce the full program (~220 LOC) down to a minimal example later, but the gist of it is that each of these iterators is implemented in terms of a bunch of their own nested iterators: possibleMoveTripletsFor is three nested calls to iterator possibleMovesFor, which itself calls another iterator liveCellGroups which itself calls another iterator neighbors which is two nested loops.
My key question is: what's going on here? Also, are long compile times with deeply nested iterators a known problem or should I prep a bug report? I had wanted to avoid allocation so iterators seemed better than returning seq everywhere, but if that's not good style then maybe I should rethink.
Your iterator is
proc withPlay*(b: Board, loc: Loc, player: Player): Board =
var newBoard:Board = b
newBoard[loc] = newBoard[loc] ~> player
return newBoard
## Give all sets of possible move triplets
iterator possibleMoveTriplesFor*(board: Board, player: Player): (Loc, Loc, Loc) =
var seen: HashSet[Board]
seen.incl board
for loc1 in board.possibleMovesFor player:
let b2 = board.withPlay(loc1, player)
if b2 notin seen:
seen.incl b2
for loc2 in b2.possibleMovesFor player:
let b3 = b2.withPlay(loc2, player)
if b3 notin seen:
seen.incl b3
for loc3 in b3.possibleMovesFor player:
let b4 = b3.withPlay(loc3, player)
if b4 notin seen:
seen.incl b4
yield (loc1, loc2, loc3)
Nim iterators are inlined and possibleMoveTriplesFor inserts 3 possibleMoveTriplesFor at each calls, so it does grow exponentially.
You can check in the nimcache directory (or specify a default one with --nimcache:nimcache/my_nimcache) but I'm pretty sure you'll have millions of lines there.
In general it is impossible to store a sequence of all the legal moves in response to other legal moves.
If you want to do Monte-Carlo Tree Search, have a fast sampling function and implement isLegal.
Now in general I don't know how Virus War plays, but looking at:
It's quite similar to Go and you might want to read on the CFG theory (Common Fate Graphs). Tracking those makes captures O(1) instead of having to process a long linked-list of moves and all their neighbors. https://github.com/mratsim/golem-prime/blob/master/src/core/c_groups.nim#L85-L91
That's the surprising bit! The files in nimcache aren't much bigger than the actual binaries. With a clean nimcache, the 500ms build (one nested level) is about 600kb in total, and the 6s build (two nested levels) is only about 800kb. I'll let the 2h build start and get back to you, but even then, the entire binary was only 180kb.
What do you mean by linked lists of moves and neighbors? I thought iterators work on control flow, not allocations.
Thanks for the MCTS hints. I was going to wind up writing the MCTS differently with less nesting anyways; I mostly brought this up because I'm curious about what it reveals about nim's compiler.
What do you mean by linked lists of moves and neighbors? I thought iterators work on control flow, not allocations.
It's not about low-level allocation / control-flow but high level algorithm and data structures.
In go neighboring stones live or die together, or are captured together, in a group.
Common Fate Graphs represent and allow to determine life-and-death in a very easy and O(1) check instead of counting empty neighbors at each life-and-death check. That counting takes O(4n) with n being the length of the group and the 4 is because in go you have 4 neighbors (no diagonals).
Now in general I don't know how Virus War plays.
For anyone curious about the game:
I found the rules explained in English here: https://www.iggamecenter.com/en/rules/viruswars
And here is a playable version vs AI (3 moves variant): https://metaschool.ru/pub/games/viruswar/viruswar.php