I wrote a thesis on reinforcement learning in Warcraft II. Our system started with zero knowledge and learned to beat the existing AIs about half the time.

It did this by sending its single starting unit to attack the opponent's single unit, before either could use theirs to build more.

Two identical, weak units fighting was just a coin flip.