20200622, 02:43  #1 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
4,391 Posts 
9x9 board game odds
There's a game that is played on a 9x9 grid with a free space in the middle. Each player has 40 pieces to be played in any of the 80 remaining tiles, one at a time, in alternation. I'm interested in the proportion (or equivalently the number) of arrangements in which the 80 tiles can be placed on the board such that no player gets 5 in a row, orthogonally or diagonally. And, as a more complicated version, how many ways such that neither player gets more than one row of 5 on the board.

20200622, 04:06  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·3^{2}·11·29 Posts 
Quote:
But I suspect that would be doable by brute force if one incorporated mirroring, backtracking and early termination detection. A lot fewer than ^{80}C_{40} positions to examine. 

20200622, 06:33  #3 
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}·5^{2}·7 Posts 

20200622, 07:19  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10001110100111_{2} Posts 
*Excellent note that every gomoku and/or renju player would applaud. At least vs exactly.
It is an enormous change to the whole strategy. In most gomoku variants overline is treated as null (in renju for black as a loss), only exactly 5 is a win. Allowing for overlines leads to a duller version suitable for beginners. There is a distinct difficulty for most computer gomoku engines not to fall prey to a skilled human player who detects that the computer is bound to get an 'overline' (6 or 7, with an impossibility to end up with exactly 5) and nonchalantly build their own combination and the computer player loses immediately. 
20200622, 07:41  #5  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,127 Posts 
Quote:
 enum all lines of 5  repeat 10^8 times { . . . throw 40 random black darts (don't count if you hit a past dart, go on until 40), the rest assumed white, . . . sum up all preenum'd lines of 5 (is it or is it not) and . . . record both of the wanted outcomes (A) and (B) . . . clean up } and you will have a fairly accurate estimate. You can estimate a CI of that random process. 

20200622, 07:48  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9,127 Posts 
However, much harder:
assume both players play best strategy, then you have to run some AI research, one of the two things can happen, I would expect  either black wins every time (I suspect that, or else there would be no reason for such arcane opening restrictions in real gomoku and renju), and then your wanted estimate is 0.000  or else (like in othello/reversi 8x8)  with best play it is a draw each time, then your wanted estimate is 1.000 You can also play against Tito Gomoku (in app store); Tokarev's engine is free and very good. I API'd Tito engine into a game club >15 years ago (and nine other board games; from chess to reverse to gomoku and backgammon, and such); and had Tokarev's permission too, at that time it was just a CLI software (no code) and it was a world champion for 2yrs in a row. Another idea, instead of writing a competent engine (which is a lot of time), take CLI version and API against it. He does not release the source understandably. There are >20 AIs to choose from at https://gomocup.org/download/ 
20200622, 09:50  #7  
"Robert Gerbicz"
Oct 2005
Hungary
2^{3}·5^{2}·7 Posts 
Quote:


20200622, 15:32  #8 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
4,391 Posts 
5 only...no bonuses for more.
This is not Gomoku; but dice poker. Either player can use the middle FREE only to complete a row of 5. The game is won when a player get 2 lines of 5 in any direction...with at most 1 overlap. I realize the rules restrict you from choosing any spot but for the sake of this puzzle assume you can. First we wondered how difficult it is to avoid even 1 line of 5. Then if you can compute it; 2 lines allowing 1 overlap. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Scrambling Bob & Alice, encryption for board game play across the net  xilman  Lounge  9  20200321 16:38 
Engineassisted game vs Stockfish, move 36 discussion. Drawn game?  MooMoo2  Other Chess Games  10  20170429 17:39 
A Holy New Board Game  MattcAnderson  Puzzles  2  20151018 09:40 
N queens on an N/N board.  Peter Hackman  Math  4  20080924 16:34 
Board colors  Prime Monster  Lounge  38  20030523 19:14 