Angel \”Java\” Lopez on Blog

January 9, 2015

JavaScript And Artificial Intelligence (3)

Filed under: Artificial Intelligence, JavaScript — ajlopez @ 9:43 am

Previous Post

One topic that I presented with an example (but without running it) is the evaluation of the next move in a board game. I mentioned a movie I watched decades ago and influenced me a lot in the way of seeing artificial intelligence, War Games (“War Games” 1983, see Wikipedia see IMDB):

In board games, it is common to evaluate a position, given the possible moves, evaluate the resulting positions, choosing the best one for our side. The problem is to determine the "best". In general, there is no perfect evaluation functions. What you can do is explore a tree of moves, to have a "deeper" assessment of the current position. This allows calculating a current position value based on the possible evolution of the next moves. There are several ways to explore a tree (I refer you to book mentioned in the previous post, based on all the talk)

I chose as an example, a board game with random, where the moves involve the roll of dices, the popular backgammon. I remember the work of Hans Berliner, in the eighties, that I met thanks to an article in Scientific American:

 

It was the first program to beat a human world champion in a board game. You can read the articles of Hans Berliner in:

Backgammon Computer Program Beats World Champion
Computer Backgammon

If you read the description of the program, it has a lot of heuristics, and expert knowledge of the game. My project is more modest and tries to evaluate a position exploring the tree of moves, calculating at the end a simple "metric" of how far we are the ultimate goal (remove all the tiles from the board before your opponent ).

The project in JavaScript at:

https://github.com/ajlopez/SimpleGammon

It was written using TDD (Test-Driven Development), as usual, using Node.js console. But the example can run in the browser:

https://github.com/ajlopez/SimpleGammon/tree/master/samples/html

Simple interface to be improved:

Runs evaluating two moves forward to the client. Before click "Play" you can choose who moves, and what are the initial dices values. But now, the algorithm takes seconds to run, something to improves. Several options to explore, such as parallel processing (we saw at the conference that JavaScript has implementations to run in multiprocessors), and derive the evaluation to the server, where it can be forwarded to many worker machines (something I did for another example , genetic algorithms).

Other projects that I am working to evaluate positions (but still without examples, work in progress):

https://github.com/ajlopez/SimpleGo
https://github.com/ajlopez/SimpleChess

The game of Go is compelling, but not trivial. First, I want to go further with the implementation of backgammon, the first candidate to distributed evaluation.

Stay tuned!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

Blog at WordPress.com.

%d bloggers like this: