mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-06-22, 02:43   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×1,459 Posts
Default 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.
petrw1 is offline   Reply With Quote
Old 2020-06-22, 04:06   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52·229 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
I don't have an answer.

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.
retina is offline   Reply With Quote
Old 2020-06-22, 06:33   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7·199 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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?
R. Gerbicz is offline   Reply With Quote
Old 2020-06-22, 07:19   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×2,281 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
Batalov is offline   Reply With Quote
Old 2020-06-22, 07:41   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
Batalov is offline   Reply With Quote
Old 2020-06-22, 07:48   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Default

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/
Batalov is offline   Reply With Quote
Old 2020-06-22, 09:50   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

7·199 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 .
R. Gerbicz is offline   Reply With Quote
Old 2020-06-22, 15:32   #8
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3×1,459 Posts
Default

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.
petrw1 is offline   Reply With Quote
Reply

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 2020-03-21 16:38
Engine-assisted game vs Stockfish, move 36 discussion. Drawn game? MooMoo2 Other Chess Games 10 2017-04-29 17:39
A Holy New Board Game MattcAnderson Puzzles 2 2015-10-18 09:40
N queens on an N/N board. Peter Hackman Math 4 2008-09-24 16:34
Board colors Prime Monster Lounge 38 2003-05-23 19:14

All times are UTC. The time now is 11:18.

Sat Sep 19 11:18:05 UTC 2020 up 9 days, 8:29, 0 users, load averages: 2.01, 2.02, 1.76

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.