3 ms·

I am building a card game engine in typescript. A simple AI based on monte carlo tree search requires me to copy the gamestate a lot. And it's always a list of

by dtx1 3y ago

I am building a card game engine in typescript. A simple AI based on monte carlo tree search requires me to copy the gamestate a lot. And it's always a list of cards that i'm modeling so I really need to deepclone arrays.

chatmasta 3y ago
Can you not serialize this state to/from JSON? I'd encourage trying to reduce the state to be JSON-serializable, and then re-initialize any "classes" after deserializarion with a .fromJSON() method (the "factory method" pattern) - in fact you can even call such .toJSON() "replacer" [0] and .fromJSON() "reviver" [1] functions in a callback passed to JSON.stringify and JSON.parse. [0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/JSON/stringify#the_replacer_parameter https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/JSON/parse#the_reviver_parameter https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- dtx1 3y ago
  I haven't really gotten to the point where anything works but doing the serialize de/serialize combo is possible. The issue is, that I am thinking about doing this not a few hundred times but more like several million times (preferably per minute), so i'll likely have to implement several competing versions and benchmark them. The full idea is implement a deckbuilding game like magic and use genetic algorithms and montecarlo simulation to balance the card pool. But that requires millions of games with millions of simulations to work. So i'll see if it's even possible.
  - chatmasta 3y ago
    If you really need maximum performance then you probably don't want to deal with JS objects at all. (But you should benchmark it first... you might be surprised how far V8 gets you with JIT optimizations - although serialization will be a bottleneck whether you're using JSON or deepClone.) For example, as one potential alternative, you could invent a scheme for encoding the state in a bit array, and then find clever bitwise operations for inspecting or manipulating it. For inspiration, many chess engines store game state in a "bitboard" [0] which is a 64 bit representation of some (partial) state of the board. Of course, at this point you might not even want to be using JavaScript... maybe you could write the hot path in Rust, compile it to wasm, and then use JS for orchestration/UI. [0] https://en.wikipedia.org/wiki/Bitboard#Chess_bitboards https://en.wikipedia.org/wiki/Bitboard#Chess_bitboards
    - dtx1 3y ago
      That is really useful, thank you! I think first stage is building the game and see if the whole Genetic Algorithm/Monte Carlo Setup actually works, even if the first few iterations take weeks. The issue is I want to figure out if there are combos that I don't even know exist that are unusually strong. Basically make sure I balance the card pool but automatically.
      - chatmasta 3y ago
        > first stage is building the game Yeah :) Definitely better to make it slow but ship it. Then make it fast later.
- jholman 3y ago
  How is this better than deepcopying? Deserializing requires paying all the same costs as deepcopying, both in terms of compute time and in terms of memory usage, but it also incurs the extra costs of parsing. I'm not saying that there wouldn't be benefits to having a serializer for their gamestate (because there would surely be benefits), but I just cannot understand this as an alternative for the problem they described.
jholman 3y ago
There are at least two obvious alternatives to (fully) deepcloning. First, many "everything must be immutable" libraries provide data structures that give operations that feel like mutations (but actually are not), and many of those can re-use all the old objects that are not mutated. This could save a lot, relative to full naive deepcopies. Or it could save very little, depending on what you're doing. Second, if you have the ability, you can always mutate before recursion and then revert when the recursion finishes. This could potentially be very tricky, because it's not always easy to revert mutations. As such, it's not a good plan for a prototype, but if you can get it right, this could make your tree search wayyyyy faster.

by dtx1 3y ago

chatmasta 3y ago

Can you not serialize this state to/from JSON? I'd encourage trying to reduce the state to be JSON-serializable, and then re-initialize any "classes" after deserializarion with a .fromJSON() method (the "factory method" pattern) - in fact you can even call such .toJSON() "replacer" [0] and .fromJSON() "reviver" [1] functions in a callback passed to JSON.stringify and JSON.parse. [0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/JSON/stringify#the_replacer_parameter https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe... [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/JSON/parse#the_reviver_parameter https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

dtx1 3y ago
I haven't really gotten to the point where anything works but doing the serialize de/serialize combo is possible. The issue is, that I am thinking about doing this not a few hundred times but more like several million times (preferably per minute), so i'll likely have to implement several competing versions and benchmark them. The full idea is implement a deckbuilding game like magic and use genetic algorithms and montecarlo simulation to balance the card pool. But that requires millions of games with millions of simulations to work. So i'll see if it's even possible.
- chatmasta 3y ago
  If you really need maximum performance then you probably don't want to deal with JS objects at all. (But you should benchmark it first... you might be surprised how far V8 gets you with JIT optimizations - although serialization will be a bottleneck whether you're using JSON or deepClone.) For example, as one potential alternative, you could invent a scheme for encoding the state in a bit array, and then find clever bitwise operations for inspecting or manipulating it. For inspiration, many chess engines store game state in a "bitboard" [0] which is a 64 bit representation of some (partial) state of the board. Of course, at this point you might not even want to be using JavaScript... maybe you could write the hot path in Rust, compile it to wasm, and then use JS for orchestration/UI. [0] https://en.wikipedia.org/wiki/Bitboard#Chess_bitboards https://en.wikipedia.org/wiki/Bitboard#Chess_bitboards
  - dtx1 3y ago
    That is really useful, thank you! I think first stage is building the game and see if the whole Genetic Algorithm/Monte Carlo Setup actually works, even if the first few iterations take weeks. The issue is I want to figure out if there are combos that I don't even know exist that are unusually strong. Basically make sure I balance the card pool but automatically.
    - chatmasta 3y ago
      > first stage is building the game Yeah :) Definitely better to make it slow but ship it. Then make it fast later.
jholman 3y ago
How is this better than deepcopying? Deserializing requires paying all the same costs as deepcopying, both in terms of compute time and in terms of memory usage, but it also incurs the extra costs of parsing. I'm not saying that there wouldn't be benefits to having a serializer for their gamestate (because there would surely be benefits), but I just cannot understand this as an alternative for the problem they described.

jholman 3y ago

There are at least two obvious alternatives to (fully) deepcloning. First, many "everything must be immutable" libraries provide data structures that give operations that feel like mutations (but actually are not), and many of those can re-use all the old objects that are not mutated. This could save a lot, relative to full naive deepcopies. Or it could save very little, depending on what you're doing. Second, if you have the ability, you can always mutate before recursion and then revert when the recursion finishes. This could potentially be very tricky, because it's not always easy to revert mutations. As such, it's not a good plan for a prototype, but if you can get it right, this could make your tree search wayyyyy faster.