Best algorithm for reinforcement learning for a four in a row game

Question

What is the best algorithm for reinforcement learning for a four in a row game. I want to build a four in a row game that will use one of the RL algorithms to play: Q-Learning, MinMax etc.

What is the best one to use considering I am using Java.

Answer 1

MinMax is pretty good for that game. The real question is how good will be your eurhistic function to determine what's the "value" of a certain move.

Answer 2

MinMax isn't usually considered to be a reinforcement learning algorithm, but it probably is the 'best' (depending on what you mean by that) for Connect 4.

Connect 4 has been solved (on many different sizes of board) for nearly three decades now. The solver has even been used as a processor benchmark known as Fhourstones and the source in Java (and C) is freely available.

If your aim is to learn about Q-learning (in tabular form), REINFORCE, or some of the more modern reinforcement learning algorithms such as Deep Q-learning using neural networks (DQN) or Action Advantage Actor Critic (A3C) then I've no doubt that these can all be applied successfully to Connect 4. I'd recommend a good book such as Barto & Sutton's Reinforcement Learning. At the time of writing, a draft of the 2nd edition is freely available in PDF form.

However, if your aim is simply to have a best player, then you'll struggle to beat the perfect play of Fhourstones.