Sign in to follow this  
Kethis

Finding all nodes at a specific depth

Recommended Posts

Kethis    122
I am trying to extend an iPad based LUA implementation of monte carlo tree search (that I wrote) to play the board game Ramses. http://boardgamegeek.com/boardgame/1529/ramses

I know that my performance bottleneck will be in pathfinding. Looking at the code's (barely acceptable) run time per playout in other (simpler) games I strongly suspect that Ramses will run (unacceptably) slower.

Ramses can be represented as a 38 node directed cyclic graph. Nodes have 2 to 4 incoming edges, and 2 to 4 outgoing edges. It is a 2 player game and each player has 4 pieces. When a piece moves, it must travel exactly N-many spaces (where N varies and is >=1). Its path can not self intersect nor can it cross through a node occupied by another piece.

There are two groups of 9 nodes each which are occupied whenever a single piece is in them. [I believe it is also impossible to cross through either group multiple times in one move. The website containing the rules is down.] You could of course also represent these groups of nodes as a single node each, with variable edges. This would drop the game down to 22 nodes (which is how many the human player sees).

Specifically what I want to optimize is: given the board's current state, the piece to move, and a number N, find all points reachable after exactly N-many non-intersecting edge traversals (subject to the board's unique stipulation, outlined in the paragraph above).

Currently, I am CPU-constrained, not memory-constrained.

Thank you in advance!

Share this post


Link to post
Share on other sites
DarrylStein    653
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?

Share this post


Link to post
Share on other sites
Kethis    122
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:

[CODE]
function buildPotentialMoves
for every node alpha within allNodes
for i=1..8
alpha.moves[i] = {}
run DFS, assuming empty board, max depth 8
for every node (leafNode) expanded by DFS:
if leafNode is not contained within alpha.depth[i] 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
[/CODE]

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.

Share this post


Link to post
Share on other sites
Kethis    122
Whoops, looks like the indentation in the CODE tags didnt work out quite right. Cant find an edit button, but it should be readable.

Share this post


Link to post
Share on other sites
jefferytitan    2523
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. ;)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this