1 month was justified for this kind of game though.
If it’s too short and the game is complicated then there isn’t enough time to explore it.
2 Likes
Many thanks for this really rich and deep game.
I really appreciated the one-month format. The lockdown allowed me in one month about what I usually have in one week. I am now pretty sure there is a choice to make: go for legend or have kids! But still, one month was very nice.
I wanted to try and build some efficient functional-oriented algorithms to deal with grid-based games. This game was a perfect playground. I ended up with merging and intersecting lists of lists (list of (x, (list of (y, data))). Mixing that with an offset function, you get really efficient computations. It helps also in flood-filling or pathfinding algorithms.
I used only heuristics to choose the next moves, and I kept no records of the opponent’s mines. I could reach mid-silver this way, but I really should work harder if I want to reach legend some day!
2 Likes
Same types of questions as for kovi:
- can you evaluate the maximum branching factor, both for your MCTS and MC ? I could consider 568 types of sequences on turn 0 when SILENCE and TORPEDO were available, I don’t get how this number allows any kind of meaningful simulation…
- typical depth reached with the MCTS (not including the depth 4 rollout) ?
Can you also describe a bit more the rollouts that were used for the MCTS ?
I do like the “nonsense score” idea you brought to your AI 
EDIT: Also, I don’t get the logic of the “proba * (1 - proba)” you have described everywhere in your PM ?
1 Like
The branching factor can be reduced by pruning some actions. I pruned some without regret : torpedo/trigger that have no expected damages. I also pruned some (but not many) that seemed bad : silence when only one direction is allowed (only in monte carlo and after first turn), torpedo/trigger that have too low expectattions.
Hence the branching factor remained high, and my searches were not expected to find the global optimum. But when guided, one can be confident in finding good solutions.
In the case of mcts, I expanded a node after each action (not only after turn). Also I used two distinct (decoupled) trees (one for me, one for the opponent). A typical reached depth (for expanded nodes) was of 2 turns, but with some “knowledge” at depth 3-4. The rollouts are similar to MC but with mean update (not max).
The motivation for p(1-p) to reward the detection comes from the proportion of pruned opponent paths.
To illustrate this, consider a SONAR action and let p_i be the probability the opponent is in sector s_i. Assuming there is no other action in the turn that impact detection, if you choose to SONAR in s_i :
- you will success with proba p_i and will prune 1-p_i
- you will not succes with proba (1-p_i) and will prune p_i
In consequence you will expect to prune p_i (1-p_i) + (1-p_i) p_i = 2 p_i (1-p_i).
The same holds for trigger/torpedo where sector s_i is replaced with damage area.
Notice that it vanishes for p=0 and p=1 (nonsense actions 
) and it is maximal for p=0.5 when you can split the set in two subsets of equal sizes.
4 Likes
Hello again everyone,
I have performed some improvements in my code in order to beat this terrible legend IA!
It was hard, I have added these functionalities to be able to do it:
- Compute fatality, being able to do surface + move + silence + torpedo in any order to win (I didn’t include mines)
- If in danger (mines or torpedo) and silence possible, compute the best combo move/torpedo + silence. Move and torpedo are optionals, but I think it’s better to perform them first. In this case, torpedo was launched if I have more than 70% chance of touching my opponent.
- Timeout security. With the previous combo, I lost quite few games in timeout, I modified my code to compute between 1 and 3 turns in advance according the already consumed time.
- Better starting position. Thanks to one of the PM, I am searching for the biggest square, if equality the one this the best neighbour squares
- Modifying my computed score:
3000 * MY_POSS_POSITIONS + 1000 * REMAINING_TILES - 500 * TORPEDO_RISK - 500 * MINES_RISK + DIST_TO_OPP
MY_POSS_POSITIONS => Number of positions where my opponent think I am
REMAINING_TILES => Number of accessible positions (computed with Connection Point, less effective than Tron but not that bad)
TORPEDO_RISK => If my opponent could shoot near me, what are the percentage of covered possibilities by shoot near me + penalty if on my position (so silence with 0 or 4 would be better)
MINES_RISK => Probability computed on each tile for mine, score is the sum of my path
DIST_TO_OPP => Well, not sure if it is useful, but trying to be at more then 6 distances from opp, unless my torpedo cooldown is better than opp, in that case I try to be at a distance of 4. - Power-up order: TORPEDO > SILENCE > MINE > SONAR. And a little modification. If SILENCE cooldown is slower than torpedo, it is better to go for silence.
Now I am ranking 16 and truly happy. to be there =)
Thanks a lot to post the game that quickly in multi, it might seems weird but I didn’t had the time to finish all what I wanted to do during the month of the contest ahah.
P.S: I think my filling area (to compute remaining tiles) is not performant (basic BFS). If someone have a good idea to perform it (with connection points or something similar) it would be perfect =)
4 Likes
How can i detect if an island is around my sub?