Warning: file_put_contents(): Only 0 of 8322 bytes written, possibly out of free disk space in system/classes/filecache.php line 154
Warning: file_put_contents(): Only 0 of 303 bytes written, possibly out of free disk space in system/classes/filecache.php line 157
RedAlt

Welcome back to my multi-part discussion on Reversi AI, and particularly the related performance ideas. This time around, I'm going to wax philosophical and set up the foundation for future posts.

Philosophical discussion of performance

One of the key, if not THE key, tenants to performance improvement is measurement. Optimizing without taking measurements is like shooting in the dark. Finding out where the program is spending its time is key to good optimization. The biggest bang for the buck will be gotten by tweaking the code where the most time is spent. Programs often follow the 80/20 rule, and this "20" is often the "inner loop" of the program. It's often easy to tell where this is, but it's just as easy to be wrong and waste time tweaking the wrong code. This is where profilers come in. I'm not going to go into their usage or provide recommendations, but a good profiler is an excellent tool to have available.

Tweaking the performance of an inner loop can be critical to the performance of a program. Let's say you want to calculate moves to a depth where you need to evaluate 1 million different boards (maybe 7 moves ahead). If you can remove 1000 clock cycles from that evaluation function, that's 1 billion cycles saved, or ~1 second on a 1Ghz processor.

There is an interesting trade-off between fidelity of the information gleaned and the depth of the search. Let's say that there's a calculation that will provide a pretty good estimation of how often a certain board will result in a player winning. Calculations take time and will need to be done for any board that is evaluated. When considering performance, this time must be gauged against the increase in fidelity provided by that value. Let's say that, during the time lost to calculate that value, the program could search 1 move deeper. At this point, you have to look at the gains of the new metric versus knowing what the game will look like after 1 more ply. Almost always, 1 ply deeper is better.

