1
$\begingroup$

(I asked this on StackOverflow, which garnered no response, but maybe this site is a better choice.)

I have a question about game tree planning (I believe this is the correct domain). I am playing a game and want to find the correct sequence of actions at each turn that will maximize my gain at the end of the game. My problem is as follows:

  • There are $100$ turns, $t_1,\dots,t_{100}$.

  • At each turn, a sequence of actions must be taken by the player. (note the sequence $[A,B]$ may not produce the same results as $[B,A]$; in the former $A$ has been undertaken first, and in the latter $B$ has been chosen first.

  • During a turn, choosing one action may prohibit you from choosing other actions later in the same turn. These restrictions are reset when a new turn begins, e.g. sequence: choosing a $B$ may not allow an $A$ to be chosen in the same turn.

My goal is to find the set of actions at $t_1,\dots,t_{100}$ that maximize $f(t_{100})$ where $f(x)$ is a fitness function that is known.

EDIT -- I apologize for any previous vagueness. One real-life analogy is that of solving chess. Let each state (turn) be a description of what pieces are on the board and where. Therefore, we get a tree where the first state (turn) can take you to $10$ possible states (turns) depending on your initial move (move one of $8$ pawns, or either horse). This tree expands very quickly.

Now envision that on each turn instead of making only one move, you can make between 1 and 8 moves in sequence (obviously the order you make these moves alters the state, and thus moving your knight first might be worse for you than moving your pawn first).

So, my problem is performing well in a game of chess where you can make between $1$ and $8$ moves per turn.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I am a bit worried that without further details this question will be hard to answer. As I am pretty clueless on this, I do not (yet) vote to close, but encourage you to give a bit more details. $\endgroup$
    – user9072
    Commented Aug 20, 2011 at 18:47
  • 2
    $\begingroup$ Do you really mean that the quantity to be maximized, f(t100), depends only on the last turn, t100? And that what you are permitted to do at any turn is not constrained by your choices at earlier turns (as "restrictions are reset when a new turn begins")? If so, then what's the point of the first 99 turns? And if not, then please clarify the question. $\endgroup$
    – Andreas Blass
    Commented Aug 20, 2011 at 18:49
  • 1
    $\begingroup$ As is, the question is simply too vague. $\endgroup$
    – Thierry Zell
    Commented Aug 20, 2011 at 19:06
  • 1
    $\begingroup$ voted to close . $\endgroup$
    – Will Jagy
    Commented Aug 20, 2011 at 21:08
  • $\begingroup$ So I am imagining the problem as a tree with each turn taking you from one state of the game to another possible state: t1 -> sequence1 -> state1 -> t2 -> sequence2 -> state2... Therefore, the state100 will in fact have been affected by all your previous choices. So f(t100) will encompass previous decisions. (And yes, your domain of actions "resets" at each turn.) $\endgroup$
    – oisin720
    Commented Aug 21, 2011 at 1:10

2 Answers 2

Reset to default
1
$\begingroup$

This more a set of observations and a request for more detail than an answer.

There is a version of chess where on each turn, the player can make one more standard move than the opponent made just before. Using the notion of ply for half of a turn in standard chess, this version allows white the first ply, black the next two plies, white then gets three, followed by four for black, and so on. Actually, I suspect there is a win for black by or shortly after black's twelfth ply, so this game is not that interesting to analyze.

I suspect your game differs from chess in that there is one player, not two, so that affects the analysis. Other features that would be nice to know are whether one can stop after fewer than 100 moves, if the objective function f is a function of only the game state, or whether the history is involved and contributes to the objective.

One can be flexible in the definition of move, and say that any allowed sequence of actions is a move a.k.a. a turn, and the game tree is thus one with 101 levels and many branches at each node. Thinking in these terms may ease rather than complicate the analysis of your game.

If the optimizing target is evaluated with the game history taken into account, then some sort of monotonicity property will be needed in order to do anything short of a brute force try-all-combinations analysis. By this I mean some game paths have to be obviously nonoptimal to justify not pursuing them (each move takes the player to a worse state than before). Alternatively, you need an example of a good strategy such that, for a large class of outcomes, you can demonstrate that each such leads to a suboptimal outcome, and so you do not need to carry out any detailed analysis for those game paths.

If the objective is just a function of state, then you can analyze game positions (states) instead; this may involve much fewer cases to analyze, and the question becomes more about feasibility and less about strategy. Again, knowing a good or near-optimal state is key in avoiding a detailed analysis of much of the state space.

There are similar things that can be said, but at this point knowing more detail would help select the useful things to say.

Gerhard "Ask Me About System Design" Paseman, 2011.08.20

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much for your reply! The problem is similar to your chess example but it seems a bit more difficult since the number of plies per "turn" is not known in advance. Also: there is one player in this game; the game cannot stop before or after 100 turns; and the history is involved only to the point that it has brought the game to the current state (the function only takes into account the details of the current state). Mostly my confusion lay in how to deal with the varying number of plies per turn. My only idea is to actually present an "End Turn" action that the user can take $\endgroup$
    – oisin720
    Commented Aug 21, 2011 at 4:25
  • $\begingroup$ It might be useful then to ask about the part that gives confusion; the current question gives little hint of what your difficulty is. My suggestion that combining several plies into one move may involve lots of different possibilities for a move, but it is clear (to my way of thinking) that a move automatically includes an "End Turn" action (or "Ready To Increment Turn Counter" signal). Gerhard "Ready To Increment Turn Counter" Paseman, 2011.08.21 $\endgroup$
    – Gerhard Paseman
    Commented Aug 21, 2011 at 20:28
0
$\begingroup$

The problem (as vaguely as it is described) seems at least as complex as chess, hence, an exact solution might not be possible. Are you interested in algorithms for finding good (but maybe not optimal) decision trees? I'd suggest trying genetic algorithms (they work very good for Nim, where, in each step, each player decide if it should take 1,2 or 3 sticks).

Does your game end in a similar fashion each time, so that backtracking is feasible? (Chess is not such a game, Nim is).

There are also standard algorithms, such as alpha/beta pruning, and minimax (see wikipedia).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .