The topic where you can tell how you liked the challenge, & how you solved it.
4 Likes
BlitzProg, 175th
This challenge was very hard for me, considering that my favorite (and lazy) tactic wasnāt viable here (monte carlo) despite how simple the game mechanics were.
-
Wood 3 to 2 : output the last legal action of the list.
-
Wood 2 to 1 : Thatās the kind of challenge I thought Iād like, because a game engine was really simple to code. So I went all out and nuked the boss with a monte carlo approach. I wasnāt as smart as I first felt, tho.
-
Wood 1 to Bronze: My trusty and lazy monte carlo approach did good, but nowhere near my original expectations. It went to the top of the wood1 league but stopped there. A very simple heuristic approach did the job much better (simulate each move, evaluate it, pick the best result)
-
Bronze to Silver: was simply a matter of fixing a few glitches from the heuristic. At this point it became clear that randomly simulating wasnāt the way to go. Almost got to gold as well, stopped there 3rd of the league (but I didnāt get past)
-
Silver to Gold: Youād think you can wait for someone to push you when youāre 3rd in a league, well after some waiting I went down to about 15th! Too bad.
So I added a single level of deep searching (minimax with depth 1) : Donāt eval for a move you play straight away, eval once more with every possible legal action of the opponents for each move, and keep the worst evaluation for that move. You end up playing the move with the best āworst caseā scenario.
Got me in the gold league (~200/300) -
Gold league: oh neigh! such an insane difficulty. Added iterative deepening and tweaked my heuristic, gained like 100 extra ranks for that, but thatās still very far away from the boss. Looks like I still have a lot to learn.
Tried the following:
-
Alpha Beta Pruning - All I get about this trick is that I end up skipping the good moves. So the opponent wins more easily.
-
Opponent detection: Being able to find out where an opponent is when you canāt see him give a very interesting advantage. So long you can do it reliably enough! Sadly I couldnāt get my own to work.
Iām interested in how others approached the Challenge. The top players had insanely good scores, itās getting me curious. I had fun and had the opportunity to practice Minimax algorithm, I didnāt do that in a quite long time
1 Like
35th
This challenge was easy for me - i just implemented minimax in wood2 on the 1st day, got a perfect 100% winrate, and was top-3 bronze in the first days of contest
my scoring was using voronoi diagram to check āmyā area size and instead of getting game points it was trying to get more area by pushing enemy to the corners where he most probably would get into a trap
and i used non-linear values for scoring the current cell heights - 0, 3, 5, 6. I did it to make unit 2 go up heights more early and not have him sleep at 0 height for the entire game with unit 1 jumping at 3 heights alone
14 Likes
180th
Finally managed to Keep It Simple Stupid! Bronze to Gold:
- do I score
- count accessible cells (with a decreasing factor, distance = 1 -> +1, distance = 2 -> +1/2)
- unit height
I added my units scores minus enemy (visible) units scores for every possible actions. No minimax (I was timing out).
1 Like
My usual simple stuff :
- Evaluate full grid for a single player position based on the height of the occupied cell (large factor), heights of the rank-1 accessible neighbors (medium factor) and height of the rank-2 accessible neigbors (small factor)
- I used non-linear values for scoring the cell heights (try Fibonacci or squares) to favor higher cells
- pseudo-Voronoi for determining which cells I can access before the opponent
- score for the full grid is score of my units - score of the opponentās units + pseudo-Voronoi score for each of my units
- opponent units are entirely ignored if their positions are unknown
- hardcoded depth 2 minmax for evaluating the opponentās moves when known
- attempt at detecting the opponent by comparing the current grid to the expected state after my move of the previous turn. This is certainly the most complex and probably less reliable part of my code.
This kept a very stable top 30 throughout the entire week, then utterly failed to keep that after the gold boss appeared and I finished 78th. A bit disappointing but thatās life In fact my code this time was so simple that there was basically nothing I could tinker with to look for an improvement (virtually no magic numbers) and I was entirely out of ideas - and time - by Friday.
One of my satisfactions is that for once I have rather clean and well-structured code that got reliable results for every push (none of that āranks anywhere between 50th and 270thā nonsense) and, for once, doesnāt rely on an actual certified bug in order to perform good 
5 Likes
Congrats!
Got 301st. I just evaluated the first turn possible moves. I think I got something wrong in my eval since I (sometimes) managed to deduce positions of the enemy in the fog of war but ended behind you.
As Magus wrote in the chat during the week, the simpler the eval, the better.
Good game @_CG_jupoulton and nice graphics.
1 Like
I tried a voronoi approach as a late addition to my heuristic and that didnāt work at all for me! I guess I should have fiddled more with it.
Maybe Iāll try again when the challenge become available again in multiplayer.
1 Like
u need to predict enemy to do that, and u need to make it not forget about saving your 2nd unit from getting into traps - if one unit successfully attacks and gets the entire area of your 2nd unit, then if 2nd unit will fall into a trap it wonāt lose any score
1 Like
Around ~50 in Legend (hopefully after the rerun).
Had trouble going to Bronze as usual with a simplistic python AI, so I had to code a very rough minmax in wood1. Anyway, that was the way I wanted to go anyway.
Made it to gold with a very simple eval : 5.0*(my_score - enemy_score) + (my_legal_moves - en_legal_moves). This evaluated only for the last node at depth 2.
Then to get to top gold, I changed everything to alpha-beta and iterative deepening. Got to top gold by implementing a rough detection of enemy and stayed there for a while. When the gold boss got out, I added more info to my eval, mainly two things :
- A floodfill to see which cells I could get to before the enemy
- A small bonus to get closer to the enemy
This could get me to legend.
Then I planned on improving the global performances of my algorithm, because the eval was relying on my ābuild_legal_movesā function which was eating 50% of the time. I spent whole week-end trying to do that with absolutely no success. So I did some punctual optimisations here and there yesterday evening and left it like that.
I loved the contest, and Iām happy to see finally another contest when we can practice minmax. A bit disappointed because I feel like I could have done way better but Iām still legend so thatās that.
What I liked about the contest :
- Very simple engine
- Simple rules yet lots of complexity in the game
- Had, once again, a lot of fun on the chat, and I want to thank all the people I had fun and chatted with !
What I disliked : - Ugh that fog of war
- Getting the score as input would have been of great help.
- Damnit Iām going to lose this one to BeberLeNewbie ā¦ EDIT : Finally I finished right in front of him Perfect ending.
4 Likes
76th
Used minimax at first.
Found that it time-out easily.
Decided to go back to the basic -> make a good board evaluation function.
Write 1500 lines of scoring function with test-cases: LINK
Made it to Gold.
Write enemy prediction function with test-cases: LINK
Made it to 100th.
Add more stuff to the scoring function.
Made it to 76th.
2 Likes
Hello there, 300th
I did not implemented much things in this contest, not inspired enough even if it was cool. 
To get Wood 2, I just printed the first legalAction provided in input.
To get Wood 1, I directly went to a Monte Carlo with DEPTH = 10, simulating the moves and evaluating each round with a patience term (0.7^round). From this point, I didnāt use the legalActions provided in input anymore. My evaluation was simple: for each of my units, the score is increased by 1 for each height occupied. Furthermore, I add one extra point if I hit a height 3 during the round.
To get Bronze, I added the possibility to use the PUSH&BUILD action. For that, I simulated the first action considering that if Iām aiming to a cell occupied by an opponent, I change the action to a PUSH simulate it, then the evaluation is the same. The opponent is then ignored for the rest of the simulation. I added the opponent in my evaluation, getting negative points to my score for each height occupied by an ennemy unit. This way, my AI thinks it is good to PUSH an ennemy unit if it makes it fall to height 0.
To get Silver, I corrected my code to take into account the fog of war: if I donāt know the position of an enemy unit, it is ignored to prevent my simulation to crash.
To get Gold, I just changed a bit my evaluation. For each of my units, I add 1 point for each height occupied and add an extra point if my unit reached a height of 3 during the round I evaluate. Then, I compute how many cells are reachable from the unit position, divide the number by the total number of cells of the map and add it to the score (therefore, itās better to move somewhere where you have access to more cells). I added a malus if the unit is blocked (cannoāt perform any move). For each of enemy units, I do the same but the score is decreased instead of increased, and if a unit is blocked, this is a bonus. I also played a bit with the DEPTH of my MC to see if it changed some things.
To make it simple: my AI tried to block the opponent with a depth 1 when seen, and otherwise it just tries to score keeping as much cells reachable as possible, considering āthe higher, the betterā, and thatās it. I didnāt try to compute where the opponent was.
1 Like
285 th, Gold
I first tried with my genetic algorithm, but it was not a good solution for enemy moves.
And then I tried a MCTS algorithm, but I couldnāt manage to simulate enough to obtain results. I tried to limit depth, but I had to evaluate positions and I tried quickly, no good result. So I desactivated depth exploration.
I finished just by evaluating all possible moves I could do with a complicated fitness functions.
- Routage to count accessible cells (the farther the less points : 1 point for depth 1 accessible cells, and less for depth 2 and so on). It allow to find long routes but prefer open spaces.
- Evaluate good builder : height, accessibility, liberty degrees of enemy
- Am I a good pusher on this action ? if enemy falls in jail, if enemy couldnāt come back, if enemy looses liberty degrees, if enemy is farther from map center
- Evaluate position : best if I go towards the map center, if I have a lot of liberty degrees, if I can access a lot of cells, if I am in altitude, if I can access level 3 cells
- Avoid cells where a jail is near : I could be pushed by an enemy invisible to me now.
- Detect if Iāve been pushed to display a message (important ! )
- If one of my entites have pushed, then I had more fitness points to move the other entity : it allows to āwaitā for enemy to move again near me and then push him
It is complex and not that efficient, I better have used a Negamax algorithm.
The game was very interesting !
1 Like
14th Legend (at the momentā¦)
Well, I really liked this challenge, and Iām quit proud of my results Itās the very first time I manage to reach the Legend League !
Wood 3 to Wood 1 : I just printed legal moves, and used a very simple heuristic
Then, I found difficult to reach the Bronze League with only a heuristic, and I didnāt want to spend to much time trying to do so, so I began to create a engine to simulate the game, and I implemented a min-max algorithm. Then, I just improved my min-max all the week (alpha-beta, heuristic, perfs, bugfixā¦), until I get in the Legend League.
Here are the main things I used in my heuristic to score a game situation :
- the height of the current cell (for each unit)
- the height of the cells next to the current cell that can be reached from the current cell (for each unit)
- a malus if a unit canāt move anywhere
- the size of the areas of each unit in the Voronoi diagram
Then, I subtract to the score of the current player the score of his opponent.
I also created something to predict where the ennemies are, mainly based on their last positions, and on the fact that they must be near the cells built in the map.
Whatās more, I think I was quite lucky, because I was in holidays all the length of the contest, so I could spend all my time coding for the contest, without being disturbed
Finally, I wanna thank all the people who created this contest, and of course the persons I chatted with during the contest !
Thank you, and see you soon !
5 Likes
I finished somewhere around 20th (still calculating and its very close). I used the negascout variation of minimax with a voronoi based heuristic. Until sunday the only enemy tracking I did was storing the last position Iād seen them and assuming they were still there. Pushing would update their position to where theyād been pushed (and failed pushes would mark the other enemy as in that location to stop it getting stuck in a loop).
It was quite clear after legend opened that lots of people had much better enemy tracking, and Iād fallen down to around 25th by Sunday morning. I implemented some quick improvements (mostly just spotting where they had built and setting whichever enemy I thought was closest to that point to be in one of the squares round the built one) and got back up to 15th, but I feel like the lack of a proper solution to this was my biggest problem.
4 Likes
I will finished around #5 (maybe #4 or maybe #6).
I have the following features in my code:
- A system to detect the ennemy in the fog. Pretty hard to code but you need it.
- A minimax algorithm with alphabeta pruning.
- My evaluation function contains the following:
- The score of each player
- The height of the cell of each pawn
- The number of possible actions for each player
- A āvoronoiā.
- A bonus/malus if a pawn is entirely blocked
- A bonus/malus if a player has no more action
Iām waiting for the PM of the top 3. I really want to know what feature is putting them so high.
7 Likes
Hey. 245th, Gold. Language: C.
[9th of Germany, 12th of lang:c]
This is my third CG contest after cotc and c4l.
Again I first must thank a few people from the GENERAL_DE chat:
@eulerscheZahl, @DerRadikaleRusse, @Babajajuk and many more.
Strategy:
Wood3: just print the first of the legalActions
Wood2->wood1->bronze created a small scoring function to evaluate all legalActions, using
[details=this scoring]```c
if (currentTile+1 == nextTile) { //climbing is good
score += 100 + 10nextTile;
}
if (currentTile > nextTile) { //going down is bad
score -= 100 + 10(nextTile-currentTile);
}
if (currentTile == nextTile && currentTile == 3) { //scoring is the best
score += 300;
}
//build scoring (later: other action scoring)
pos buildpos = getNeighbor(nextpos, action->dirs[1]);
int buildTile = char2height(map[buildpos.y][buildpos.x]);
if (buildTile == 3) { //finishing a tower is bad for now
score -=300;
}
**Bronze Rank ~100:** Introduced Pushing into the scoring, something like [details=**this**]```c
if (newTile < pushTile) { //pushing enemy down is good, the further, the better
score += 100 + 10*(pushTile-newTile);
if (pushTile == 3) {
score += 100; //bonus for kicking enemy off scoring level
}
}
if (getFreeNeighbors(newenemypos, enemies, mine) == 0) {
score +=1000; //pushing enemy into a hole he can't escape from is best!
}
if (getFreeNeighbors(newenemypos, enemies, mine) < 3) {
score +=500; //pushing enemy into a hole he can't escape from is best!
}
```[/details]
also I stole the `printf("ACCEPT-DEFEAT (āÆĀ°ā”Ā°ļ¼āÆļøµ ā»āā»\n");` from @EulerscheZahl (sorry)
**Bronze Rank ~59:** Fixed a stupid bug in scoring (using `currentTile` instead of `nextTile`) and scored climbing with a higher value
**Silver Rank ~170:** Fiddled around randomly with stuff in the scoring
At that point I was starting to rewrite my code to actually simulate a single action on a given game state and evaluate the full board after that action. This took forever and it never got as good as the previous version.
I tried to implement a floodfill to end up with a voronoi diagram but realized I'd need the enemy position for that.
Instead, I wanted to incorporate a more visual debug output like @EulerscheZahl did and included the very nice and short [GIFenc](https://github.com/lecram/gifenc) but actually never got around to use it for much :o/
Because I got more and more frustrated and didn't know whether all my code was working the way I expected, I looked into UnitTesting Frameworks that would work with the style that is given for CG games (i.e. all in one file).
I ended up with [Greatest](https://github.com/silentbicycle/greatest) which fit my needs really well and so I spent an evening, writing Unittests for all the functions I used in my scoring.
It turned out, they all worked as expected, which was a relief because that meant that "only" my scoring was bad.
But this basically frustrated me so much that I didn't do much on Saturday. Even my attempts at being funny in the code didn't do much
[details=**funny?**]```c
/* huge bonus for getting enemy into a pit */
if (isPit(enemy1, newState) || isPit(enemy2, newState)) {
score += 9001;
}
/* huge penalty for going into a pit */
if (isPit(player1, newState) || isPit(player2, newState)) {
score -= 9001;
}
```[/details]
On Sunday, in one last attempt, to get out of silver, I prepped my code to accept the parameters for the scoring function from the "outside" so that I could run the amazing [ParameterFiddler](https://github.com/eulerscheZahl/ParameterFiddler) by @EulerscheZahl on it.
To do that "properly" I reset all my param values to 1.0 and let the Fiddler run while I was out to eat.
**Silver->Gold:** After about 4 hours of runtime, the fiddler came up with some values which turned out to not help at all :o/ BUT they did make me think of some possibly better values. In the end, I used [details=**these**]
```c
float height_factor = 3;
float freedom_factor = 1.2555931818181711;
float sameheight_factor = 0.5175625000000198;
float climb_factor = 0.701777859179884;
float bonusheight_factor = 0.7682927777777669;
float cliffpenalty_factor = 0.881430232558123;
float bonusremovefreedom_factor = 5;
[/details]
The āweirdā values are still from the fiddler. And those got me to gold (Rank ~193/360) on Sunday/Monday night at 0:48
It was an amazing feeling to watch that last Battle unfold!
So I did not do any ārealā simulation and I never got around to finding the enemy, but still got to Gold with 800 lines of C including comments and unit tests.
Thanks again for a great game, lots of fun and frustration along the way.
PS: the ādetailsā function for the code snippets works in the preview window, but doesnāt seem to work on the actual pageā¦
3 Likes
84th and 1st in PHP \o/
My IA is pretty simple. Taking the list of legal moves (the good idea of this contest), evaluating them and output the best one
When the opponents positions arenāt known, I take the last known positions, then, analyzing the gameboard, I detect the nearest modified cell and eventually update the position of unit to this cell (even if I know itās 100% false, itās enough for evaluations)
Evaluations are different for me and the opponent :
- The height of the my cell and neighbours, and the number of accessible cells for my units
- The distance to nearest corner of the gameboard and the number of accessible cells for the opponent units
Gold bot was too strong for me.
Iām already looking for even a single link between the game and the theme. But that was fun anywayā¦
4 Likes
64th and 2nd Scala
My bot simply takes the move that maximizes my eval function which is a floodfill based heuristic.
If at least one of the enemy units is not visible it replaces the (x=-1, y=-1) given in the input by an approximation of its coordinates.
I wasted a lot of time trying to implement minmax but I had performance issues so it never worked. 
1 Like
Thanks for good contest.
Lollypop, 501st
Wood 3 to 2: output the first legal action
Wood 2 to 1: legal action with higher position after it.
Wood 1 to Bronze: if i have legal action, that can block enemy, iām block enemy, if havenāt, ligal action with higher position.
Bronze to Silver: push enemy, if i can, otherwise previous strategy.
1 Like
Hi everybody,
This challenge was a great one
rank 40th Legend
- Wood3 to Wood2 : take a random move from the legal list
- Wood2 to Wood1 : Simulate + Evaluate on points, height and neighbour heights
- Wood1 to Bronze : Evaluate with more precision with the formula (N ^ P) * F on all counts
- N : Count something (height, points, etcā¦)
- P : Power to increase or slow eval progression
- F : Factor to balance vs other criterias
- Bronze to Silver : Adding some other evals :
- Count free cells where you can move
- Trap malus (free cells == 0)
- Is there an enemy near my units
- Silver to Gold : Playing with evaluation criterias
- P < 1.0 for counting height makes your units climb together
- P > 1.0 for counting neighbour heights makes your unit build stairs higher faster
- ā¦
- Top Gold : Here was the hard work :
- Knowing where is the enemy (divination() function):
ā Remember 3 states : state before your last move, state after your last move, state now (after enemy move)
ā Use possible enemy position in fog
ā Manage all cases (cancel moves, ā¦)
ā When you canāt find position precisely, give the first possible - Generate moves
- Negamax then finally MinMax 2 levels (me + enemy)
- VoronoĆÆ to count the cells nearest from me
- Voronoi ā3Dā to count the volume of all cells nearest from me
- Gold to Legend : The WondevBoss was very hard to pass
- Thanx to all people who helped to make it down
- Watching top matches made me think to have a very strong āVoronoiā value to block enemy
- Malus value on enemy proximity to gain benefit from my divination() function
- Trying all night without success except have given the Boss + 3.0 points (sorry, yes it was me)
- Having a VoronoĆÆ x 1000 in the morning to pass it (with othersā help to push me up)
- Legend : Here began the very hard work :
- Alpha beta prunning to see upto 4th depth
- Sort generated moves with a light evaluation (point and heights)
- Here my perf was not very good (< 15000 simulations / 40 ms) so I had to optimize all my code (1800 LOC)
ā Replace my states copy by a reverse simulation function. I got problems to make it work in my alpha beta implementation, so I could use it only on some depth (I kept it on 4th depth).
ā All my states are calculated in each node and then copied, but I didnāt have time to extract all those states in one only place
ā Truncate number of moves on each depth (final values : 45 30 12 4). - playing with evaluation values :
ā Forcing on Voronoi 3D was strong vs top 20 but not vs top 50
ā Forcing on Voronoi (1D) was stong vs top 50 but not vs top 30
ā Inverse P > 1.0 or P < 1.0 for heights or free cells did very opposite strategies - Finally, I spent last night to push every strategies I could, and repushed the best one on the morning.
Thanks to all participants and especially to BeberLeNewBie and Aveuh (the top -3 as said Magus when we were all three on bottom Legend) and all others I chatted with.
Very good game, graphism, music (heu sorry, that was my musicā¦ ) and eager to see the multi and debugg my alpha beta un-simulate functions.
Thanx to all CG team !
+1 to Beber & Aveuh for their last matches to win the 50th vs 51th place (who won the T-shirt ?..)
9 Likes