Question

I've been working on making a game solver for about a month now, trying a variety of strategies but most have been oriented around brute force. This works for simpler cases of the game but it fails for more complex cases (higher game tree depth). Here is an abstract formulation of the game:

1) There is a set of possible actions to do, A.

2) Applying an action to a state produces a probabilistic distribution of possible states. apply(A, s) = [[s1, p1], [s2, p2], [s3, p3]]

3) The game ends when a goal state has been reached.

4) Each state has a score associated with it.

3) There are two types of goal states, "Success" states where the score of the state is the score of it's predecessor state, and "Failure" states where the score is 0.

5) The goal is to produce a strategy that maximizes the average score at the end of the game.

6) There are no cycles. All paths have finite lengths.

I formulated the game in the most abstract sense possible because it's the one I think people will be most familiar with. My current strategy is a simple depth first search that caches unique states to prevent work duplication. This works up until roughly 200 million unique states which is when I run out of memory. I want to know if there are any clever algorithms for the general case of the game before I start breaking apart the lower level details to find optimizations. If anyone is interested in the details of how state transitions are generated I can provide them. Here are some ways I have of reducing the problem to known problems.

1) A stochastic Markov Decision process where the state reward function is 0 for any non goal state and the score of the goal state otherwise. I know the general algorithm for MDPs is not very efficient, but certain classes of MDPs have efficient solutions. Does this problem fit one of those certain classes?

2) A stochastic longest path problem in a directed acyclic graph with negative edge weights.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top