Finding all nodes at a specific depth

Sound interesting, but what is exactly your question? Or am i missing something?

Couldn't you just perform a depth first search down to N on the current state? Each successor node would take a list of nodes already visited to ensure that when generating child nodes they wouldn't include your previously visited nodes on this path?

Im asking for insight in how to build a near ideal implementation. Im trying to see if I can be clever and avoid the obvious DFS because with a little thought it becomes clear that it is likely not viable.

When I tested the MCTS on the iPad, it took about ~10,000 playouts to perform well. Changing the search depth made this in 5 to 20 seconds. That implementation's performance was dominated by the function which tested if the game had been won. This function had to check 28 squares, to detect if a sequence of length >= 4 occured. Search depth was usually around 15 ply if I remember correctly, but was usually increased to unbounded as the game progressed. Potentially, this is something like ~5 million squares being visited.

Now in Ramses, there are 38 nodes. Determining the random move will dominate the performance. There are always 4 pieces per player. Each piece moves 1..8 places. Assuming the pieces are randomly placed on the nodes, this gives a (napkin math) average 4 to 5 (lets call it 4.5). 18 nodes have 1 outgoing edge, 2 have 2, 6 have 3, 10 have 4, and 2 have 10. That averages to ~2.63 so we can roughly estimate that per turn we would have to visit 2.6^4.5 = 74 nodes for each of the 4 pieces (so about 300 nodes). Let me pull a number out of thin air and guess that each piece can move to about 5 valid spaces per turn. So 20 possibilities for populating the first two values of the 4-tuple describing your turn.

When you move the enemies piece in the second half of your turn, a naive implementation would have to repeat this process ~20 times, because each one of the ~20 possibilities for the first half of your move changes the game state. This is approximately 6000 nodes visited *per ply*. Assuming a similar MCTS search horizon of 15 ply, and 10,000 playouts, this is about a BILLION nodes visited. Even if you somehow only had to expand 600 nodes per ply, this takes the MCTS run time into the territory of several minutes.

The special squares breaks the property of orthogonal grid movement that nodes are either accessible by an even or odd number of moves, regardless of path.

Now, is it a good idea to call MCTS to calculate the 4-tuple necessary to describe your entire turn (which of your pieces, its destination, which of their pieces, its destination), or should you simply call it for each of the two moves?

Earlier today I decided against using 22 nodes with variable edges, because then you would potentially need a 6 tuple to describe your turn.

Are any memoization techniques worthwhile? What about:


function buildPotentialMoves
for every node alpha within allNodes
for i=1..8
alpha.moves = {}
run DFS, assuming empty board, max depth 8
for every node (leafNode) expanded by DFS:
if leafNode is not contained within alpha.depth then
table.insert(alpha.moves[depth], leaf)
table.insert(alpha.moves[depth][leaf], path)
-- where path is the set of squares which must be empty for this end node to be a viable destination



function findAllValidMoves(fromNode, moveDepth)
valid = {}
for every unoccupied leafNode in alpha.moves[moveDepth]
for every path in alpha.moves[moveDepth][leafNode]
sentinel = true
for every node in path
if node == occupied then sentinel = false
if sentinel = true then
table.insert(valid, leafNode)
goto label
:label


I need to go to bed, but Ill do some napkin math to see if that technique is viable. It seems like verifying that a path to a location is valid would be quicker in the long run. A one time start up cost might be acceptable for my purposes, especially since it could be saved to disk.

Whoops, looks like the indentation in the CODE tags didnt work out quite right. Cant find an edit button, but it should be readable.

Hmm, it's an interesting problem. Maybe some sort of dynamic programming algorithm could be used. I can see that there will be many paths that could be shared (at least partially) by multiple pieces.

For example, if there are two adjacent pieces, "A" that moves N squares at a time and "B" that moves N-1 squares at a time, if A moves one square towards B and ends up adjacent to B, then B's full set of moves will be a subset of A's set of moves as long as they don't overlap with A's first move.

Good lord, this is the Tron lightbike game turned into a chess-like. ;)