dutchflyboy - Hmm i think you can avoid that , or maybe simply i got what you said wrong but consider something like this ;
xmap = Get Current Map;
Create first node , add xmap to it ;
Layer 1 - My moves
-Get available moves according to parents map , do all stuff but don't save updated map to node. layer 1 nodes
Layer 2 - His moves
-Get his parents map ( which is still xmap ) , get available moves according to that , Update both this nodes and parent nodes moves on that map & save it to layer 2 nodes. ( now layer 2 nodes has updated map )
Repeat the process.
Well you don't really need to save all map if you don't want to ; you can just save differences , apply & get moves & de-apply (uh , surely there is a word for that but... ) & update differences list etc.
Since layer 1-3-5 doesn't update the map , there will be nodes where opponent and player have same square's (aka tie). Then all you need is a little if clause to stop branching after tie situation.
With something like this ; both player and his opponent will have 3 available moves in the first step of your example (i loved it by the way). And since north & south gives negative voronei territory results ( player is purple right? ) , bot will surely prefer west & tie.
Now I really hope you wont come up & say "i wasn't talking about that , you got me wrong" , which is very probable since i just woke up

( i can also use this as an excuse for grammar mistakes and weird explanation

)