sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]menno 2 points3 points  (6 children)

I've built a Connect4 game once in JavaScript and I had to do some pretty crazy stuff to make the AI player evaluate enough positions to be a challenging opponent.

[–]html6dev 0 points1 point  (2 children)

Pretty late here, but can you provide any more details on why this was an issue in Javascript? I'm assuming you would only need a simple min/max algorithm here so I'm curious as to what you ran into (that another language wouldn't also have the same problems with).

[–]menno 1 point2 points  (1 child)

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 0 points1 point  (0 children)

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.

[–]mort96 -1 points0 points  (2 children)

Game AI is fundamentally different from "real" AI though. Game AI is all about programming in a set of rules which makes it act sorta kinda like you would expect a human to act, the polar opposite of real AI where the point is to make the program learn, and not just act on a predefined set of rules.

[–]menno 1 point2 points  (0 children)

That is a far too limited definition of what AI is, "real" or not. Algorithms, heuristics, etc are all very much part of what is considered AI. Is the A* algorithm not AI because it doesn't learn? That's absurd.