I responded to a forum thread about the solvability(is that a word?) of the game Starcraft with my new found knowledge of game theory =) Since it took a while to write, and the thread will disappear under thousands of other threads in a few days, here it is!

"Leaving aside technical issues of APM and micro/macro skills, as I think the OP intended, Starcraft is a game with both simultaneous and sequential moves. The sequential strategy of players may be simplified to be recognised as only the "macro" aspect of the mid to late game, ie. the choice of unit compositions, number of bases to take, choice of tech, etc. which you decide when you are able to effectively scout your opponent's macro strategy. This aspect of SC may be solvable using rollback, as it is possible to come up with strategies to counter your opponent's strats (eg. vults to harass -> goons to defend -> sieged tanks to hold map control -> arbiters to stasis tanks -> vessels to emp arbiters). Again I must emphasise that this is possible because we are ignoring the "skill" of the players and only focusing on the balance of units between Perfect Players. Hence, it is mathematically possible to calculate a rollback equilibrium for this aspect.

The simultaneous aspect of SC occurs when there is strategic uncertainty because of a lack of scouting. This is definitely applicable when choosing the build orders to start the game with (5pool or 12hatch?) when you are uncertain about what your opponent will play. Since SCBW has been played by progamers for 10 years now, and there is no "imba" unstoppable strategy that has been found, we can quite surely say that there is no dominance in any particular build order. It is obvious that there is also no Nash equilibrium for choosing build orders, if not we'll be seeing the same games over and over again. Thus the thing to look for would be a mixed strategy. I do think that a lot of progamers or coaches have already devised rather successful mixed strategies for early game BOs.

Responding to some of the above posts, I do not agree that the "luck/chance" factor is a deterrent to solving the game. We know that a ranged unit has a certain miss chance against a unit up a cliff; the percentage might not be available to the public, but Blizzard certainly knows it. As such, it is theoretically possible to come up with the expected value of attacks that may miss or be dodged. With this expectation, it is now possible to come up with a mixed strategy.

Pathseeking: this does not matter at all with perfect micro. The units should move in Perfect movements, accurate up to the pixel.

Psychological mindgames: This should affect nothing other than the physical skill of a player; in a Perfect situation this can be ignored. I can't remember the proof off the top of my head, but in a zero-sum game such player communications (direct or indirect) can be ignored when devising strategies.

Maps: This is obviously a null point when discussing the THEORETICAL possibility of solving Starcraft. The map changes the expected payout of each strategy, hence all that is required is to alter the mixed strategy or rollback to fit the new payouts of each map.

Like some posters have mentioned, the second game's solution does not work if a player places a coin near the centre of the table. Is there a way to avoid this, or is there a more elegant solution?"

The last paragraph is referring to this puzzle: "There is a circular table and a large pile of quarters. You and a friend take turns placing quarters on the table, such that no two quarters overlap. A player loses if he/she cannot place another quarter on the table. Do you want to move first or second?"

One solution posted was this: "whenever player 1 places a quarter, say in some spot S, you should place a quarter in the spot that is diametrically opposed to S on the table. to see that you will never lose with this strategy, note the following invariant: after you have placed your quarter (on any move), you can spin the table 180 degrees, and the pattern of quarters on the table will not have changed. so if player 1 places a quarter in spot S, then spot S+180 degrees must be free as well ("undo" player 1's last move -- the quarter in spot S -- and apply the invariant)"

I've heard of this before, but can't remember if there was a different solution. Hmm....


EDIT: Alright I've thought up of the solution =D The first mover will win, as he can place the first quarter at the centre of the table, then follow the above solution.