Description of method


Let's start with a recent post by Brendan Owen to the egroups Eternity mailing list.

Brendan wrote:

> I think so, the basic idea behind the solution process was outlined here.
>
> - Finding out what endgame shapes tend to be easier.
> - Dividing the board into two regions.
> - Estimating the needed size of the end game.
> - Finding the easy and hard pieces by randomly tiling the endgame or another
> related shape.
> - Using a limited BFS to tile the start game keeping easy pieces.
> - Speed increases ie CCells, void checks, etc.
> - Avoiding ATG searches.
> - Showing parity is practically useless for this puzzle.
> - Estimating the number of solutions.
> - etc.

This pretty much describes our method at the top level, except that we do not divide the board into two regions.

Here is one way to think of tiling. For an algorithm which keeps trying to place pieces we can pretend there is a typical branching factor (i.e., typical number of ways of adding a piece to the current position) which depends only on the number of placed pieces, and so you get a graph like the above one. `A' is meant to be the area above the x-axis and below the curve, and `B' is the area below the x-axis and above the curve. So the expected number of solutions is exp(A-B), which is independent of the algorithm used, although A and B can individually depend on the algorithm. In general the better the algorithm, the closer the curve is to the x-axis and the smaller A and B are.

If A<B then the problem is overconstrained and we would expect no solutions unless someone planted one, in which case there would be one solution and we would be aiming at finding the solution. In this case I guess the only method would be some kind of an exhaustive search. The running time would be about exp(A) because after `p' pieces are placed the search will quickly reach a point where it can't branch any further. Making the algorithm branch on the most constrained sites first will reduce A and so make it quicker.

If A>B then the problem is underconstrained and you have extra freedom before you reach the point p. Clearly we want to use this freedom to arrive at the best possible situation when we hit the point p. This is done by getting rid of the least tilable pieces first and leaving as good a board shape as possible. We will have to arrive at the point p about exp(B) times before we expect a solution. As before, after arriving at p the search will quickly terminate. We should spend some effort in getting to p in a good state, but presumably this effort will be comparable with the time taken to exhaust from p, so in all the algorithm will take about exp(B) time to find a solution.

For the full Eternity board we are in the second case with A>>B. We have estimated there are about 1095 solutions to eternity, though this is very rough. Others have put the figure at 10120 and they may well be right. There is some critical boardsize, c, for which we would expect 1 (unplanted) solution. We did estimate this c some time ago but I can't remember our conclusion. Maybe it was about 70 for a typical set of pieces. Whatever it is, it probably represents the most difficult size to solve. So the more pieces you add after c, the easier the puzzle gets which may seem a bit surprising. Given a larger boardsize c+r, one has freedom to place the first r pieces in many different ways. Presumably it is easy to find a way of placing them (choosing bad pieces) such that the resulting size c problem is easier than typical. Of course that is how you solve Eternity itself. Here is a plausibility argument which shows why you might expect there to be a critical size c. The number of ways of arranging the n pieces (not worrying about small overlaps) is something like n!an for some constant a, and the number of constraints these have to satisfy to actually fit is proportional to the total perimeter of the shapes which is proportional to n. So you expect something like n!(a/b)n solutions for some constants a and b (a/b<1). For large enough n this will be greater than 1. I think Brendan Owen has said this before in a different way.

Solver details

We use a vector based representation of the board. This has the advantage that when you do a local lookup, the index to the lookup table contains more relevant information than for a bitmap representation. For example: say you can afford a lookup table with an 18 bit index. This is enough to encode all hexagonal templates in a bitmap representation, and is more than enough to encode all paths of length 7 using a vector representation. It may be that the typical length of boundary segment that passes through a hexagon template is of length 5, which is less than 7 and so not as good. All the same, I don't know if a vector based method is a lot better. It's probably not too big an issue. In practice we had two lookup tables. One was indexed by paths of length 6 and each entry was a list of all possible ways to place pieces at the third site along the path. The other was indexed by paths of length 11 and each entry was one bit saying whether or not it could possibly arise as a boundary (similar to being tilable on both sides). Constructing this table was probably the most fiddly and awkward bit of programming we did, because using a vector representation there are many ways that lines can hit and cross themselves, and many cases to be sorted out.

Before we took on Eternity proper, we worked a bit on making a solver - i.e., a program that exhaustively searches smaller shapes. To make a solver, you need to make the program decide which site to tile at any stage and whether or not to terminate work on a partial when it can be proved that it is/will be stuck (I think this is called void checking here on this list). Our void checking is quite strong: after the placement of any piece, we make sure that all length 11 subpaths of the boundary are valid according to the above-mentioned lookup table. In addition to this, when we decide which site to tile, we calculate how constrained every site is according to an n-ply search (n is adjustable, but typically only 1 or 2). So if there is any site where you can't place n pieces leaving a boundary which passes the lookup table test then the partial will be rejected. We think it is generally important to tile the most constrained site, but in some cases it is clearly a waste of time and even a simple fixed order is better, so we have some idea how we might improve our method of choosing sites. For hex9 we find the 73752 solutions in about 25 seconds (with no special symmetry code), which at the time we wrote it (c. Feb 2000) was quite a bit faster than other publicised solvers. On other benchmarks like hex36 we were also quite a lot faster. But on one of the latest benchmarks - milestone 32 - our solver is 20 times slower than `Soliver'. On the other hand I think milestone 32 is particularly suited to a fixed order because it is long and thin (so there is an obvious good order) and there is no altitude-type boundary.

