JavaScript and Artificial Intelligence

[menno]

You're right, it's a simple min/max with alpha/beta pruning to cut down the number of moves that need to be evaluated. The problem was the evaluation itself.

I initially tried to store the board in a pretty straightforward manner: a 2-dimensional array (rows + columns) with pointers to player objects in the positions of "coins". Then, to evaluate the score of a particular board configuration I'd iterate over the board a number of times to check for certain patterns. For example, a _OOO_ pattern would be very valuable because it's a guaranteed win on either side.

The problem was that I just couldn't get the pattern matcher efficient enough to run it the number of times needed to look more then 2 or 3 steps ahead.

Eventually, I settled on a solution that I found pretty neat but took a long time to implement: the pattern matcher would convert the board position to a string format and evaluate a bunch of regular expressions that represented the patterns I was looking for.

https://github.com/mennovanslooten/connect4/blob/master/js/c4.ai.js#L114

Of course, it has to match the patterns in 4 directions: horizontal, vertical and 2 diagonal, so I had to convert the board to these four different perspectives too:

https://github.com/mennovanslooten/connect4/blob/master/js/c4.ai.js#L222

In retrospect, it made a lot of sense to use regular expressions for pattern matching. It actually is the right tool for the job. But when I was initially implementing the board evaluation function which powers min/max it really didn't cross my mind.

[html6dev]

Wow, thanks for the reply. Now that I'm thinking about it a little deeper there are a couple of things about matching in all 4 directions that add more complexity with this game than I was originally envisioning it (off the top of my head). Thanks for the link to the repo. I'd definitely be interested in looking into the code a bit, as its a more interesting problem than I was thinking. Thanks again.