Hello GameDev.net community! I'm not sure if this is the right forum or topic to post, but this is my first post so please bear with me.
I'm working on a program that will solve any Connect 4 position on the fly. However, the program is specifically designed to solve Pop Out. Pop Out is a variant where it plays exactly like the original except players can additionally remove one of their disks from the bottom of the board causing every other disk that was on top fall down. I'm an intermediate Connect 4 player myself, and I have been coding in general for a while, but this is my first time creating an AI solver for ANY game. As far as I know, there are NO Connect 4 Pop Out programs anywhere on the Internet. I also plan to solve more Connect 4 variants like Power Up and Pop 10. I will want to use this codebase to solve those respective variants. All of the code is written in C.
Currently, my program uses a one-dimensional array data structure for the game board. Some other variables include another array to keep track of the heights of each column, a move counter to determine which side to move, and a self-constructed vector containing played moves. I have developed functions to do both drop and pop moves and their undo equivalents. I also have a function to check whether either player has a four in a row in all vertical, horizontal, and diagonal directions. There can be a possibility of both players having a four in a row after a pop. The player who popped is declared the winner. The only code that is missing is a check if the position was repeated at least three times. This is because a full board is no longer a draw under this variant.
I used a depth-limited minimax with alpha-beta, and "pseudo" iterative deepening to solve the position. What I mean by pseudo is that it has a static move order from central columns to the extreme sides of the board; there's no move ordering at all. My program was able to solve Pop Out to a first player win at a depth of 21 in about 20 minutes alone. This code works even if there's a simultaneous connection as the algorithm ignores the opposing side anyway.
My next objective is to add a transposition table. This is where I get stuck as I have no idea how to implement it. So far, I used Zobrist hashing to hash the board, and it is working fine with drop moves through debugging. Unfortunately, it doesn't really work with pop moves, even after numerous attempts at changing lines of code and debugging it. What am I doing wrong? The hashes do not match after I drop some disks, and then reach the same position one move before with pops. This is needed for my repetition code and among other things to optimize my program. For the transposition table, I know I need key and value pairs as it's technically an array of hashtables, but what other data do I need to store into the transposition table? What should I do with it from the minimax function?
