The topic where you can tell how you liked the challenge, & how you solved it. 
=> https://www.codingame.com/contests/xmas-rush
Thanks again to the creators (Chimney42, Iuliia, rnkey, Tzupy)
end #92 in gold league
A very enthusiastic contest. I have really appreciate the rules! that are very simple but the bosses were harder that usual. Many thanks to the authors!
First I try a very simple heuristic: push an object in my hand, then push it on the opposite side to make the player spawn on it. And I do not do moves… this has a good results.
then to improve that I had a pathfinding to pick all accessible objets then go to the nearest border (very perf killer: BFS to all items, then choose best possible path by bruteforce)
this makes me to the top silver.
I then do a list of moves: all accessible tile after collecting all items.
After that I done a random search with a deph 1.5 (push+move+push or move+push+move) this makes me reach the TOP100.
I also added a deadlock détection, if a deadlock is detected i do a random push.
My evaluation is simple:
10000 for vistory
1000 for each completed quests
200 for all accessibles items
500 for all quests item that are on the border
I done many try to setup the Smithimax algorithm without success…
Thanks to @MSmits for his article!
1 Like
I really disliked the “nothing happens” during PUSH turns where both players were pushing same row / column.
Repetitive / Stale turns aren’t fun and they weren’t fun in WW either.
As for my bot. Didn’t bother doing a sim and didn’t bother reading the referee, what could go wrong?
I ended up around #130 in Gold with a very bugged PUSH selector. Any attempt to fix it caused me to drop about 100 ranks - see last submitted bot (#238), went last second yolo on the leaderboard.
The unpredictability of the PUSH is what got me the extra ranks obviously.
Overall i would have preferred the turns to not be simultaneous.
2 Likes
A good contest in my opinion. But with a major game-breaking issue : the constant deadlocks draws. Holy shit … Please remove that thing for the multiplayer puzzle. I can suggest 2 solutions:
- End the game after X deadlock turns (5 turns for example).
- Add a new rule : you can’t push the same row/column twice, even if the push is cancelled.
I’ll end around the top #20 i think.
My code is a minmax algorithm with alpha-beta pruning. I test all possibles PUSH. During a MOVE turn, my legal moves are each tile i can reach (and not all the possibles paths). When i move to a tile, i check if i can reach a quest and still end on the target.
Most of the time, my code can reach 5 turns in the future (1 turn = a full push turn or a full move turn).
My evaluation function is simple :
- 100 points when i valid a quest
- 1 point for each tile i can reach
- 3 points for each item i can reach
- 50 points for each quest i can reach
-
-distance(circular manhattan) to each quest -
-3*distance(circular manhattan) to the nearest quest - -14 points if the opponent has one of my quest in his hand
11 Likes
Finished #118 [#55 gold)
I failed to implement working min/max, mc or mcts … so my bot ignore opponent !
I use floodfill to list accessible tiles and quests and i run onther floodfill for each quest i can reach. With all theses datas i can figure out the best path (using as few move as i can).
At this point, i know how many moves i used and i will list all the tiles i can reach with the remaining moves and evaluate each tile (item on it, shape, …).
push turn : trying 28 push + “best move” + trying 28 push + “best move”
move turn : “best move” + trying 28 push + “best move”
Deadlock : just keeping track of the last board (push turn only), if i’m loosing and no change on the board i play another push !
I will fix my english later !
Nice contest
2 Likes
Very good contest, finished 80th on gold league with simple strategy :
- Try all possible PUSH and eval the results (100 points for each accessible quest, + bonus if one quest is going near the border of the grid…)
- Bruteforce the best path to collect all accessibles quests and finish the move on an object (if a quest has been collected) or on the best reliable tile (1 point for each exit on my tile + 1 point if there is a path to the neighbour tile)
Thanks to the authors of this one !
1 Like
Ranked #207
This contest was pretty hard to enter (especially for beginners) which might have been the reason for so few participants. I personally enjoyed the contest, though - at least until my code was smaller than 1000 lines. At some point, I struggled to make progress because my code structure was quite terrible (a lot of copy&paste).
Pros
- great graphics
- rules are easy to understand and deterministic
Cons
- simultanous PUSH moves are rather difficult to handle as the choice of your enemy heavily influences the impact of your own PUSH
- deadlocks and repitions were hard to handle
Congrats to the winners and thank you for creating this game!
codingWhale 
1 Like
Finished #102 Gold
I liked the contest. Also I don’t think the deadlock was so much of an issue, since it was easy to detect.
Push Turn:
Basically minmax with depth 1. I simulated every combination of pushes and valued my options with the mean instead of the min, which lead to way better results at the start and middle of the game.
If I see a deadlock for more than 3 turns, I check who is leading and keep it locked if it’s me else I expect the opponent to keep pushing this lane and try to exploit this.
Evaluation:
- 100 Points quest reachable.
- 15 Points quest in hand.
- -10 Points if quest in enemy hand.
- 1 Point for every reachable tile.
I also tested a few more like reachable items, but it always got worse.
Move Turn:
Basically just walk to the nearest reachable quest until there are no reachable quests left.
Then simulate a push turn on every reachable tile and go to the best result.
1 Like
I’m probably going to finish top 10 (6th before recalc, but so far dropping slowly downwards).
I started with a minimax implementation as that is usually a safe way to quickly get a good rank (I wasn’t going to be around for much of the weekend and was only aiming to get into legend). This got me into the bottom of gold, but really seemed to be struggling to get much higher. In CSB when I’d tried smitsimax I’d very quickly beaten my minimax version so I gave that a quick go and got into the top 30.
It’s slightly more awkward to use here as the available moves aren’t the same every move turn, so my nodes always allocated all 49 possible move children and would then only allow selection of possible ones. This reduced performance a lot as I was always recalculating valid moves and I’m not sure it works entirely correctly (UCT formula would use the count of all moves not just valid ones, score normalization wasn’t based on current valid moves) but seemed to work well enough.
Fixing a couple of silly bugs (e.g. I only allowed 24 different push moves instead of 28) got me into third place by Friday morning, which was enough to get into legend. When I got back on Sunday evening I was down to 15th, and managed to get back to 5th by changing how I handled push ties. My original idea reduced my score if the enemy cancelled my push, but this led to some bad choices.
I changed to remembering my last push and if it was the same one 3 times in a row then I limited my enemies depth 0 choice to be the pushes that countered that choice (as there was a very high change they’d do the same thing again). If I knew what the enemy was going to do I would be able to choose the best counter to that rather than the best move assuming the enemy would try to counter me.
I cut off the search at depth 8 (4 pushs / 4 moves). If depth 0 was a move turn I did a search to find moves that picked up as many active quests as possible in the shortest distance, but for other move turns I just did a floodfill from my position and scored all quest items that were within 20 distance as picked up. I would then allow movement to any square reached in the floodfill (on depth 0 move turns this floodfill was started from the last item picked up with the depth reduced to how far I was still able to move). Items that weren’t actively on a quest were entirely ignored.
My eval was:
- numbers of active quest items reachable
- number of squares reachable
- distance to closest active item (if one was in hand distance = 0)
I scored enemy items 50% higher than my items to try and ensure I would do more to counter enemy than to help myself as it’s very hard to catch back up once you are behind.
18 Likes
Fun contest ! I’m really not into search algos and it was an obvious search algo one so I’m surprised that I enjoyed it (I do like pathfinding tho). I finished 137th (somewhere in gold) which I’m happy giving the fact I didnt had much hope to win.
I did a kind of depth 2 search: “push - move - push” on the push turn and only “move - push” on the move turn. Bruteforcing moves selected by some heuristic.
My heuristic was pretty simple: look for the open area and neighbors of the open area and keep all the rows and columns and flag them as “relevent” + the rows and columns where I have a quest item. Those will be the pushes I try.
For the move it was again in the open area (max 20 distance), but the X number of positions the closest to a quest item (except if there is a an item in the open area than I would grab it).
I also added enemy prediction in the end but i didnt do much to my ranking.
My only problem with this contest is the initial barrier of entry and I think thats why there were so few contestants. Probably a lot gave up before submitting anything. I would suggest this for multiplayer:
Add a wood 3 league that would only require pathfinding to beat. Force the map to be both players at 1,1 and 6,6 with 8 tiles around them “+” tiles and an open path to their only item to pick, so a single push cant break the open path, so anyone who reads the map properly and implement a simple pathfinding would beat wood 3.
2 Likes
BlitzProg, 132th.
Oh man. I was introducing a friend to the concept of multiplayer challenges, and he was wildly set aback by the starting difficulty. I took a long time to get into it myself, and even then it was hard to get any satisfying AI. Still got into gold league, though
-
Wood 2 to Wood 1
I went straight for a Dijkstra search in C++. items are 0, +1 on tiles i can reach, +30 on tiles I could reach if they were moved horizontally or vertically. This would get my bot to position itself in a good place for a coming Push. (Usually, I just go into bronze league with a PHP dummy, but I couldn’t think of any good AI to go for without a search) -
Wood 1 to Silver
Bug fixing (most notably, my AI would go for items that weren’t yet given as a quest) -
Silver to Gold
if my AI has chosen the same push command five times and i’m losing, chose another one. Both players are often looping into a conflicting command, changing to something else avoid a loss that had a chance to be a win otherwise. It didn’t fix more complex looping cases but did its job. -
Mid Gold to ~70th gold
I tried many things. what worked best was simply replacing my Dijkstra driven push by a basic heuristic. Floodfill to detect how many items are in range, give a big bonus if the “tile” i’m holding has an item I need, give a little bonus if interesting items are on the border. Dijkstra was still used for moving around, also changed so every border tiles was a starting node if I was holding an item, so my AI would get “ready” to collect it if no other item was available.
Things I tried:
-
Minimax: I was quickly miss-leaded into this approach. But the sheer amount of possibilities makes me wonder how this is even feasible. Most likely I’m doing something wrong, but nothing really worked, and if it seemed to run at first, I would end up with a timeout.
-
Bruteforce: Picking up a move and anticipating everything the other could do. It seemed a good thing to try, but I ended up with an AI to dodge pushes that wouldn’t happen.
See you next time!
3 Likes
I finished #45 legend using negamax with alpha-beta pruning.
Technically, I go to depth 1.5 on the MOVE turn (MOVE+PUSH+MOVE) and depth 2 on the PUSH turn (PUSH+MOVE+PUSH+MOVE).
Or depth 3 and 4, depending how you count things. Or 6 and 8 ply, I don’t know nobody ever agrees. 
For the first MOVE phase of the MOVE turn only, I use a DFS to establish all possibles paths that contains all reachable quests (taking into account the 20 steps limit).
Basically it’s just a normal DFS with pathing except every time I reach a quest the stack is cleared. In the end you’re left with a list of paths that all go through reachable quests and then to the different reachable tiles.
For any other MOVE phase (moves after a PUSH), for performance I just establish the list of all reachable tiles using a quick BFS without pathing and just assume I can go anywhere while grabbing all the quests in reach.
(Reasonable assumption, the maximum number of steps is mostly a non-subject and worse case scenario on the next MOVE phase the complete DFS with pathing will sort it out)
Evaluation happens at the end of the MOVE turn and is: bunch of points for every quest validated, moderate points for having a quest in your hand, small modifier for distance to closest quest.
Final score is opponent’s eval minus my eval (which meant the lower the score the better, and also caused me plenty of stupid bugs because I would forget and invert the signs all the time)
The main shortcoming I didn’t have time to adress during this contest is that on PUSH turns, because I don’t have the required performance to consider everything at depth 2, after the depth 1 MOVE phase I have to seriously limit the number of possible ‘landing’ tiles considered during the following depth 2 PUSH phase.
I use my scoring eval to establish a sublist of “most likely” tiles, but in practice that’s seriously flawed and probably explains why I didn’t rank any better.
All in all good contest, was very interesting and at least I know what I can improve when it comes back as a multiplayer game!
8 Likes
I have a bad ranking as always (entirely my fault). Tried Smitsimax but wasn’t able to make it run good enough. Simultaneous games are bad for minimax.
I’ll just write random stuff and some code snippets, if it may be useful for someone at multis, in C#: https://tech.io/snippet/w7oVJ0F (Note: it’s NOT a bot, it doesn’t even compile!!!, it’s full of bugs and there are just some random functions here and there. It’s intended for <gold leagues)
Edited: I was wrong about permutations of rows
Deadlocks on Pushes can be tracked by checking GameState hashes. You can track loop DeadLocks too, by searching in a history of hashes+Pushes. I share some simple snippet
BFS seems the simplest way to do the pathfinding. Shared some code. It’s BFS with quests finding. Nothing fancy like bitboards
I implemented pushes as simply moving cells and relocate any player on it. Shared some snippet. I don’t think that’s fast but it’s simple to see the idea of a push. It isn’t just a single function to do all kind of pushes to try to be a bit faster.
I created some Quest guesser, it’s probably bugged. I encoded items 0-11 for player1 and 12-23 for P2
The challenge itself has many “minigames”
-Item Guessing: Future quests can be guessed, tracking Items appereance in either player as Quests. I put some snippet too
-Move Turns: If you find >1 quest item, you have a travel salesman problem. I added too the guessed item, so you permutate all possible moves with <=20 distance, and guessed items are always last. With that I created some initial list of optimal moves. I share some snippet.
-Push Turns: Deadlocks. That’s a minigame by itself, detecting them and countering it if you are winning or losing. I don’t have an snippet because I implemented some naive checks, like only using it after 3 deadlocked turns and if enemy.score > 0 || turn > 20. That’s to avoid early locks in games with lower ranked players
4 Likes
Was thinking of doing this, but really just saving last push command seems far more convenient. There’s no way you’ll have to “push 3 right” three times in a row like in the starter code for example.
I’ve seen loops of 2 push turns
I forgot about those. Was going to save move history and check the sequence of move commands for repetitions, but was stuck at fixing my push bugs.
Woh, 4th. A surprise, but a welcome one. Got lucky this time I guess.
Like quite a few others, I went for smitsimax (hell of a find, msmits!).
For the tile pushing part, I would totally ignore the move part, and run a smitsimax of depth 2.
For the move part, I would run the same algo on each reachable tile.
To compute the path to objects, I had an A*. Now I see that in sim mode I could have gone away with BFS, as I didn’t need the exact path to each object. Oh well.
This got me to legend, at around 35th place. The next breakthrough was deadlock detection, which I did quite candidly (just check if there’s a change in the tiles each player is holding). But it helped getting into the top 20.
After that it was just tweaking parameters and the score function (which in the end is incredibly straightforward, just a diff of remaining cards between player). Every addition I tried made it worse.
Regarding the contest, I found it hard to get started, you needed to code a lot for a first version… Which probably explains why so few players participated. Apart from that it was a very interesting challenge with its own quirks, and the adaptation of a board game I used to play as a kid, so I thoroughly enjoyed it 
Many thanks to the creators!
8 Likes
Push [Row0L,Row4R] is the same as [Row4R,Row0L]
What about player tiles / pushed items ?
2 Likes
Hi Dr, congrats on that 4th place !
By depth 2 you mean push-move-push-move/move-push-move-push, right? how many sims did you achieve per turn?
Nope, I totally ignored possible moves in this phase. I was averaging 25K per turn. Could have probably added a few moves If time had allowed it…