One way of seeing why we want to choose the most constrained site first (assuming there is no cost in finding out what it is) is this. Pretend that the branching factor when there are n pieces in place is always bn. Then the number of nodes searched is N=1+b0(1+b1(1+b2(1+...))). If bn > bn+1 then you reduce N by swapping bn and bn+1, so you get the smallest N by putting b0, b1,... in increasing order.

What is the branching factor at a particular site? You could say it is the number of legal placements that cover that site. But some of those placements may lead immediately to dead ends (e.g., 30 degree angles), so it seems reasonable to discard these and count just the placements that don't lead to immediate impossibilities. But this treats placements which have only one possible followup move the same as placements which have many followup moves. Wouldn't a more refined measure treat the former with less weight than the latter? Well maybe. If you took this to the extreme then your `measure' would end up being how many global solutions there were, so you have to take into account how long it actually takes to calculate the local information to get a meaningful balance. If you expect to do say 10^10 nodes of work underneath the current node, then it is presumably worth choosing the site to branch on with quite a lot of care, but if you only expect 10^5 nodes then you can't afford to waste too much time choosing the site.

The above waffle was leading to the idea of a 2-ply version of the local branching factor (which is not just the sum over local placements of followup placements). Our solver decides on an appropriate n, works out an n-ply version of the local branching factor at each site, and then branches on the site with the smallest one. However it seems that for the kind of length exhaust we typically did (of the order of minutes), it is rarely worth using more than the ordinary n=1, so this method does not gain all that much in the cases in which we used it. But because I like the n-ply local branching factor, I'm include a description of it here. Perhaps it might even be useful for other search problems.

Data gathering

(We're using the notation that a region is the empty shape to be tiled, and its size is the number of pieces that fit in it.) Having made a solver we set about tiling `endgame' regions. But here we run up against a fundamental problem with eternity pieces. Say for example we want to to tile 1000 regions of size n and count the number of solutions for each to see what kind of regions tend to be more tilable. If these regions and pieces arise from placing 209-n pieces in the Eternity grid in the usual way, then finding a solution to any one of them obviously means you have solved Eternity anyway, so that is no good. If on the other hand the regions and pieces you use are artificial in some way, then you don't know that the answers you get are meaningful. Basically any method of predicting how well you're doing is likely to rely on a form of extrapolation somewhere along the line. We took a lot of care trying to make sure the extrapolation was OK, but we still couldn't be sure it was, so as a result we still can't be completely sure how often to expect a solution.

We chose to extrapolate by using extra pieces, i.e., exhausting regions using more pieces than fit in the region. This method, and the modeling process that followed, underwent many changes, but we'll describe our first version of it here. To begin with we worked with regions of size 24 (obtained in some fairly ad hoc way) and then replaced the 24 pieces in remaining hand with 90 random pieces. The advantage of using extra pieces is that we expect to get solutions, but not to take too long to exhaust. With these numbers we are sort of getting (90 choose 24)/4=about 1021 times more solutions (fake) at the cost of a much smaller increase in running time. (The 1/4 comes in because there is a 1/4 chance that a random set of the 90 pieces will have the right parity.) Unfortunately these random pieces are not really comparable to the 24 pieces that were there naturally. For example, at any site on the boundary there will be a piece from the original 24 which fits there (this follows from our most constrained site choice), but there may or may not be a piece from the 90 random pieces which fits there, so for this and other reasons the random pieces don't have the same distribution as the original pieces. This illustrates how the extrapolation process may lead to wrong results. We did have some refinements in our later versions to reduce this problem, and some others to monitor it.

