Chess @ home: create the largest chess AI
Many are familiar with the project Seti @ home : the most powerful initiative to find traces of extraterrestrial civilizations in the ocean of data obtained from the sky, using the capacities of millions of computers around the globe ("matrix").
Although no aliens have yet been discovered, Seti @ home quite successfully demonstrates the potential of large-scale distributed computing. Projects like BOINC have extended similar initiatives to other areas: biology, medicine, and physics.
Last weekend, a team from Joshfire ( Thomas , Nathan , Michael, and I ) participated in the 48-hour Node Knockout competition. The rules were simple: encode the most entertaining thing over the weekend, which uses server-side JavaScript.
JavaScript is an old, but fascinating technology that is now being reborn due to increased performance , server engines and a heap of new features offered by HTML5 . In addition, it is the most common language. Any computer connected to the web can easily execute JavaScript code, just type in the browser address or run the script from the command line.
')
We decided to use its prevalence and high performance of Node in order to build a large-scale distributed computing project that people could join simply by going to a web page . The search for aliens was quickly crossed out, because we didn't have a radar system at hand. Because we began to solve the problem easier: Chess .
None of us is a good chess player, but in the Guinness Book of Records we found a mention of the largest chess AI , consisting of 2,070 knots, and decided that we could beat him. This is how the project Chess @ home was born.
After 48 hours, there were a few more bugs in the prototype, but it was in a completely playable state and looked like this:
Starting the study, we identified the following problem areas:
Delay We had a desire to follow the standard tournament rules (~ 90 minutes per game), which led to the requirement to calculate the course on average per minute. Moreover, players on the web would definitely prefer a shorter response, and we set ourselves the goal of making it as short as possible.
The small time window for calculations does not allow playing well on most existing distributed computing infrastructures, which are mostly optimized for high power . We needed to build a new, almost real-time infrastructure. Websocket s were asking for as part of the solution.
Parallelism Optimizing response time means that you need to send small amounts of processing to each calculator. So we had to figure out how to break the code calculation into thousands of small pieces.
Without going into details, the minimax algorithm used in most chess AI is based on tree traversal , and is essentially consistent with the use of alpha-beta clipping . We considered various algorithms that would be suitable for parallelization, keeping in mind the following:
We found two potential candidates: APHID (simple, used in ChessBrain.net , is the current champion of Guinness records) and variations of YBWC (more difficult, but more effective). Having a 48-hour limit on coding, we decided to start with APHID.
JavaScript performance . The coolest chess AI can pass up to 15 million tree nodes per second (NPS = nodes per second) using the most advanced hardware. We took GarboChess , an open source chess AI with JavaScript, whose performance is 100k NPS under Chrome on a modern Macbook Pro. The coefficient of 150 didn’t upset us much, especially since in 48 hours we wouldn’t have time to profile and optimize the code that could win any of us using only one computer.
For reference, they say that Deep Blue worked at a speed of 200m NPS to defeat Kasparov, which in general was theoretically achievable at our 2070-node goal.
Fault tolerance / security . Running JavaScript on third-party computers means that its results cannot be trusted for two reasons: accessibility (users can leave the page at any time) and accuracy (attackers may slip wrong results, and the AI ​​will make a foolish move).
We decided not to deal with the reliability in the first variant, but the availability remained critical so that our algorithm was completed on time, without missing obvious moves in the decision tree. We set up a FIFO queue for computing tasks in MangoDB and set a timeout of 5 seconds so that another computer can pick up the task and process it, if no response has come from the first one.
Here is the outline of our prototype:
Let us examine the main components:
In this implementation there is something to improve, but do not forget - everything was done in 48 hours. But launching AI on Web Workers, both browser and server, will remain the main idea.
Ethics for widgets . Usually, in order to use someone else's computing power, the consent of their owner is necessary: ​​people install the SETI @ home or BOINC software, thus allowing them to their processor. JavaScript allows you to use other people's processors without explicit permission, you just go to the page with the widget, which is not very good.
We decided to get the consent of users, but installing the widget on foreign sites with high traffic remains the main unresolved task for our 2070-node goal, and we will do our best to respond to objections or discontent that may arise.
For example, since we plan to use “public” resources, we must keep the results as open as possible . The code will remain open on GitHub. We also plan to open API for chess AI.
Improvements to AI . After we understand the few remaining interface bugs , we will continue to optimize AI in the following areas:
Plan for hour X. When the AI ​​becomes strong enough, we will call the real French grandmaster and the representative of Guinness to hold the most exciting chess game!
We need to coordinate a lot of people so that they connect to the matrix at the same time. Installing the widget on several highly-visited sites should help. We also want people to have the opportunity to observe the game on Chess @ home, and also participate in the calculations.
If you have an idea how to connect the maximum number of people, please tell us! We are also looking for talented JavaScript developers to handle everything described above.
If you want to help us, look at the current task list or try finding new ones on Chess @ home . Good luck with the Matrix!
PS We won the Node Knockout in the Completion category .
For those who do not know how to use Habrom:
Although no aliens have yet been discovered, Seti @ home quite successfully demonstrates the potential of large-scale distributed computing. Projects like BOINC have extended similar initiatives to other areas: biology, medicine, and physics.
Last weekend, a team from Joshfire ( Thomas , Nathan , Michael, and I ) participated in the 48-hour Node Knockout competition. The rules were simple: encode the most entertaining thing over the weekend, which uses server-side JavaScript.
JavaScript is an old, but fascinating technology that is now being reborn due to increased performance , server engines and a heap of new features offered by HTML5 . In addition, it is the most common language. Any computer connected to the web can easily execute JavaScript code, just type in the browser address or run the script from the command line.
')
We decided to use its prevalence and high performance of Node in order to build a large-scale distributed computing project that people could join simply by going to a web page . The search for aliens was quickly crossed out, because we didn't have a radar system at hand. Because we began to solve the problem easier: Chess .
None of us is a good chess player, but in the Guinness Book of Records we found a mention of the largest chess AI , consisting of 2,070 knots, and decided that we could beat him. This is how the project Chess @ home was born.
After 48 hours, there were a few more bugs in the prototype, but it was in a completely playable state and looked like this:
Problems of distributed chess AI
Starting the study, we identified the following problem areas:
Delay We had a desire to follow the standard tournament rules (~ 90 minutes per game), which led to the requirement to calculate the course on average per minute. Moreover, players on the web would definitely prefer a shorter response, and we set ourselves the goal of making it as short as possible.
The small time window for calculations does not allow playing well on most existing distributed computing infrastructures, which are mostly optimized for high power . We needed to build a new, almost real-time infrastructure. Websocket s were asking for as part of the solution.
Parallelism Optimizing response time means that you need to send small amounts of processing to each calculator. So we had to figure out how to break the code calculation into thousands of small pieces.
Without going into details, the minimax algorithm used in most chess AI is based on tree traversal , and is essentially consistent with the use of alpha-beta clipping . We considered various algorithms that would be suitable for parallelization, keeping in mind the following:
- calculators should not be particularly dependent on common variables web sockets do not work according to the client-client scheme (and the data run through the server prevents scaling);
- The calculation of each move should be broken down into thousands of small tasks.
We found two potential candidates: APHID (simple, used in ChessBrain.net , is the current champion of Guinness records) and variations of YBWC (more difficult, but more effective). Having a 48-hour limit on coding, we decided to start with APHID.
JavaScript performance . The coolest chess AI can pass up to 15 million tree nodes per second (NPS = nodes per second) using the most advanced hardware. We took GarboChess , an open source chess AI with JavaScript, whose performance is 100k NPS under Chrome on a modern Macbook Pro. The coefficient of 150 didn’t upset us much, especially since in 48 hours we wouldn’t have time to profile and optimize the code that could win any of us using only one computer.
For reference, they say that Deep Blue worked at a speed of 200m NPS to defeat Kasparov, which in general was theoretically achievable at our 2070-node goal.
Fault tolerance / security . Running JavaScript on third-party computers means that its results cannot be trusted for two reasons: accessibility (users can leave the page at any time) and accuracy (attackers may slip wrong results, and the AI ​​will make a foolish move).
We decided not to deal with the reliability in the first variant, but the availability remained critical so that our algorithm was completed on time, without missing obvious moves in the decision tree. We set up a FIFO queue for computing tasks in MangoDB and set a timeout of 5 seconds so that another computer can pick up the task and process it, if no response has come from the first one.
The implementation of the prototype in 48 hours
Here is the outline of our prototype:
Let us examine the main components:
- dnode The Node.js library for two-way asynchronous remote method calls. Provides transport in the style of sockets and web sockets (using socket.io ) so that system processes can communicate with each other and with processes running in browsers using the same interface. We used it for almost all network interactions.
- Web Workers (web calculators). Single-thread (JavaScript) environment, limiting the execution of a single script so that the user interface does not hang. Web Workers allow us to run scripts with a long execution time to solve computationally demanding tasks, but without blocking the interface or other user interaction scripts. From the server side, we used node-webworker (a Web Worker implementation for Node), so we had a single interface for communicating with AI.
- MongoDB . MongoHQ sponsored Node Knockout, and we decided to use pre-made MongoDB instances to store game states and a potentially large cache of positions.
- Node . The central link of the architecture, Node has both fast development (the same code on the server and the client), and high performance (its non-blocking I / O paradigm has confirmed its competitive ability and speed).
- Local AI on the server. This place obviously does not scale, but nevertheless we have to make several AI calls on the server, mainly because the APHID needs to first build a small tree in order to distribute the work to the clients. Perhaps in the future we will remove it.
In this implementation there is something to improve, but do not forget - everything was done in 48 hours. But launching AI on Web Workers, both browser and server, will remain the main idea.
Whats ahead
Ethics for widgets . Usually, in order to use someone else's computing power, the consent of their owner is necessary: ​​people install the SETI @ home or BOINC software, thus allowing them to their processor. JavaScript allows you to use other people's processors without explicit permission, you just go to the page with the widget, which is not very good.
We decided to get the consent of users, but installing the widget on foreign sites with high traffic remains the main unresolved task for our 2070-node goal, and we will do our best to respond to objections or discontent that may arise.
For example, since we plan to use “public” resources, we must keep the results as open as possible . The code will remain open on GitHub. We also plan to open API for chess AI.
Improvements to AI . After we understand the few remaining interface bugs , we will continue to optimize AI in the following areas:
- Improved concurrency : we plan to switch from APHID to YBWC in order to more flexibly distribute tasks between calculators. This is especially important because of the poor performance of JavaScript, you need to compensate for its large scale.
- Unit tests : We have already carried out unit testing for a couple of hundreds of positions, but many more are available online, and we are going to integrate them in the manner of STS .
- Improvements to the algorithm: GarboChess has already implemented alpha-beta clipping, zero window detection , finding quiet positions and several other functions, but improving the evaluation function and some modifications of the AI ​​will allow it to play better.
Plan for hour X. When the AI ​​becomes strong enough, we will call the real French grandmaster and the representative of Guinness to hold the most exciting chess game!
We need to coordinate a lot of people so that they connect to the matrix at the same time. Installing the widget on several highly-visited sites should help. We also want people to have the opportunity to observe the game on Chess @ home, and also participate in the calculations.
If you have an idea how to connect the maximum number of people, please tell us! We are also looking for talented JavaScript developers to handle everything described above.
If you want to help us, look at the current task list or try finding new ones on Chess @ home . Good luck with the Matrix!
PS We won the Node Knockout in the Completion category .
For those who do not know how to use Habrom:
- translated: unconnected
- Lyrics by: Sylvain Zimmer
- original: Chess @ home: Building the largest Chess AI ever
Source: https://habr.com/ru/post/128598/
All Articles