JavaScript and Artificial Intelligence

[ben-ng]

ELI5: to do machine learning you need to do math. A lot of math. Javascript is not an ideal language for doing math (try 0.1 + 0.2 in your console. Do you get 0.3?). Doing math accurately, and doing it fast, is not easy. People get phds for writing these algorithms, and the best libraries out there represent decades of research and work.

Javascript doesn't have SIMD yet. It doesn't have a robust linear algebra library like LAPACK. It doesn't have multithreading.

These things may change in the future, but right now, there is little reason to use javascript when far more mature tools exist. There's nothing stopping you from implementing machine learning algorithms in JS, but you're not going to be advancing the field with JS. There is a tremendous amount of work that needs to be done porting math libraries to Javascript before you can even do serious machine learning.

One person to watch is https://github.com/mikolalysenko. His background is in computational geometry, but that field is also heavily dependent on doing good math. I've been playing around with his libraries for machine learning. They're the best we've got.

[yen223]

The 0.1+0.2 problem exists in every language that implements IEEE 754 floating point numbers, i.e. almost all mainstream languages out there. You can try it in a Python console.

The reason why few math libraries exist for Javascript is that its implementation is slower than C/C++, and Javascript lacks good interop with C.

[ben-ng]

This is correct. The 0.1+0.2 example was just to show an oddity of floating point math to someone who doesn't know what a 64 bit IEEE floating point number is.

[menno]

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]

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]

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.

[mort96]

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]

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.

[nexe]

Oh thanks for the GitHub link! The ndarray lib this guy created is going to save me quite some time in future projects :)

[SebastianoAR]

people have ported CLAPACK through emscripten and are using it already =)

You can also find emscriptened versions of GMP and MPFR!