In fact, you can turn this concept right around... instead of trying to develop a new algorithm that provides higher fidelity, look at what you have and see if you can sacrifice some fidelity but gain extra depth. As an example of this, it is very common for strong Reversi AI to evaluate boards based on matching against patterns rather than looking at something like stable pieces. The patterns (assuming they're reasonably chosen) provide some of the same value as things like the number of stable pieces or edge evaluations (but not all), but can be done MUCH faster. This extra time easily adds up to another move when you do it enough.

Performance Optimizations

A lot may be gained from tweaking the code and code can be tweaked in a variety of different ways. I like to categorize these as "large-scale optimizations" and "small-scale optimizations" (this is my own thinking and not any sort of standard terminology). Bigger gains can be found from employing large-scale optimizations, but they also result in significantly more code churn. The possible benefit must be weighed against the amount of time spent to make the change. Calling it "small-scale" doesn't necessarily mean that the gains to be had aren't significant, but that the amount of change to your program is smaller. Sometimes huge benefits can be had by making small changes. This is where a profiler would help.

Large scale optimizations require significant changes to be made to the behavior of the code. Typically these are done by changing the algorithm used: changing the runtime complexity to something more efficient. Doing this is often easier than small-scale optimizations, because often it's pretty straightforward to substitute one algorithm for another. It's common for areas of a program to have linear runtime performance that can be easily be made sub-linear with a simple data structure change such as moving from a list to a tree or even an array. Since the gains are greater, I recommend large-scale optimizations before small scale ones (unless you only need very minor performance improvements). Also, tweaking code with small-scale optimizations will be wasted if you change to a new algorithm.

There are numerous places I employed these large-scale optimizations, particularly around the game board and the "think-ahead" methodology of the AI. I don't have the performance impact numbers anymore, but it is MANY, MANY times faster than it used to be when I was first putting things together. I'll talk about these in more detail later.

Small scale optimizations are generally taking the existing code and making tweaks that reduce the number of CPU cycles required. The runtime efficiency is basically the same, but the code runs faster. There are pretty standard ways to start doing this, like making better use of pointers, but also more advanced methods, like reorganizing code/data to cause better cache utilization, improve pipelining, or to result in less memory paging. Small scale optimizations are where performance measuring is really important.

Performance Observations

Running a profiler on my Reversi game was quite revealing. As it turns out, there are two key places where the program was spending its time:

  1. Calculating possible moves / which positions are flipped when a move is made
  2. Estimating the value of the board

Before it's possible to determine the best move, you need to be able to determine which moves are even valid. That means that this calculation must be done once per ply. Determining all the valid moves on a board is not trivial, as you may have noticed from the earlier description. Likewise, estimating the value of the board is something that happens very often... every board at the final search depth must have this calculation done. These calculations took a significant amount of time, and they were called often (over 90% of the time was spent there), so they were very good candidates for optimization.

Now that I've set up the discussion, next time I'll start giving specifics about what I'm calling large-scale optimizations.

Quite a while ago, I started work on a Reversi game, mostly to see if I could challenge my friend who is a pretty strong Reversi player. I don't have much experience with this sort of task, as it's not the sort of thing on which I generally work, but it was a nice change of pace. While it was new to me, this IS a pretty well-trod area... I never expected any revelations or unique developments. Certainly, if you expect to find something unavailable elsewhere here, you are mistaken, but if you want a quick look into some interesting challenges, mostly performance-related challenges, hopefully this entry (and related entries) will be interesting. I'll be breaking it into a number of posts:

  1. Basic introduction to Reversi AI
  2. High-level performance considerations
  3. Large-scale optimizations
  4. Search tree algorithms
  5. Small-scale optimizations
  6. Wrap up and Resources

I suppose first I'll give an introduction to Reversi. You can find plenty of descriptions online, but for the lazy among us, here's a breakdown: Reversi is a 2 player game played on an 8 by 8 grid of equal-sized squares. Each player has their own unique color (traditionally black and white). The pieces are flat and cylindrical, with top and bottom sides solidly colored one for each player. Pieces are placed centered in the squares on the board and the top color of the piece indicates which player owns that square (initially this must match the player that played the piece). The starting configuration for the board has the 4 middle squares filled by pieces, alternating white-black on the upper middle row, then black-white on the lower middle row. Traditionally, play starts with the black player. Players take turns placing a piece into a valid position until neither player has a valid move. If a player doesn't have a valid move, they pass, but otherwise they must place a piece (players cannot opt to pass). A move is valid if it results in at least one of the opponent's pieces flipping. This happens when, horizontally, vertically, or diagonally, a line can be drawn from the move's position through 1 or more of the opponent's pieces and then to another of the current player's pieces without going through an empty square or piece owned by the current player. This sort of sandwiching of the opponent's pieces with the current player's pieces is called "flanking". When a piece is played, all of the flanked opponent's pieces (in every direction) are flipped to be owned by the player who just placed the piece. The winner is the player who has the most pieces at the end of the game.

One area that was particularly new to me was the development of artificial intelligence for the computer players. Like many pieces of technology, it seemed as if it would be wondrous: Neural nets and/or complex logical rules. Indeed, if you look at traditional human strategic elements, you will see mention of things like parity, stable pieces, and balanced edges. Somehow, these ideas must be combined together to produce an incredibly intelligent player.

Sadly, like many magic tricks, the wonder dissolved once the secret was revealed: Try to think as far ahead as possible. By simulating every possible move from both sides, the AI is able to look ahead a number of moves. Each move it looks ahead is called a "ply". The further ahead the computer can calculate (i.e. the more ply), the better a move it is likely to make. If the computer is able to calculate to the end of the game, then it will know if it will win or lose and the sequence of moves to get there.

What's important to understand at this point is that Reversi is a relatively deep game, in that there are many turns per game (usually 30 per side). Also, to know who won the game, you need to get to the end of the game and then it's down to a simple question: Who has more pieces on the board? In the ideal case, the computer could solve the game all the way to the end, trying every possible move, and then it could know which move would be the best move. Unfortunately, that's not really feasible with the current technology; the number of possible games is extremely large as there are usually many potential moves per board position... on average about 7.488, according to my estimation. This grows exponentially with each move... it doesn't take too many ply before it takes more than a day to compute all the possible board outcomes. From this, we can conclude a few things:

  1. We need a way to deal with the fact that we're not going to be able to solve to the end of the game
  2. Performance will be pretty important

Dealing with uncertainty

Given the computational needs of completely solving Reversi, it is pretty obvious that the AI has to deal with the fact that completely solving Reversi is not going to happen. Generally the method used is to play the game as deeply as we have time for, and then come up with an accurate estimate of how good the resulting board is. In an ideal world, this estimate would indicate how likely that board is to lead to a win for the current player. This depth will eventually reach the end states of the game and, when that happens, the estimation can be replaced by certainty.

This estimation may take in any number of different calculations and combine them in an unlimited number of ways. Generally, it seems that the most common way is to use linear combination to combine the different metrics together into the final estimate. This solution is quick, easy, and provides good results. Linear combination involves combining a number of features, like "available moves" or "pieces on board", applying a weight to them, and then adding them together. There is no limit on the number of terms that can be combined in this way or what the weights may be. A simple (arbitrary and poor) example of this sort of algorithm: board_strength = 0.3 * stable_pieces - 0.1 * number_of_valid_moves. In this example, the algorithm is trying to maximize the number of stable pieces and reduce the number of valid moves. Because of the weighting, an increase of 1 stable piece offsets the increase of 3 valid moves.

Possibilities range from choosing a single metric, to using machine learning to discover a superior weighting system. If you're interested in the latter, I found this lecture on Autonomous Derivation interesting, if a bit much to dive into without preparation. You could probably also just search for the ideas covered there, like linear regression and gradient descent, and find something useful.

I'm not really going to discuss the specifics of what metrics should be used or how they should be weighted, but I WILL say that this evaluation function must be fast, since it is one of the most common calculations the AI will make.

Next post, I'll talk about some of the philosophical concepts of performance and look at difference kinds of optimizations.

Well, today's feedreader binge brings the advice to "Zip It" -- that projects that success most are the ones that keep themselves secret. Apparently, the idea is that by purging the idea from your mind, it gives you enough satisfaction by sharing it, and this satisfaction fills the spot of actually accomplishing the task itself to the point that you don't actually do the thing you talk about.

Ok, then. Just to keep people in the loop, I'm following one of my personal principles: Move Forward Every Day. If I keep doing a little, I'll inevitably get somewhere.

In the vein of moving forward, here's Alice.

Alice Burns is basically... me. She's a seasoned developer for Skywater-Stone. She's used many different project and/or bug tracking systems. She knows her way around web applications because she builds them. She's willing to put up with a little inconvenience in the perfection of an application if it is generally useful, but on the whole, she'll complain a lot if something doesn't work the way it's supposed to.

Alice's primary task consists of writing code for various client projects. At any one point, Alice will be working on (on average) between one and four client projects. While working on these projects, she has a frequent need to return to functional specifications - documents that describe what she's supposed to be producing.

She also needs access to project files provided by either the client or designer. Sometimes these files aren't complete and need to be sent back for review. She usually has a direct line to both the client and designer, but sometimes works through an intermediary, either someone within her company, someone hired by the client (often the design firm who subcontracted the development work), or within the client's company itself (sometimes a print designer re-purposed to web design, or a "project manager" that doesn't themselves know development).

Day to day, Alice keeps track of client requests, converting them into actionable items and acting upon those she has time for. She may keep a spreadsheet of items to work on, which may also include assignment dates and estimates. She may keep a combined to-do list for all clients as next-actions. Whether each of these to-do items corresponds to a larger list depends on the project size and how well it is (and needs to be) documented. Speed of using any of these tools is key to her, since messing around with some interface other than her IDE is a waste of the time she has so little of to begin with.

Although there is often someone between the client and Alice, ultimately her goal is to satisfy the client's needs. Sometimes requests are forwarded directly from the client that are out of scope for the current project. Sometimes these requests come from intermediary project managers that don't understand the development process enough to know how their request is affected by scope. Alice must often make the determination of what is in scope and out, and be able to make the case to the client.

As is the nature of the business, Alice reports time spent on projects for billing purposes. It is useful for her to use the amount of time estimated to spend on current projects to predict how busy she is going to be, and when she will be able to schedule new large tasks and client work. Knowing what's coming on the horizon would be an asset for planning what might happen in a more distant schedule.

Although a lot of her work might happen on her own, Alice sometimes has the responsibility for leading a project team. In those cases, coordinating who should work on what part of the project is important. Keeping in touch with the whole team is usually done via email. Sometimes inefficiencies in email make it unclear who is supposed to be doing what, so she has to be extra clear.

Once again... Subject to review.

The weird thing about coding a project management application is that you have to rely on a support structure that you wish had been written already.

One of the things I neglected to include in my initiation/requirements form a few days ago was a source browser or code review system. I think that's probably a part of the system, but I didn't want to commit to it right away. I have some interesting thoughts about integration, anyway. But even though it's an eventual feature of the system, developing the system requires it exists right away.

Clearly, for PHP developers, there needs to be an alternative to Trac for source code browsing. For one thing, if you're coding in PHP, it simply makes sense to have your project management and code review application also be written in PHP. This would hopefully lead to more opportunity for customization. It also makes it much more familiar to deploy than something like Redmine (Ruby) or Trac (Python) since you simply unzip the archive and go. I'm not sure where Ruby and Python developers ever got the idea that installing their stuff was easy -- there is a reason the "P" in "LAMP" usually stands for "PHP" after all.

Nonetheless, until the end product exists, some decision needs to be made about the tools that will be used to manage the project of building that end product. I've been cataloging some of this in this blog, but ideally these documents would better live on their own, in a way that other developers could add to or alter them.

It would also be useful to have hosted source code control and file hosting until the project itself is usable. Perhaps it would be best to proceed with a hosted infrastructure for the base bits, and then migrate everything to the in-progress system when it becomes at least marginally usable. In this way, we wouldn't migrate from software to software, but server to server, which would leave a cleaner result in the end.

Also, I think it would be useful to use the simplest solution possible. Rather than have a ton of features that would be difficult or impossible to transfer into the new system, it would just have some basic wiki and upload functionality alongside the source control. Hmm, this is sounding a lot like Google Code.

Google Code seems like a good barebones choice to start out. In terms of incubation, it's as good a place as any to have code to start as a launching point. Github looks like an interesting alternative, and I like some of their reviw features, but I dislike paying for features that I'm getting for free in an SCM tool (svn) that I'm already familiar with, namely what Github refers to as "Private Collaborators". When Stonepath is complete, the pay-per-user model will go away for anyone willing to host their own copy.

So look forward to Stonepath on Google Code sometime soon, to eventually be followed by its own project host.

Sometimes it's easier when debugging to just dump some variable out to the browser to see what it's contents are, even if you are using a debugger, especially when the debugger - as it's wont to do - acts flaky and doesn't stop on breakpoints.

Usually, I have XDebug set up to style the output of my var_dump() commands so that I can see values more clearly. That's useful. But often times, the location that I dump the variable is styled with CSS in a way that makes it hard to read, like at the top of a text-align: center column. Ew. This is a handy fix for that problem.

I installed the Stylish Firefox extension, which allows you to supply custom stylesheets for any page you want. You can also do this with user stylesheets in your Firefox profile, but Stylish is both easier and more flexible.

All you need to to is apply styles to the xdebug-var-dump class, which is output as part of XDebug's var_dump() stylized output. I use something like this in my custom stylesheet:

.xdebug-var-dump { background-color: white; text-align: left; color: black; white-space: pre; font-family: Consolas, Courier, monospace; font-size: 12px; }

That moves everything back to the left, colors it normally, sets a nice monospace font of the correct size (for me, guaranteed -- remember the goal is not scalability/flexibility in this case, but giving me what I need to debug), and ensures that the wrapping works as expected.