# Optimizing A Game Tree

(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, t1,...,t100.

• 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. eg. 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 t1,..,t100 that maximize f(t100) 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.

-
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. – user9072 Aug 20 '11 at 18:47
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. – Andreas Blass Aug 20 '11 at 18:49
As is, the question is simply too vague. – Thierry Zell Aug 20 '11 at 19:06
voted to close . – Will Jagy Aug 20 '11 at 21:08
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.) – oisin720 Aug 21 '11 at 1:10

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.