My interest in Connect Four was captured by the recent contest by jonbush and earthnite. Although I wasn't able to compete due to finals, I'm still planning to make an AI in pure 84 BASIC, and I want it to be really good—it probably won't play perfectly, but it should be fairly close.

Right now I'm still at the planning stage, and trying to find out approach is best.

Earlier, I had planned a simple minimax algorithm to 3 ply, with a heuristic based on the number and quality of threats (threes-in-a-row). With 7 options for each move, that's 343 board position; if I want the AI to take about one minute per move, I'd need to evaluate each board position in 175 ms—and that's not counting overhead. That's a very tight time constraint, and I don't want my AI to take more than about a minute per move. Precomputation could help some (for example, remembering the result of the same board position created by making moves in a different order reduces the number of positions to 238). However, it's probably not possible to make this approach work.

The other approach I was thinking about was entirely rule-based, like jonbush's test AI for the contest. Rather than searching through a game tree, the AI would just entirely follow rules like "move in the center", or "block the opponent's threat". However, this seems like it would be a difficult model to use to cover all possible strategies, and although it wouldn't be as much of a waste of processing power as minimax, it would be a pain to write.

I'm looking for something in the middle, with advantages of both approaches—something that I can improve by giving it more processing time or speeding up the algorithm, but that isn't so ad-hoc or tedious.

Regardless of the approach, my current strategy looks like this:

* Take a winning move
* Block the other player
* Keep the other player from having a forced win in 3 moves...
* Create an odd threat (threat in an odd row), by taking any even squares available to make an odd threat
* Keep the opponent from getting an even threat in the same column as, and lower than, my odd threat. Do this by grabbing squares that the opponent can possibly use to establish an even threat.
* Move in the center column, because every nonvertical winning possibility requires a center space. Expert Play in Connect Four also states that d3, d4, and d5 are crucial squares.
* Maybe an opening book? I don't know how much it would help, though, seeing as there are plenty of forced wins in the opening that such a simple strategy won't be able to solve anyway.

Oh, I forgot to mention: For simplicity, I'll make this for the 1st player, and then expand the code to play as 2nd player sometime later.

I'd appreciate thoughts or advice.

Well, here's an interesting position-- a forced draw. I think being able to recognize these will help an AI.

http://connect4.game-solver.org/?pos=2444425564452662266

Here's another baffling one: why is the best move G1?

http://connect4.game-solver.org/?pos=436444

Okay, I finally have what I think is a good approach. It combines the optimizability of minimax with the efficiency of simple rules.

First, calculate the possession-value of all open squares. The possession-value is how much having one square helps the player that has it. For example:

* A square that wins the game is worth 100
* A square that blocks the other player's win is worth almost as much
* A square that establishes an odd threat (remember, I'm just caring about White for now) is worth a lot.
* A square that blocks the opponent's even threat is worth a lot, especially if the even threat would be low on the board and there's no odd threat for 1st player somewhere else.
* A square that blocks the opponent's second odd threat is worth a lot.
* A square in the d column, or in the 3rd, 4th, or 5th rows, is worth heuristically more.
* A square that cannot connect to 4 in a row anywhere is worth 0.

This could be expanded with additional rules, or even into some sort of search.

From possession-value, we compute the value of all squares, taking into account that occupying a square allows the other player to occupy the square above.

Then we just choose the highest-valued squares out of the 7 (or less) available to move in. If we want randomness we may choose a slightly worse square.

I found this approach by searching for information about VICTOR, which apparently uses numbers from -255 to 255 to determine how desirable squares are. It's nice, because the "don't step below your own threat" rules naturally fall out of considering the value of the squares above.

I'm still not sure if an opening book would help. If I ever finish this project, I'll code the opening book last.

EDIT: I'm scratching the above. Though I have one new idea, I probably won't have time to code anything significant soon. Speed is still very much a problem if I want to search any useful number of positions.

* The board can be represented using five different numbers for X, O, empty even square, empty odd square, and immediately playable square. This allows win checking one ply ahead (one can just sum the values of the squares and check for X-X-X-playable on O's turn, for instance). It also allows searching for odd/even threats more easily, because with a good choice of the values of square types, X-X-odd-odd will have a unique sum.