JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Marathon Matches TCO17 Poland - KnightsAttacks Post your Approach
 Post your Approach | Reply 7th place provisionallyThat was a pretty nifty problem, really good for the 3 days duration. Congrats to the organizers and to nika for a pretty dominant performance!I did pure Simulated Annealing, heavily optimized (not enough judging by some example results from other competitors).My SA move is simple, choose a cell purely randomly, and flip it (if it had a knight, remove the knight, otherwise add a knight). At first, I used O(cell neighbors) operations for applying the flip and undoing the flip (in case the move wasn't accepted).This meant around 8 + 8 operations per iteration.However, the number of accepted moves is significantly lower than the total number of tried moves, therefore it would be better to have an ultra fast 'ComputeMoveDelta' function and a slower 'ApplyMove' one (which would be called only for an accepted move).I stored the delta for a flip in each cell (potential[cell] = if the cell would be flipped, by how much would the score change?). This leads to an O(1) 'ComputeMoveDelta' function. Whenever I applied a move (by flipping a cell), I had to update the potential value for neighbors of neighbors of the cell (flipping a cell would affect the potential for other 33 cells in the worst case). This was done only for the accepted moves however.That was pretty much it. If we colored the board like a chessboard, the black cells and the white cells are completely independent, which means we actually have 2 disjoint subproblems. I tried to use this fact to no avail.I also tried to guide the SA somehow (by not choosing a cell purely random) but couldn't find anything that worked.Catalin
 Re: Post your Approach (response to post by CatalinT) | Reply My approach was very similar, but with few details that I will describe later.Somehow, instead of picking a random cell, trying to flip sequentially, from left to right and top to bottom for example, produced much better results...CatalinT, if you have some time try to make this change and see if it helps.I couldn't find a good explanation...
 Re: Post your Approach (response to post by wleite) | Reply Thanks wleite, great idea!Tried it locally, huge difference ... (-400 on seed 3).Congrats on the 2nd provisional place, must have been a tough match for Java :)
 Re: Post your Approach (response to post by CatalinT) | Reply 1st place provisionalMy solution has two stages. First one is exactly what CatalinT described. Instant move evaluation, slower updates. Have some idea where 33 comes from but I just had 8x8 worst case updates, on average much fewer than that. This whole thing is running for the first 2 seconds and can get reasonably close to the optimal solution.Second stage is doing the following until time runs out: choose 16x16 subgrid randomly, run 8K iterations of exactly same SA (only minor change in temperature calculation) and revert the board to the last optimal state obtained in the process (regressions are reverted, but moves that lead to same score are good). This process can converge to near-optimal solution given enough time, which is more than 10 seconds for bigger tests. EDIT: here I've managed to use the fact that black and white cells are independent and color of allowed moves is chosen beforehand randomly. After the contest I've tried wleite's idea and not only it is positive change as it is, but also replaces relatively expensive random generator calls with simple iteration which is a huge deal for harder tests. Got almost -500 on seed 3 without any other tweaks.Here are the best scores obtained after running this solution for a few minutes:```seed score 1 23 2 598 3 88698 4 3594 5 5144 6 21087 7 23455 8 62631 9 43554 10 24841 ```