title: Find optimal/good-enough strategy and AI for the game 'Proximity'?
body: <p>'<strong><em>Proximity</em></strong>' is a strategy game of territorial domination similar to Othello, Go and Risk.
  Two players, uses a 10x12 hex grid. Game invented by <em>Brian Cable</em> in 2007.</p>
  
  <p>Seems to be a worthy game for discussing a) optimal algorithm then b) how to build an AI.<br>
  Strategies are going to be probabilistic or heuristic-based, due to the randomness factor, and the insane branching factor (20^120).
  So it will be kind of hard to compare objectively.
  <strong>A compute time limit of 5 seconds max per turn seems reasonable => this rules out all brute-force attempts.</strong> (Play the game's AI on Expert level to get a feel - it does a very good job based on some simple heuristic)</p>
  
  <p><strong>Game:</strong> <a href="http://www.briancable.com/view.php?id=1" rel="nofollow noreferrer">Flash version here</a>, <a href="http://www.iapplemobileapps.com/iproximity.html" rel="nofollow noreferrer">iPhone version <em>iProximity</em> here</a> and many copies elsewhere on the web
  Rules: <a href="http://www.freegamesnews.com/en/?p=1164" rel="nofollow noreferrer">here</a></p>
  
  <p><strong>Object</strong>: to have control of the most armies after all tiles have been placed. You start with an empty hexboard. Each turn you receive a randomly numbered tile (value between 1 and 20 armies) to place on any vacant board space. If this tile is adjacent to any ALLY tiles, it will strengthen each of those tile's defenses +1 (up to a max value of 20). If it is adjacent to any ENEMY tiles, it will take control over them IF its number is higher than the number on the enemy tile.</p>
  
  <p><strong>Thoughts on strategy:</strong> Here are some initial thoughts; setting the computer AI to Expert will probably teach a lot:</p>
  
  <ol>
  <li>minimizing your perimeter seems to be a good strategy, to prevent flips and minimize worst-case damage</li>
  <li>like in Go, leaving holes inside your formation is lethal, only more so with the hex grid because you can lose armies on up to 6 squares in one move</li>
  <li>low-numbered tiles are a liability, so place them away from your main territory, near the board edges and scattered. You can also use low-numbered tiles to plug holes in your formation, or make small gains along the perimeter which the opponent will not tend to bother attacking.</li>
  <li>a triangle formation of three pieces is strong since they mutually reinforce, and also reduce the perimeter </li>
  <li>Each tile can be flipped at most 6 times, i.e. when its neighbor tiles are occupied. Control of a formation can flow back and forth. Sometimes you lose part of a formation and plug any holes to render that part of the board 'dead' and lock in your territory/ prevent further losses.</li>
  <li>Low-numbered tiles are obvious-but-low-valued liabilities, but high-numbered tiles can be bigger liabilities if they get flipped (which is harder). One lucky play with a 20-army tile can cause a swing of 200 (from +100 to -100 armies). So tile placement will have both offensive and defensive considerations.</li>
  </ol>
  
  <p>Comment 1,2,4 seem to resemble a minimax strategy where we minimize the maximum expected possible loss (modified by some probabilistic consideration of the value ß the opponent can get from 1..20 i.e. a structure which can only be flipped by a ß=20 tile is 'nearly impregnable'.)
  I'm not clear what the implications of comments 3,5,6 are for optimal strategy.
  Interested in comments from Go, Chess or Othello players.</p>
  
  <p>(The sequel <a href="http://www.briancable.com/proximityhd/" rel="nofollow noreferrer">ProximityHD for XBox Live, allows 4-player -cooperative or -competitive local multiplayer</a> increases the branching factor since you now have 5 tiles in your hand at any given time, of which you can only play one. Reinforcement of ally tiles is increased to +2 per ally.)</p>