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, $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.
 A: 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
A: 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).
