You may or may not be aware of the game of Peg Solitaire. This problem presents an alternative objective to Peg Solitaire. Given a board with some pegs, where you are allowed to make moves that are valid in Peg Solitaire,
Maximize the number of pegs that are left at the end.
EXPLANATION
Peg Solitaire is a Combinatorial game. There are finitely many states that are reachable from the initial state. We have to search the state space and end up at the most desirable state.
The desirability of the state is defined by the number of pegs that are left when there is no move possible.
This problem can be solved using some metaheuristic or search technique. Metaheuristics pick a candidate solution and try to optimize them. Search techniques try to explore the solution tree and percolate towards the optimal solution. This editorial is based on Beam Search, which was used by Hiroto while testing this problem.
Beam Search builds the search tree similar to Breadth First search.
We iterate through the nodes at each level and find the nodes for the next level.
But, not all the nodes for the next level are stored. Only the top B nodes ordered by some scoring funciton (that scores each state).
B is called the Beam Width.
Beam Search always terminates at Final states (those from which you cannot go ahead).
Hence we tradeoff Optimality (since we donāt go through the entire search tree) for Completeness (we will always have some valid solution).
Beam Search will always end up in a state in which no moves can be made, while pruning to find a state that hopefully has more pegs remaining.
The scoring function used by the testerās solution is as follows
Initialize the score with a large value.
For every move that could be made, reduce the score by 1.
Ahah ! My first idea was to implement a beam search as well. At least at the beginning. But, the only scoring function that came to my mind was the opposite of the number of remaining pegs. When i discovered (eureka!) how stupid it was (because at a specific level of the tree, all states would have the same cost), i simply discarded the whole beam-search method. After reading that editorial, i feel like iām a ā¦ letās say ā¦ a complete moron !
At least, iāll think different the next time, and wonāt probably discard the whole method just because of choices i made !
Can anyone help me with this: When I was trying to import ārandomā in my python code, judge was showing a runtime error. I believe its because my code has thrown some exception to the judge. In one of my successful submissions I just included the import random statement, and didnāt use it anywhere, still I got the same runtime error. Can anyone please tell me what can be the possible reason? Iām I missing something? I couldnāt find any thing in wiki related to it. One difference that I can see is, Iām using python 3.3.0 and judge has python 3.1.2. Not sure if its because of that.
Donāt really get what the point to āreduce the score by 0.7 for every empty cellā. On every level of the tree this increment will be the same for all states. So it is equivalent to just number of available moves.
I also have used a beam search but did not come with a good scoring function. I use the following ones:
Minimize the number of available moves (for me performs very pure)
Minimize the number of existing pairs of consecutive pegs (was better)
Similar to 2. but has some cost (negative or positive) for full row or column of pegs
With different combinations of this functions I can reach only 0.334 points.
It was quite challenging for some of these functions to implement update after the move in O(1).
Another idea I use is to divide the grid into several sub-grids, run beam-search on each one (which allows to use larger width) and then run on their union.
After the contest I looked through @hirosegolfās solution and realized how I fool I was. The best and the simplest scoring function is to maximize the number of pegs in the cells with fixed (x+y) mod 2. Just using this for both residues mod 2 without any combination with other score functions allows me to score 0.334 as before (see here, but be careful there is 20Kb of code :)). Combining this with my previous solution allows to reach 0.346 (see here). Probably developing this ideas further and seeking for better combinations could allow to reach desirable 0.36 which would bring the second place at the contest.
@bcurcio: Thanks for reply! But I think import should work since in one of the Wikis for faster IO they have asked programmers to import psyco in program.
So the question is still open! Would like to jump deeper? Here are the links to my submissions:
One which was accepted: http://www.codechef.com/viewsolution/1550131
One resulted in runtime error: http://www.codechef.com/viewsolution/1550134
My actual strategy in tie-break problems is āimplement something working and try to find better solution later (when other problems are to tough or I have new brilliant idea )ā
I implemented simple āfind first peg that can jump and jumpā strategy and got score 0.1755 (0.49pts).
Later I wanted to try this improvements:
do not choose first possible jump, but randomize this and run this in loop (try multiple possibilities) according to time limit
count number of pegs on left/right half of the board and top/bottom half of the board and from all possible jumps select the one that jumps to the half with min number of pegs
Unfortunately I had no time to do this, I was stucked on CBARS O:-)
As usual, the scoring function is the most important aspect of strategies like beam search (I also used something similar). My scoring function was pretty good (though not good enough to get me the first place at the contest ) - it only got me 0.359456 points. Anyway, my initial version of the scoring function was the size of the maximum matching (where you have an edge between two adjacent cells if they both contain pegs). However, it turns out that the size of a simpler, but maximal, greedy matching works better. Finding a maximal matching is pretty easy to do in O(N^2) ā for instance, we traverse the board in row order, and for each row, in column order. For each peg, we first try to match it with the peg above it (if it exists and is unmatched) and, if not possible, with the peg to its left (again, if it exists and is unmatched). The size of the matching is a good approximation of the minimum number of moves needed to get the board into a final state.
Since the scoring function was the bottleneck of my solution, implementing it as fast as possible was very important. It turns out that you can implement the scoring function I described with O(N) bit operations (considering that each row is represented as an N-bit number ā since N<=30, int or unsigned int is enough for that) if you precompute some values (2^30 is too large a number, but splitting it into two halves makes it manageable already). Moreover, when trying multiple moves originating from the same state, the score of the newly obtained state does not need to be recomputed from scratch (e.g. if you made a move in row i, column j, then the maximal matching up to row i-3 does not change and you do not need to start from the first row again). By having a fast score function, I was able to analyze more states and, thus, get a better quality solution.
The origin of my scoring function also came from an odd-even argument (i.e. trying to keep those pegs with odd or even sum of coordinates), but it seemed to me that using a maximal matching would get me more points.
Did anyone try an ant colony approach? It was the first time I tried such an approach so if anyone did anything similar, please share. My idea was that my program sets itās own scoring function based on exploration. (because I couldnāt think of a good objective function)
First, for each 3x3 possible square, I calculate a number, that represents this square. With this I try to detect shapes, and collapse rotations. Since there are 2^9 possible square boards, I just calculate a number for the square, and get an ID number. (I got 66 different square boards)
Next, for each move, I calculate a number that is the ID of the 3x3 square centered in the moved piece after the move, concatenated with the ID of the 3x3 square centered where the piece falls after the move. In some way, this is an ID for a move.
What I try to score are which moves are good and which are bad. So, I run several DFS, calculate the ID of each move of the path, and depending on how many steps it took to reach an ending step I update the āgoodnessā of each move. What I do to choose a move, I use the goodness to weigh the probability of choosing that move, initially all moves are equally probable.
I finished with 0.223402 [0.623pts]. I think it would have come out better if I actually knew what I was doing my main problem was the low iteration count, how to identify a move, and I should have implemented in some way something to forget old ārewards/bonusesā. Maybe the whole approach doesnāt even make sense, no idea, but it was fun.
)ā