Slashdot Mirror
Distributed Chess Computing Project
jcarley writes "Just found an interesting project that is looking to capitalise on the power of unused computing cycles to develop a strong chess playing computer. Given the power in single and dual CPU chess programmes these days, if they can find a good way to efficiently parallel the anaysis this could be interesting. "
Background information
.3DS and .DXF files into Flash movies. This would allow me to render each 3D chess piece model at various angles while applying lighting and a camera view to create a Flash movie for each piece. One of the issues that surfaced was that a 64 frame movie (a piece rendered at each square) would yield a rather large movie file. Wanting to keep the size of the Flash based chess viewer small made this approach unusable. I decided that I would have to resort to an old game programming trick. The technique in question involved rendering an object at several fixed angles and then scaling the object in size to give the illusion of movement within a larger 3D space. This technique allowed me to render an 8 frame movie (one frame per eight positions). While not perfect this technique produces a pleasing effect.
I'm passionate about the chess. My love for the game goes back to my early childhood when my mother taught me to play. During my youth, I played chess obsessively, and my devotion to chess study had an adverse affect on my school grades. I can recall playing chess in place of lunch, and between classes. It became clear to me that I would have to attend to things other than chess.
In the early 1980's I developed an interest in computing. The first software program that I purchased was of course a chess program, Sargon for the Commodore Vic 20. As I learned the fine art of computer programming, my desire to build chess related software grew. My focus, however remained primarily on building a career, and a family... chess work would have to wait. Nearly five years ago I started working on components for what would become the ChessBrain project. The project changed in scope during the past three years, affected in large part by the work that was being done on the Seti@Home project and in the peer-to-peer distributed computing space.
The Seti@Home project was created to aid in the Search for Extraterrestrial Intelligence. Seti@Home allows users to download a small program which is able to communicates with the SETI computer to retrieve small blocks of data that will be processed on the users machine. The data in question consist of small segments of data collected via the radio telescope on the island of Puerto Rico. Once the data is processed the results are then submitted back to the Seti computer. In this way, millions of users donate the use of their computers processing power to aid the Seti effort.
Seti@Home inspired me to apply the distributed computing model toward the goal of creating a massive chess computer that uses the processing power of networked machines to calculate its moves.
Primary Servers
I use many computers on the ChessBrain project (eleven at one point). Most of the computers are used for testing, however, two computers are currently in fulltime service.
The first is a computer which I do not own, but rent time and space on, it's a computer at a web site hosting facility in Arizona. That is the current home of the chessbrain.net site.
The second computer is one of four PIII-1 ghz machines I own and has been dispatched to Corona, California. This machine hosts the distributedchess.net domain and a software application called the SuperNode server.
I have limited space available at home and thus rely heavily on the use of five laptop computers. These computers support my testing efforts. I run a variety of operating systems, several on the Win32 platform, several under various versions for Linux and one iBook running Mac OSX.
In the next two sections we'll look at the SuperNode server and some of the reasons for using multiple machines.
SuperNode Server
ChessBrain users will download a program which communicates with the main ChessBrain server to retrieve chess positions. Each users machine will process the chess position in question and return a result to the ChessBrain server. The ChessBrain server (called the SuperNode server hereafter) is the machine that is directly coordinating the game at hand. When it becomes its turn to move, the SuperNode server analysis the current position and dispatches potential moves to users (PeerNodes) for further analysis. This scenario is considerably more involved than described, however the explanation will need to suffice for the time being.
Two years ago I started working on pieces of the SuperNode server under Linux. My choice of Linux was largely due to a desire to learn Linux server programming. At the time my core competency was; programming on the Microsoft Windows platform. However, I really wanted to learn more about Linux.
The SuperNode multithreaded server is written in C++, and compiled using the GCC compiler under RedHat Linux 7.1. Currently the SuperNode server code is a bit more than 13,000 lines of code.
When the SuperNode server is running it accepts network connections (from Server Nodes) using Berkeley Sockets, and accesses a thread pool to dispatch the handling of the connection request to a background thread. This allows the SuperNode server to simultaneously service multiple client connections. In load testing, I've measured 200+ simultaneous connections.
You can access the SuperNode server statistics page to view the current server load.
Currently, the SuperNode server is running a set of game simulations. So it isn't actually playing a real chess game at this time. The simulations are in place so that the server can be tested as it communicates with other software client nodes. There are currently six types of clients available.
Server Nodes (Linux, Win32, Cygwin, MacOSX)
Game viewer (Java, Flash)
3D Game viewer (C++, Win32, DirectX3D)
PHP game viewer (PHP 4)
PHP SOAP proxy
Perl test suite (Perl 5)
PeerNodes are the computer clients which communicate with the SuperNode server, illustrated in the flash animation above. PeerNodes are written in portable C++ and compiled for Linux, Windows and MacOSX.
Users can view the current game in progress by using one of the Java, Flash, Win32 (Microsoft Windows), or PHP based game viewers. Viewers can be accessed on the downloads page and on the viewers page.
I use a small PHP proxy script to enable the use of HTTP Get request to return SOAP responses. We'll examine this further in a later section.
Most of the current SuperNode server testing is done via the use of automated testing scripts written in the Perl programming language. We'll look at Perl and Perl's SOAP::Lite later in this document.
The animation on the left shows how a client machine running any one of the client programs discussed above, goes about formulating an HTTP payload with an XML based SOAP request and transmits it to the SuperNode server.
The SuperNode server receives the HTTP request, extracts the SOAP request and processes the request.
The request is performed, and a new SOAP response is generated and packaged inside of an HTTP response and sent back to the client machine.
The ChessBrain project doesn't run on a single computer. This site, chessbrain.net is one of two computers involved. The next sections explores my reasons for choosing to utilize several computers.
Why two servers?
It is entirely possible to simply use one server to host ChessBrain. However, do to the cost of doing so, I decided to go another route.
Cost
I started by investigating dedicated hosting cost and realized that I would have to spend anywhere from one hundred to several hundred dollars per month in hosting charges. Given that ChessBrain is a non profit project, the expense was a bit difficult to justify. I chose to purchase a one year contract of basic web (non-dedicated) hosting service, for one hundred dollars. This basic hosting plan meant that ChessBrain would run on a machine along with several other web sites, hence the term non-dedicated.
Decentralization
Naturally, choosing low cost hosting had certain major drawbacks. The biggest single drawback was the inability to host my own server application. The ChessBrain project uses a custom server application called the SuperNode server, which communicates with other peer node servers. This wasn't going to happen on a 12 dollar per month service.
Once I accepted the fact that I would have to use non-dedicated hosting, I soon started to look on the bright side of the situation. Decentralization is a good thing, I thought. I decided to have the ChessBrain site communicate with my home computer as needed. If I shutdown the SuperNode server, users on the ChessBrain site would still be able to access the site. Only the ability to view the current game in progress and access SuperNode server statistics would be unavailable. Damage control is one of the key benefits of decentralization!
My home network was connected to the Internet via a cable modem, so bandwidth wasn't a problem. However, my cable service provider didn't take too kindly to my Internet usage and shut my connect down on several occasions.
Fortunately for me, a friend came to the rescue. My friend Walter Howard happen to have a T1 into his home (yes, I have interesting friends) and didn't mind hosting a machine for me. As far as this project is concerned, this was a life saver!
Firewalls
Many corporations, institutions and an increasing number of individuals are choosing to run intrusion prevention hardware / software (firewalls). Firewall software closes off connection ports that would otherwise be available to networking software. Only the most common ports are left open, and more often than not, the only port left open is port 80, the port through which web traffic normally travels through.
Because web servers take over port 80, running other software on the same machine that also requires port 80 isn't possible. This is why many people chose to write server extensions (scripting languages that are added to web servers to enable extensions).
Using more than one computer where each computer uses port 80 to communicate with each other...
(TBC)
Server Administration
The chessbrain.net and distributedchess.net sites are administered remotely using a tool called secure shell (SSH). SSH is similar to telnet, only it's encrypted and hosts a number of nice features. For security reasons, the SSH servers are setup to only accept connections from known IP addresses. This reduces the likelihood of the sites being hacked. The SSH tool suite includes a tool called SCP which simplified the secure copying of files and replaces the need for FTP.
Communication
The ChessBrain project consists of two publicly accessible sites. The first is this site, the chessbrain.net site (CB), and the second is the distributedchess.net (DC) site. Both sites are able to communicate with each other to support users.
The animation on the left shows that two users at opposite edges of the net are able to communicate with both the CB, DC servers.
In addition, the CB and DC servers communicate with one another to support users.
On the CB site users can learn about the project, download project related files, and view the current game in progress. The site runs under an Apache web server on a Linux machine at a site hosting company in Phoenix Arizona. The CB server doesn't actually play chess, however it does know how to communicate with a server that does, the DC server.
DistributedChess.net is the brain behind the CB site. This site is very different from the CB site in that it doesn't actually run a known web server, such as Apache. Instead the DC site runs a custom server called the SuperNode server, which is hosted on a Linux machine in Corona CA.
Currently when a user accesses the stats page, or a page that displays the current game position, the CB server contacts the DC server requesting the information, and then formats and displays the results to the user.
Over the past two decades, computer scientists and researchers have developed many ways of enabling computers to communicate with each other. Today we have many methods from which to choose from. For the ChessBrain project, I needed a way to allow Java, PHP, Perl, C++ based programs running under Linux, Windows and MacOSX to communicate using a common language (protocol).
Two standards were gaining widespread acceptance among software developers building next generation web applications, XMLRPC (extendible Markup Language for Remote Procedure Calls) and SOAP (Simple Object Access Protocol).
In December 2001, I chose to use XMLRPC, which utilizes a small XML grammar to formalize the passing of commands (methods, parameters, etc...) between communicating systems. XMLRPC was simple enough to implement across the platforms I was interested in. My intention was to ultimately migrate over to the use of SOAP once everything was working well under XMLRPC. It was clear to me at the time that SOAP would be the method of choice for web service developers, and that I couldn't possibly avoid migrating to it. The reason for this is simple. SOAP is quickly becoming the method of choice for building highly interoperable systems. Many companies are building tools that simplify the process for the software development community.
Once everything was working well, I realized that it would be better to use the SOAP standard, because it is quickly becoming the methods of choice in the industry.
Today the ChessBrain project uses SOAP as the communication language.
Communication Glue
On the CB site users can learn about the project, download project related files, and view the current game in progress. The site runs under the Apache web server on a Linux machine using the PHP scripting language for dynamic content generation. PHP also facilitates communication between the CB and DC servers. The CB server doesn't actually play chess, but it does however know how to communicate with a server that does, the DC server.
(TBC)
Game Viewers
Java viewer
Win32 3D viewer
PHP viewer
Flash viewer
Last February (2002) I had the opportunity to explore the use of Macromedia FlashMX (Flash 6). FlashMX has support for XML which allows a Flash programmer to handle SOAP. Intrigued with Flash presentation and networking capability, I decided to start building a Flash based chess viewer for use on this site.
I decided early on that a simple 2D looking viewer (similar to the Java viewer available on this site) wouldn't show off Flash's capabilities. So I decided to simulate 3D graphics using Flash. Now, keep in mind that Flash is a 2D vector technology without support for true 3D (multi-layer Z order is not 3D!).
My first obstacle concerned how to take my 3D Studio (.3DS) chess models and convert them into a format that could be used within the Flash environment. I searched the web and found a product called Swift3D that converts
The end result isn't true 3D, but rather simulated 3D using 2D graphic (movies). This is often referred to as 2 1/2 D or isometric.
The next challenge involved using the newly created Flash movies within the Flash environment to position the pieces within each chess board square. The approach I took involved turning each chess piece movie into a SmartMovie component, and to drive instances of the smart movie clips (chess pieces) using Macromedia Flash's built-in programming language, ActionScript.
(TBC)
Web Services
Web servers and browsers have changed the computing landscape by providing efficient access to applications. The ease of deployment and accessibility of services have enabled web applications to continue to emerge as products and services that many of us use via the Internet.
The benefits offered by the network application development paradigm has ushered in a new era in software development. In this next generation of the web, applications are communicating with other web applications to aggregate liked services. Unlike the prior web generation, this new generation is about giving machines the ability to locate, dynamically bind, and communicate with other services on the fly.
This isn't the future it's already underway!
There a considerable amount of conversation generated about a new paradigm in computing called Web Services. While the approach to web services is new, the needs it addresses have existed since the time when at least one computer had to speak to another. Web services promises to simplify how computers communicate with each other to share resources, and this alone is generating much of the interest.
By leveraging open standards, web services will become the fundamental building blocks of distributed computing across networked devices from large-scale sites down to embedded devices.
The emergence of peer-to-peer networked devices is quickly becoming a reality, and there is a strong parallel between what is happening on a macro scale (large scale web applications) and on a micro scale (embedded systems). The new web services model treats networked devices as both consumers and producers of services.
During the past few years we've started to see embedded systems supporting the use of web servers in their products. Internet application devices, such as cable modem routers, and network attached storage devices (NAS).
The Web service paradigm has the potential to enable a level of global collaboration unlike any in seen in the history of our planet. This alone has many of the largest computing companies scrambling to embrace web services.
Agent / Bots
The ChessBrain SuperNode server uses a software component to communicate to the Free Internet Chess Server and its online users. The module called Shannon is a simplistic agent or bot that performs the same commands that a human user might perform while on FICS.
Shannon is an agent for the SuperNode server in the same way that human counter parts (particularly in the entertainment field) use agents to act on their behalf. Technically, Shannon is a C++ module that runs as a thread inside of the SuperNode server.
Software Testing
Testing software is remarkably difficult to do. Each year products are released with problems to unsuspecting customers. Often companies find themselves comparing market pressures against their desires to produce quality software products. More often than not, market pressures win, and software is released with known issues. In my twenty years of experience, I've consistently watched companies underestimate the cost of software development. Take a team of five software developers, add at least one manager, and throw in at least two software testers over six months and you've got a half a million dollar project. I've worked on similar sized teams with budgets ranging from half a million to two million dollars, working on project that no one really knew would sell. Hard to imagine? You know what they say... Reality can be stranger than fiction!
During the early 90s I was hired at the Symantec Peter Norton Group. At that time, Symantec encountered difficulty testing their complex and feature rich software applications. The number of people hired to test software was staggering. This was one of the reasons that motivation Symantec to consider automated software testing software tools. Automated testing tools do not eliminate the human software tester. Rather, the tools enhance the ability of human testers to root out hard to find problems. The end resulted in time savings and thus lower cost.
My experiences with Symantec and the many other companies I've worked with since that time have instilled in me a now ingrained sense of the importance of software testing. When I started working on the SuperNode server testing. My early experience with the use of scripting languages in automated testing products served as a powerful reminder. I chose the Perl programming language. In all fairness, PHP was another viable alternative. Perl offers several outstanding features that make it ideal for software testing. Perl is ideal for a large number of other uses. For many people, Perl is the only language they need (many sysadmins will agree).
The Perl programming language proved ideal.
Perl scripts run on multiple platforms.
Perl has excellent support for networking.
Perl could be extended for web services using SOAP::Lite.
Perl's support for regular expressions simplified network message parsing.
New scripts can be quickly authored.
I use Perl in the following ways:
Load testing. I run Perl scripts on several machines (concurrently) that repeatedly connect with the SuperNode server. The scripts issue the exact commands that viewers and node servers issue. This allows me to test new commands prior to making the functionality publicly available.
Handling Complexity
By far, the largest area of difficulty stems from the nature of testing software that is actively engaged in performing functionality simultaneously. At any one point, the SuperNode server may be accepting a connection, servicing a connection, interacting with other servers etc... The SuperNode server is a multi-threaded server. I use a dual processor computer so actions may indeed occur simultaneously. In order to stress test this sort of situation, I run multiple simulated clients (using Perl scripts) as fast as they can execute across multiple computers within a 100BaseT private network.
Quick Summary
If you've jumped to this section prior to reading the entire document, then congratulations, you're on the fast track! If you got here the old fashion way, then congratulations again, because this section will reinforce what you've already discovered.
The ChessBrain project uses many forms of computer tools and technologies. Each piece of technology serves an important role.
Key concepts
Distributed Computing allows machines to communicate which each other to solve large and complex problems.
XML and SOAP are key technologies that enable computers to provide and exchange services.
No single computing technology can serve all purposes. Effective computing architectures rely on numerous other components to address a wide range of needs.
Other key points
SOAP forms the glue for all network communication in the ChessBrain project. All (SuperNode and Peer Node) servers, and all game viewers used on the project communicate via SOAP.
Scripting languages are valuable tools in automated testing.
Computer Languages
ActionScript. Used to drive the Flash based game viewer.
C/C++: SuperNode server, Peer node servers.
Java: Java based game viewer, and bar graphs on the stats page.
PHP: Server side scripting for dynamic web pages used throughout the site, and the xmlproxy script used to translate URL based request into SOAP request.
Perl: Official software testing language for the ChessBrain site. All server functionality is tested using Perl scripts.
Resources / Links
Additional resources are listed on this site's resource page.
Operating System Platforms
Computer Languages
Media creation