Determining the model parameters

This is a description of the mathematical process we used to turn the data from the above exhausts into a probability that a given region (of a certain size) can be tiled with a given set of pieces.

HTML version
(If this comes out as gibberish then try one of the lower two.)

PDF version
(This is likely to work if you use Windows, and may work anyway.)

Postscript version
(This is likely to work if you're using a version of Unix. You may need to use ghostview to read it.)

Model parameters

probs1
These are the parameters (li and mj) resulting from the process described above. We gathered enough data to make sure the parameters had more-or-less converged. As a check, we evaluated the parameters using only one half of the data (data being a collection of many instances of (region,pieces)), then using only the other half of the data. We were only satisfied we had enough data when the two results were similar.

probs2
These are the parameters resulting from a modeling process which should be more accurate when you use it on a good (tilable) set of pieces (which is what happens in practice).

Here is how to use the parameters in probs1 or probs2. Given a region of size 24 with one simple boundary, work out

c0=the number of corners (changes in direction) in the boundary,
c1=the number of altitudes in the boundary, and
c2=the number of half-equilateral triangle edges in the boundary.
(For example, piece 1 has c0=6, c1=2, c2=12)

Then for each of the 24 available pieces, add the number in the row of the file corresponding to that piece. Add this to m0c0+m1c1+m2c2 and call the result x. The probability estimate is then 8exp(x).

The rest of the method

We now have a probability of being able to tile a size 24 region, but we are going to need the probabilities of being able to tile other (greater) size regions. So we would like a file like probs1 or probs2 for each size up to 209. (In fact we really need to know the rate of finding solutions, i.e., probability of solution divided by time to search. But it doesn't cost too much to ignore this because using the breadth-first-search method described below we hope the expected rate is approximately an increasing function of the probability, so maximising probability is approximately the same as maximising rate.) We used some not especially good methods to try to determine the correct model parameters for sizes greater than 24, making use of the model for size 24 boards. (For sizes much larger than 24 it is not possible to use the same method as we used for 24, because it will take too long to do an exhaust.) These methods involved mimicking the procedure which would be used for an actual run which tried to find solutions. These runs are tree-like, in that nodes of size n regions have child nodes (some of which will be kept) which are size n-1 regions. We tried to adjust these larger size model parameters so that the output value from the model on a node predicted the probability given by the size 24 model on its children (or later descendants). The procedure we were using was not all that good and the resulting parameters are almost certainly not as good as they could be. This was one of the things we were trying to improve before we were so rudely interrupted by an actual solution, which occurred earlier than we expected.

When you've decided on the model parameters for all sizes greater than 24, you have a score for a node. (A `node' is just a situation - a region together with the remaining unused pieces.) The breadth-first-search (BFS) method we used then works like this. You start off with an empty board and all 209 pieces unused. This is the top node (level 0). You then decide on the most constrained site and generate all the piece placements which tile that site. You then take the top 10 scoring nodes of these, and throw away the others and also throw away the top node (though you have to remember your family history if you want to be able to resconstruct a solution). This gives you 10 level 1 nodes. At the next stage you generate all of the children of all of the level 1 nodes, take the 10 most highly scoring according to the level 2 score and throw away the rest, and so on. You can improve the performance by doing extra lookahead and increasing 10 (the `width'). We were using lookahead about 2 (but with quite strong `void checking') and width about 10000 on the run that found the solution, although we have since tried widths up to 1000000 and these are better. This method was described by Patrick Hamlyn on the mailing list a long time ago and is a very nice method. I wonder if we are using it slightly differently from him, since he said he had difficulty persuading his program not to squander the good pieces, which shouldn't be a problem using absolute scores.

At some point (e.g., level 178) one should switch from a BFS to just doing an exhaustive search on all of the existing nodes. Actually, as you might expect, there are slightly better methods that make a smoother transition doing pruned searches, but I think just switching to an exhaustive search at the best point is not all that bad.



  • Back to eternity page