Questions About Fixed Arrays and Unsafe Code

So, I'm reworking an alpha/beta pruned min/max search tree using the new job system. I'm using a NativeArray with IJobParallelFor. I've a GameState struct in that array that contains only bitable types, and primitive arrays of bitable types. All of the members are readonly (until C# 7 lets me declare the entire struct as readonly).

I understand that the arrays are (somewhat deceptively) still references to memory outside the struct, but I can declare the struct 'unsafe', and make the arrays fixed length.

Setting aside the fact that enumerations are for some reason ineligible for fixed arrays, (That seems silly.)

Should I be using unsafe structs/fixed arrays inside the job system? It claims to allow 'safe' code, but I can't figure out what I'm supposed to be doing for collections. It seems that NativeArrays cannot be members of a struct in a NativeArray, because they require a bitable type while not being a bitable type theirselves? ...What's the right way to do this?

My struct looks like this now.

Code (CSharp):

1. public struct GameState : IComparable<GameState>, IDisposable
2. {
3.     const int MAX_ROWS = 76;
4.     const int MAX_NODES = 64;
5.     const int MAX_ARCS = 228;
6.     const int MAX_DEPTH = 3;
7.     readonly internal byte depth;
8.     public readonly byte whosTurn; // would be bool, but not bitable for some reason
9.  
10.     public readonly ushort player1Score;
11.     public readonly ushort player2Score;
12.     public readonly NativeArray<byte> moveList;
13.     // public readonly byte[] moveList;
14.     public readonly NativeArray<EntityState> rowStates;
15.     //public readonly EntityState[] rowStates;
16.     public readonly NativeArray<EntityState> nodeStates;
17.     // public readonly EntityState[] nodeStates;
18.     public readonly NativeArray<EntityState> arcStates;
19.     // ThenSomeMethodsAndStuff();
20. }

 

I implemented a MonteCarlo tree search myself with job system, this is what I did:
- for the tree, I allocate upfront a NativeArray<Node>, where node is a blittable struct containing only what I need about the game state (visit count, reward, parent/first child/next sibling indices, move taken, etc...)
- my GameState is similar to yours, except not readonly. I process one game state at a time, recycling the instance for the entire simulation (+1 for the root state). each iteration does indeed have to walk the tree to reach the leaf node.
- each move is a blittable struct
- other needed state is allocated "globally" (per mcts instance) and conservatively (i.e. I need to know the max number if legal moves)

so, each iteration looks like:
- copy data from 'root' state to 'current' state
- select a node
- walk the game tree by applying each move in the selected path to the 'current' game state
- do expansion, simulation, and back-propagate the results

if you already have your logic written functionally with immutable state, you can use a double-buffering for that:
- apply your game rules ((currentGameState, move) -> nextGameState)
- copy nextGameState into currentGameState

 

Thanks very much for your reply. I'm unsure what you mean about double-buffering though.
How did you implement collections in your gamestate struct? e.g. lets, say, word-tiles in Scrabble. Fixed-length 'unsafe' things, or did you use a NativeArray somehow? Am I correct in thinking I can't make a NativeArray containing NativeArrays?

 

double buffering = have 2 memory locations for your data, one for reading and one for writing, and swap their role (not the contents) each iteration

my game state contains NativeArrays, and is used directly in the job as a single field (i.e. I do not have any NativeArray<GameState>).
I process one game state at a time, and I only need to save scalar data between iterations (yes I recalculate multiple times the same game tree path if I select the same node more than once)

so my data is:

• GameState rootState (contains native arrays)
• GameState currentState
• NativeArray<Node> tree (Node contains per-iteration data, e.g. float reward, int visitCount, corresponding action, etc...)
• (additional helper buffers)

and my logic is:

• start with real game state in rootState
• set currentNode = root node (index 0 in array)
• loop:
  • copy rootState into currentState, randomize unknown variables
  • selection: loop (until child node exixts)
    • get legal actions from current state
    • select child of currentNode that correspond to a legal action
    • apply that action to currentState, then set currentNode = child
  • expansion: create a new child of currentNode, apply corresponding action to currentState)
  • simulation: play the game to the end
  • backpropagation: walk the tree from last currentNode via node.parent until root is reached, and update the rewards

ps: if you need to save the game state into each node, you can use the following tricks:

• encode the game state into a single NativeArray<byte or int> allocation
• wrap your components with properties that either access a single value at a fixed offset (e.g. current turn is data[0], etc.) or using NativeSlice (e.g. data.Slice(offset, length).SliceConvert<YourElement>() for easier access
• allocate a single NativeArray<byte> of length = gameState.data.Length * treeLength
• copy game states into that buffer using buffer.Slice(index*gameStateLength, gameStateLength).CopyFrom(gameState.data) or directly use that slice as the game state data allocation

beware that the buffer slices will have the safety restriction applied for the entire array (i.e. you can't (still) have multiple slices of the same array into the same job, and if you declare write access, you cannot access the entire buffer until the job complete)

 

Thanks. I hadn’t thought to use NativeSlice. I think I may be misusing IJobParallelFor as a collection of potential child states of root, and I should’ve instead scheduled a separate job for each child state.