9x9 board game odds

[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.

[retina]

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.

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 ⁸⁰C₄₀ positions to examine.

[R. Gerbicz]

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?

[Batalov]

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.

[Batalov]

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.

[Batalov]

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/

[R. Gerbicz]

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 .

[petrw1]

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.