Comparing connect four AI strategies.

Question

I need to design an AI for connect four that beats an AI which just places pieces in random columns. Doing this got me thinking-what is the worst AI I can build to achieve the task? In particular, does my AI need to adapt at all to the other AI's moves to win games the majority of the time?

The strategy I have in mind is very simple-it just places tokens in the first column until the column is filled, then it moves on to the second, etc. Would this work? Would it beat the random AI a most of the time?

Thank you in advance.

Answer 1

Yes, your strategy would beat a random AI most of the time. In fact, even if after four moves, you surrendered, it would still win most the time. In particular, if you go first, then there is a $(6/7)^3\approx .62$ chance that your opponent does not place any tiles into the first column before your fourth move. You would then win, and this is already a majority of the time.

If your opponent goes first, then there is again a $(6/7)^3$ chance that your opponent does not place anything into the first column between your first and fourth move - which would again result in a win assuming your opponent has not already won. One may check that the probability of your opponent winning in the first $4$ turns is no more than the probability of them winning if you played nothing. In particular, they can either get a vertical win, with probability $(1/7)^3$ or win horizontally, where they achieve one of $4$ possible rows of $4$ on the bottom, each of which may be achieved by $4!$ sequences of moves, giving an additional $\frac{4\cdot 4!}{7^4}$ probability of them winning.

Then, you can see that your overall probability of winning is at least $(6/7)^3-(1/7)^3-\frac{4\cdot 4!}{7^4}\approx .58$, which still occurs a majority of the time.

Answer 2

Well, in theory this of course depends on the opponent-AI. By always placing tokens in the first/second/etc. row you will not have a guarantee for defeating the other AI which always places tokens in random places.

To be precise, assuming you are playing with 7 columns, the probability that the enemy will not place any token in the first column four times in a row would be around $60$% (in other words: ($\frac67)^3$). If you take into account that by time, the probability will increase constantly that the enemy places a token in the column your AI is currently stacking coins in, your win chance will overall decrease over time most likely.

That's why I would say that it is not an optimal solution to beating the enemy AI, although it should work considering that you have a slightly higher chance overall. However, if you want to program more advanced AI's, I cannot really tell you a general solution, since I do not know how advanced you want your AI to be/ how advanced of an AI you are able to code. A beautiful general solution to such problems would be Artificial Neural Networks