CHECKERS - Editorial

yellow_agony · August 12, 2012, 12:23am

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Challenge

PREREQUISITES:

Graph theory, Search

PROBLEM:

Best explained in problem statement.

DETAILED EXPLANATION:

This was a challenge problem and so one din’t need to find the optimal move
sequence. Though it is not proved to be an NP complete problem, as stated here,
this problem is an open problem and so if you
do have an algorithm which finds the optimal sequence, you should try to publish
a paper quickly

One of the easiest methods to get accepted was using randomization. Randomly
choose a checker and try to move it along a random direction (except for two
“bad”
directions). After sufficient number of such random moves, grid
would be solved. The reason is in every turn we’re decreasing the “distance” of
current configuration from the goal configuration.

Setter’s solution involves filling in the goal squares one at a time, using
a bfs to find a piece that can be efficiently moved there. Maybe one could also
try some sort of local search with solution of one of these methods as the base
solution and an appropriate neighborhood function.

Better
solutions will take advantage of the jump rule and set up long series
of jumps (especially for dense grids). Setter’s expectations were that top
solutions would reach a score of 5, though it was only in last hours, ACRush
reached aronud 4. All others are way behind at 2.5. I’ve not understood ACRush’s
over 1000 line solution but I saw a function with the name MST in it One
combinatorial idea is as follows : consider a graph on all cells with upto three
edges per piece, corresponding to available jumps over that piece. It is highly
benificial to have large connected components in this graph as single piece
would be able to make several jumps.

One thing that really bothered us was there were a low number of submissions.
Even more interesting was the fact that there wasn’t a single comment on the
problem page uptil around 1 hour before the contest concluded.

I request contestants to share the high level idea of their solutions here.

In the end, here is a trivia from setter: The title for this problem comes from the fact that it’s a
one-player version of Chinese Checkers, but Chinese Checkers is neither Chinese nor a variant of Checkers!

SETTER’S SOLUTION:

Can be found here.

TESTER’S SOLUTION:

Can be found here.

Sumudu · August 12, 2012, 5:35am

My approach was fairly simplistic to start, and I added on a couple of ideas to improve the score a bit but probably I needed to spend more time on this problem than I had available.

First I wrote a function that would use a kind of BFS to find the nearest (in terms of number of turns) piece that could fill a given cell; a basic solution is then to fill cells in increasing order of (x+y), “locking” each one in place once set.

The first modification was to fill all the goal cells with (x+y) odd first, the idea being that there would be many jumps available to fill in the even cells. It turned out that randomizing the order of odd (x+y) gave a better score here. A twist on this idea is to fill in every other cell for a given (x+y), again with the idea to increase the chance we can make jumps later on.

One modification that made a big difference was to choose the most “efficient” piece instead of the “nearest” piece – i.e. that piece that maximises (decrease in (x+y)) / (number of turns). I guess it increases the tendency to move pieces from outside the goal area, as well as promotes longer jump sequences. It also turned out that with this modification, it was better to do the BFS for all empty cells in a given class (ring # and parity of x).

The last idea I tried was to have the moving of each piece randomly “early exit” and restart the BFS, hoping that this would introduce new jump opportunities. Unfortunately this didn’t improve score very much, and I was stuck in 4th place, though it’s possible that a certain choice of exit probability would perform better.

I don’t have much experience working on this type of “marathon” problem, and looking back I would have been better served choosing an approach that would benefit more from using more time. I did add some randomisation but the overall structure of the solution was pretty rigid (moves one piece to its final cell at a time, ignoring the early exit stuff) and this obviously misses many chances for beneficial jump chains – I’m pretty sure that reaching avg. score of 3 or more requires a very different approach.

ACRush · August 12, 2012, 2:23pm

Let’s use an example result of my code (may not the final one) on one case where n = 10, p = 8.

INPUT:

*..**.*...
.*..*..*..
..*....*..
..*...*..*
..**...*.*
*.....**.*
.*..**.*.*
..*..*....
.*......*.
.*.******.

(1) Make all even (x + y) pieces connected (8-directional) to the region (x + y < p), and all odd (x + y) pieces adjacent (4-directional) to at least one piece.

*oo**o*o..
o*oo*oo*..
oo*o*o.*..
oo*oo*...*
*o**..*.*.
o*o..*.*.*
oo*.**.*..
o....*....
..*.*.*.*.
.*.*.***..

Note : all empty cells in region (x + y < p) are marked by ‘o’.

(2) Fill all even (x + y) cells within the region (x + y < p). Each piece takes about 3 turns.

*.***.*...
.*.***.*..
*.*.*.....
.***.*...*
*.**..*.*.
.*...*.*..
*.*.*.....
.....*....
..*.*.*...
.*.*.*....

(3) Fill all odd (x + y) cells within the region (x + y < p). Each piece takes about 2 turns.

By (1),(2),(3), we have about 3.3 points.

(*) Add random notes : improve to 3.6 points.

(*) Compute MST to improve (1) : improve to 3.7 points.

(*) In step (1), using bfs while the size of one component is 2 : improve to 3.75 points.

Below is my submission logs.

From Aug. 8 to Aug. 9, (1.71 pts) I confused by the scoring mechanism by counting moves instead of turns.

I saw both thocevar and acube had submitted 1.95+ points solutions.
I realized that there must be some misunderstandings of the problem description.

Using (1), (2), and (3), about 3.4 pts.
http://www.codechef.com/viewsolution/1242350

Add random notes, about 3.6 pts
http://www.codechef.com/viewsolution/1242639

Add MST issue, about 3.7 pts
http://www.codechef.com/viewsolution/1244163

All issue, about 3.75 pts
http://www.codechef.com/viewsolution/1246581

Last thing, it was also easy to “sandbag” on previous submissions by adding extra moves which made me displayed a 1/3 socre as the actual score.
Then removing the sandbagging code for the final submission in the last minute.

thocevar · August 12, 2012, 4:18pm

A strategy for around 2 points was relatively simple. Define distance of a piece as (x+y). Choose the farthest piece and move it as close as possible in a single turn. This gives you a band of pieces which is slowly moving towards the origin (0,0) and allows you to make at least 1 jump with every move.

I think the reason for such low number of submissions is that there is not enough incentive for tiebreaking when you’re down in 100+ place. Even among the contestants with 7 or 8 solved problems (top 30) very few bothered with this problem. Maybe increasing the range to [0-2] points based on your position (not score) on the tiebreaker would turn up the heat. This way you could move up the standings significantly with a good solution even if you didn’t solve one of the other problems.

bcurcio · August 12, 2012, 5:53pm

I think the idea of using the [0-2]point range interesting for more participation, as it is, I think that it only makes a difference for the top spots.