| |
| A connection game is a type of abstract strategy game in whichplayers attempt to complete a specific type of connection with theirpieces, such as Gonnect, Hex, Shannon switching game, tic-tac-toeand so on. In this paper, we propose a new connection game on a concave-polygon-freeplanar graph, where one player is based on edge connectivity and theother is based on vertex connectivity. Instead of playing in turn,they begin their turns according by tossing a biased coin. We prove that the new connection game are well defined i.e., the game cannot end in a tie. To oursurprise, we show that the fair probability is closely connectedwith percolation threshold, a mathematical term related to percolation theory which is the formation of long-range connectivity in random systems. Furthermore, a dynamic programming algorithm is presented to compute the fair probability of an arbitrary planar graph . |
|
| Keywords:algorithm; combinatorial game theory; computer science; graph theory |
|
