mersenneforum.org 9x9 board game odds
 Register FAQ Search Today's Posts Mark Forums Read

 2020-06-22, 02:43 #1 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 3·1,459 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.
2020-06-22, 04:06   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

131358 Posts

Quote:
 Originally Posted by petrw1 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.

But I suspect that would be doable by brute force if one incorporated mirroring, back-tracking and early termination detection. A lot fewer than 80C40 positions to examine.

2020-06-22, 06:33   #3
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

7×199 Posts

Quote:
 Originally Posted by petrw1 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.
So there is no at least 5 in a line?

2020-06-22, 07:19   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,281 Posts

Quote:
 Originally Posted by R. Gerbicz So there is no at least* 5 in a line?
*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.

2020-06-22, 07:41   #5
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts

Quote:
 Originally Posted by petrw1 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 (A) 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, (B) how many ways such that neither player gets more than one row of 5 on the board.
if the rules are >=5 and that hole in the middle, and players have no interest in outcome and play randomly, then you can sample quite accurately by:
- 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 pre-enum'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.

 2020-06-22, 07:48 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×2,281 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/
2020-06-22, 09:50   #7
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

7×199 Posts

Quote:
 Originally Posted by Batalov if the rules are >=5 and that hole in the middle, and players have no interest in outcome and play randomly, then you can sample quite accurately by: - 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 pre-enum'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.
I've also that in my mind. Generated 1e8 random boards, and counted 8499941 configurations that has no 5 or more same piece in a line. So roughly we are expecting 0.085*binomial(80,40) for the whole board, that is approx 2^72.952 .

 2020-06-22, 15:32 #8 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 437710 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post xilman Lounge 9 2020-03-21 16:38 MooMoo2 Other Chess Games 10 2017-04-29 17:39 MattcAnderson Puzzles 2 2015-10-18 09:40 Peter Hackman Math 4 2008-09-24 16:34 Prime Monster Lounge 38 2003-05-23 19:14

All times are UTC. The time now is 13:24.

Sat Sep 19 13:24:49 UTC 2020 up 9 days, 10:35, 1 user, load averages: 0.92, 1.15, 1.30