Checking forbidden moves in Renju

Question

I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works.

Renju is a board game played on a 15x15 Go board. There are two players in the game, which we will call black and white, and they place stones of their color on the board turn by turn. Black starts first, and whoever gets 5 pieces of their color in a row wins (so it's basically like tic-tac-toe but on a bigger board).

However, this game is not balanced for white (since black starts first), so there are some restrictions on what moves black can make. Here are some of them:

1. Black cannot create an overline. (6 or more stones in a row)
2. Black cannot make a 3x3 fork, which look like these:

Take a look at the fork at the upper-right corner. You can see that if black places a stone at J, then they will create two 'open three's (an open four is a pattern of four stones in a row with both sides open, and an open three is a pattern of three stones such that adding a stone to it creates an open four) and they are guaranteed to win since white cannot block everything in time. Same thing goes for other forks shown here.

The problem I am facing is that I cannot detect these 3x3 forks just by detecting patterns. Here is a more concrete example of what I mean.

We would like to know whether black creates a 3x3 fork by placing a stone at A or not. Therefore, we must check whether placing a stone there creates two 'open three's at the same time.

Here, we've placed a black stone at A. The horizontal bar is an open three, since we can create an open four by placing a black stone at B. However, the diagonal is not an open three, since placing a black stone at C would not leave the bottom end of the four to be open, whereas placing a black stone at D would not leave the top end open (since black is not allowed to place a piece there, otherwise it will create 6 stones in a row or an overline). Therefore, this is not a 3x3 fork, and so black is allowed to place a stone at A.

My main issue is that the problem of checking this seems to be recursive, in that in order to know if I can place a piece at the point A, I need to know whether I can place a piece at other points of the board. My naive idea at first was to use dynamic programming, but I found that it's not likely to work since the forbidden moves at turn $n$ is quite different from those at turn $n - 2$, and are heavily dependent on what black and white do in the turns between. I'd like to know if there is an efficient algorithm to check this sort of thing. I'm not experienced with algorithms at all, so please pardon me if this is a trivial question. Thanks for reading till the end.

[Here is a link for a better explanation of the game in case mine isn't good enough.]

Answer 1

The rules are recursive in some sense, but note that the recursive parts depend on collections of one stone larger. Since 5 is the largest number of stones to check for, the depth of the recursion is constant, so you only need to test a constant number of board positions to check if a move is valid.

In particular, to test for a 3x3 fork, you need to check for a valid open three. A valid open three is a set of stones that can be expanded into a valid open four (which involves not making the 4x4 fork), which is a set of stones which can be expanded to a valid five (which involves not making an overline).