Help with computing something in Hex

Is there a formula/program that can, given one filled-in cell of a Hex board, compute the odds of a player winning if every other cell is filled in with a 50% chance of either color? Better yet, is there a way to compute it on nonstandard graphs, such as Quax or ConHex boards? If not, is there at least a program that can generate filled boards as such so I can manually compute estimations?

Computing it would seem to require enumerating all the positions, which is way too big for normal sized boards.

You could get a pretty good estimate with a simple Monte Carlo simulation. A million trials wouldn't be too much work for modern computers, and would give decent accuracy (typically three digits). You can reduce variance and get better accuracy by stepping through all positions systematically in the first few ply, doing k trials per position (for some small k).

You just need a program that can detect the winner on a full board (the faster the better). If you don't want to roll your own, maybe check out the open source U of Alberta Hex programs (Wolve and MoHex), or the older program Six by Gábor Melis.

BTW, MoHex is doing something similar when it does the evaluation of a position, so that might be your best bet.

http://webdocs.cs.ualberta.ca/~hayward/hex/

I doubt computing it would require enumerating all positions. I'm pretty sure this is a problem that should be in reach for a graph algorithm expert. Unfortunately, I am not one :p

seconded

however, I do agree with darse that just by simulation you will get a precise enough answer (although no proof)

Simply randomly filling all cells with colours is not the proper way to approach this question. Given that the blue player played last, you have to paint one random cell red then a random cell blue and so on. In other words you have to restrict your random distribution -- on the 13x13 board to cases where the red player will end up with 85 cells and the blue player with 84 cells.

This gives a total of 169! / (84!*85!) = 4,57 * 10^49 end positions, random colouring would give 2^169 = 7,48 * 10^50 end positions.

With this numbers Monte Carlo seems to be the best way to attack the problem.

Actually, "randomly filling all cells with colours" is the proper way to approach my question, as I'm not concerned with only legal Hex positions.