0
\$\begingroup\$

Alright, we have a large set of possible moves (what the player is allowed to do). We also have a well defined state of success that defines the desired goal. We want to generate a configuration where for the purpose of this question, only 1 set of moves leads to a victory within k steps. We also have a solver that can find all possible solutions for a given configuration problem.

For example let's take Chess, how would you place a set of chess pieces on a board such that only a specific set of moves by White will result in Check Mate?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Just a short comment: The first part of your question sounds like there is only one player. The second part with chess sounds like there are two players. Which is the case? As I do think there is a big difference. For example for chess the result highly depends on the opponent's moves. \$\endgroup\$ Commented Sep 28, 2015 at 8:52
  • \$\begingroup\$ Perhaps start from a check mate position and then do a few moves, so that the player will require to do the same moves in "reverse" to check mate ? \$\endgroup\$ Commented Sep 28, 2015 at 8:56

2 Answers 2

Reset to default
1
\$\begingroup\$

I would say brute force it. Let's keep chess as the example.

Let's say you created a chess AI. You could make two of the AIs play a game, while retaining a move history. Once the game is complete, mark the game-board as a "Solved State".

You can generate a bunch of these, tweaking the AI to ensure nice board placement. Would be cool to generate these with grand-master level AI bots.

Then, rewind the game back a few moves to get your "Starting State".

Run your solver from the Starting State, through every single possibility possible based on the rules. You would need to limit the maximum number of moves your solver would attempt (max k steps).

Keep track of each path in a Tree Structure, so that you can ensure that you do not run the same path twice. Once you are done checking all possibilities, look at the tree structure to see if you only have 1 path that is successful at a given size (length of path).

You could run this automatically overnight and see how many you get in the morning.

\$\endgroup\$
1
\$\begingroup\$

That sounds like a constraint problem.

I'd recommend writing a model for an existing solver such as Minion or GECODE, perhaps using the Savile Row modeling assistant. These implement many advanced optimisations for solving constraint problems and are likely to be much easier to change and more performant than a hand-hacked solution.

Savile Row in particular comes with a directory full of examples for solving similar well-known constraint problems, such as n-queens, knight's tour and Sokoban.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.