Peg solitaire

Hi,

i'm writing my own version of the peg solitaire game. The problem is that my program run too slow. On configurations with 32 pegs, the programs can run even for 30 mins.

I use simple brute force, with a cache that store invalid configurations (those that cannot be reduced to only one peg). I order the edges of the search space with a function that try to minimize the covered area and the 'dispersion' of the board. This function work better if i use the look-ahead technique. But if the move at deep 10 is wrong, than the program simply have to consider too much configurations.

I don't have access to two of the most important books on the subject, so i really don't know how to go on.

I know, for example, that there are some necessary conditions called 'pagoda functions'. Can someone explain me how to use and generate this functions? Can i use a pagoda function with an arbitrary configuration of pegs?

Thanks,

I assume one of these is Winning Ways, Vol. 4. What's the other one? Volume 4 is only $40 at Amazon.com, not too bad if you're serious about the subject; I don't think volume four assumes too much familiarity with the earlier volumes. You might also want to check local university libraries (if any, many people overlook these although they are generally open to the public).

A pagoda function is a function defined over the board so that no jump can increase the value of the board. So, if the desired ending position is one peg in the center, and this position has value 1, any position with a value less than 1 is bad. The function doesn't change for different peg configurations, but one can use multiple pagoda functions to prune the search tree probably much faster than what you are doing. I don't know if there are algorithms to develop pagoda functions for arbitrary sized boards, that might be an interesting area of research.

I work as a C++ programmer and have been reading Winning Ways off and on for almost a year (though I still have much to learn), so if you have any specific questions, just ask.

My university library doesn't have it.

What do you mean for 'desired ending positions'? I use a brute-force search, with a cache, look-ahead and an evalutation function that try to order the edges of the search tree to catch the best moves first. But if there are 25 or more pegs and there is an error at deep 1 or 2, than the program take too long to backtrack at that level...

In practice, how can i use the pagoda function to cut the search space?

Example 1: Any position with exactly one peg.

Example 2: The position with exactly one peg, with the peg in the center of the board.

If i have an arbitrary configuration to solve, how can i say :'this configuration, with a single peg positioned at coordinates (i,j), is one of the (really) possible final configuration'.

I ask this because if i can compute the possible final configurations, i can than compute a pagoda function specialized to work with one of that final configurations (the manhattan pagoda function). Otherwise, i really don't know how to use a pagoda function (wich? for wich final configuration?) if i have to solve an arbitrary initial configuration...

If you do a google search for the phrase 'pagoda function' one of the early results is an article called 'Modelling and Solving English Peg Solitaire' which sounds related to your problem.

I'm not sure I understand you; pagoda functions are independent of configurations. You probably will want a set of many pagoda functions, but not all of these will change after each move.

Here's what I would try: Before you even know the configuration, have some ordered set of pagoda functions. You can create a map from every jump to a list containing its difference for each pagoda function. (I'm assuming the board is known at this point, even if the particular start is not. So by 'jump' I mean any particular move possible if pegs were in the right places.) No jump will increase the values, so these will all be non-positive.

Once you have start and goal configurations, calculate a vector of the current score for each pagoda function, and another vector representing the goal.

There are two sets of jumps we'll be interested in: first, the legal jumps from any particular position. Secondly, the set of jumps which decrease any pagoda function to less than the goal value. The size of this second set will always be decreasing as we get deeper, since pagoda functions decrease as legal moves are made. Now, you only need to search the intersection of these two sets. When this intersection is empty, you can start backtracking. This should happen shallower than searching based solely on the set of legal jumps - you may need to change the set of pagoda functions to optimize the program. I think what you are doing is like this, except your set of pagoda functions is empty.

Use DFS. After each jump you try, just add the difference vector for that jump to the current score, and continue.

By the way, in your initial message you say you are keeping a 'cache' of all configurations that cannot be reduced to a single peg - I suspect that this could be quite large (since 33 holes gives roughly 2^33, about 8 billion, configurations) so I wonder if memory use is part of the problem. Also, how are you searching this cache?

The problem is that deciding if a configuration c is reducible to a configuration c' is NP-complete. So, it's difficult to have that final single final configuration. I could use the rule of three to decide if a game is not playable, but the rule of three did not give me a method to enumarate all really possible final configuration (the rule of three is only a necessary condition).

I want to write a program that can solve an arbitrary initial configuration, created by the user. So i don't know the final configuration.

So, which pagoda function should i use???

No, i'm really new to pagoda function. I have read so little about this functions and i don't know if i can use this functions to make some cut to the search space (remember that i use a brute-search algorithm).

Uhmm..., i'll read more carefully what you have wrote..i don't understand english very well so i have not understood very well what you have written..

I map each configuration to a 64-bit value. The cache is a bb-tree. When i search a particular configuration in the cache, i check also the symmetric configurations (for a given configuration there are 7 equivalent other configurations).

The cache really help to speed up the process, because the game is highly symmetric. By the way, some configurations take more to calculate.

The cause is clear to me: the order in which the possible moves are tried make the difference.

So, i use a function that try to say:'this move is better than this other'. But this procedure needs to look-ahead 3/4 moves to work decently.

But the look-ahead take much time...so now i have a program that in some cases work faster without look-ahead than with lookahead.

I've not found any other cut to use to speed-up the process

A pagoda function does not completely solve this problem; it simply identifies some cases in which c is *not* reducible to c'.

I believe the standard peg-solitaire problem has exactly one desired final configuration: only one peg remains, and it is in the exact center of the board. If you have something different in mind, then please tell us what it is.

As many as you can find. Finding them is difficult, but applying them is easy.

Let S be the set of all valid final configurations. Let pf() be a pagoda function. Let PFC be the minimum value of pf(x) where x is an element of S.

If pf(N) < PFC, then N is not reducible to *any* element of S, and so you can immediately stop considering N. If pf(N) >= PFC, then N might be reducible to one or more elements of S.

If N passes all the pagoda functions that you can find, then you can perform more complex types of analysis.