Pop-out question

[TheTrustedComputer]

Pop-out is a variation of Connect 4 where you can in addition "pop" your own discs along with the normal drops. To pop, remove a disc from the bottom of the board, and the remaining discs in that column fall one by one.

Enough said, I recently created a function in position.hpp that make pop moves described above. Here's a sample on what I wrote so far:

void pop(int col) {
    board col_mask = column_mask(col), botcol_mask = bottom_mask_col(col);
    if (current_position & botcol_mask) {
            if (!canPlay(col)) {
            mask &= mask - (col_mask >> 1);
        }
            else {
                mask ^= ((mask + botcol_mask) & col_mask) >> 1;
            }
            current_position ^= botcol_mask;
            current_position = (current_position & (col_mask ^ board_mask)) ^ (current_position & col_mask) >> 1;
    }
}

While it's not the most optimized, this code gets the job done. Yet I'm lost on how I can use this in the negamax function. Well, how can I use this function so that your solver searches the pop moves as well? There's a possibility that it may need a rewrite, since I'm not fluent on using bitwise operators.

[PascalPons]

The main issue with this additional "pop" rule allowing to remove a disc is that a game can now last forever (for example both player play one disc in the same column and then pop their disc forever).

The depth of the game tree is then unbounded. To handle that kind of game you have to bound your search depth and use heuristics evaluation function for non final positions. Your solver no longer guaranty to be a perfect solver in that case.

The current implementation of the alpha-beta algorithm is optimized to solve perfectly the Connect4 game and does not handle such non-final position heuristic score function. It will unfortunately not be straightforward to adapt the implementation to support it as several optimizations rely on the fact we use an exact score function on final position only.

[TheTrustedComputer]

Ah I see. I've kind of figured that the game might go on indefinitely with neither side winning with your current implementation.

So I need to take a similar approach to chess AIs then?

[TheTrustedComputer]

Okay, I've created the Pop-out game in Zillions of Games, a general game playing program, and I let the AI run infinitely with both sides, and the first player has a forced win in 11 moves (21 plies to be exact) on the starting position. That's roughly half of the moves of a perfect game of Connect 4! Here's a perfect game that's all drops for convenience (a pop will be a letter starting from A to G): 444432655655726226333.

My observations show that after the first player's drop to column 4, the second player has columns 2 through 6 that delays the inevitable the most. Columns 1 and 7 hastens it by 2 moves.

So I concluded subsequently that Pop-Out can't really last forever. Also, a filled up board isn't a draw in this variant. Either player can still make a few more pop moves until the game ends sooner or later. It's only a draw if either player repeats the position thrice (three times) which I think will rarely happen in any case. This draw rule comes from chess that's called a three-fold repetition. I don't think it's stated in the manual of the physical game though. It can possibly aid the search of finding other moves while solving.

That means a perfect Connect 4 Pop-out solver is still probable as these games are much shorter, and a good amount don't take all the way until the board is devoid of empty columns. Interestingly, when a player pops out, there can be positions where both sides have a connection. The player that has made the pop wins; it doesn't matter if the other side has it.