Minimax, Voronoi Territory, Draws

[tdeluca]

In the interest of stimulating the strategy discussion before the end of the tournament, here is my top-20 approach.

VORONOI TERRITORY:
My bot is playing a simple strategy that currently puts it among the top 20 bots. It uses minimax (see brikbrik's post) without pruning, etc. It simply looks two moves deep and chooses the highest scoring move using its board evaluation function. Usually there are no more than 81 boards to evaluate. (Exception: beginning a game where bots can move in 4 directions).
The evaluation function is simple. Partition the board into squares OUR bot can reach first and squares THEIR bot can reach first. I think of this as a Voronoi partition of the board. The score is simply count(OUR squares) - count(THEIR squares).

GO FOR THE DRAW:
Should your bot go for a draw? I think a perfect bot would draw against a perfect bot in every (symmetric board) game. If your bot avoids the draw by avoiding collisions your bot is making a suboptimal choice and will lose against a perfect (or a good enough) bot. My bot chooses a draw over a suboptimal move.

PROS:
Intuitively, this strategy should excel at open-field battle.

CONS: This strategy fills space poorly and so does poorly in the end-game. Here is a game where I "win" by going for the draw and then I lose by having a poor space-filling algorithm (the 2-level deep voronoi territory algorithm performs poorly here.) http://csclub.uwaterloo.ca/contest/visu ... id=3537348

CONS: This strategy splits territory unnecessarily when choosing between equally ranked moves,even before the end game. See this game, where it could have stayed against the wall and won: http://csclub.uwaterloo.ca/contest/visu ... id=3563386

Do you use an evaluation function like mine?
Do you use a single evaluation function for the whole game or a hybrid approach?
How many levels deep do you go? This is a chance for all you C/C++ programmers to brag!
How can I make my bot better?

Cheers! Discuss!

[dutchflyboy]

Well, my evalutation function isn't completely right yet -> not in the top 20 But I get to 8-10 levels deep with an unoptimized minimax (no pruning). This is enough to let it fill quite efficiently. What language are you using.

[tdeluca]

Previously Scheme, currently Python.

[dutchflyboy]

By the way, filling isn't all important: http://csclub.uwaterloo.ca/contest/visu ... id=3568374 I won without filling the board very convincingly (in my defense, it does look quite nice).

[aipcaish]

Actually I use a very similar evaluation function: my reachable area - opponent's reachable area, with +INF and -INF if it is a win or a loss. Then I use minimax evaluating 5 moves (my and opponent) ahead. Followed by some heuristics to choose one move when more than one move has the same score. My bot () seems to be doing okay...not too great (currently ranked 25).

Two problems I found with my bot:

- In larger maps, when evaluating 5 moves ahead doesn't make difference - the heuristics make the bot do some bad moves (usually in the beginning of the games). By the time the opponent gets close by, the opponent already has the advantage and CAN trap me.
- I found that my bot can trap the opponent (boxing the opponent in a smaller area), but sadly after trapping the opponent and moving away, its space filling is so bad...that it ends up out dying first (not always, but it does happen)

[Krishmin]

My bot's been ranked in the top 15 for the past few days, mostly hovering around 5. My strategy is pretty similar to yours, but a couple of quick points:

1) I've added alpha/beta pruning to my minmax tree, which is a substantial time-saver. Presumably it would be an even better optimization if I worked to sequence the evaluation order, but I haven't gotten to that yet. My program (C#) currently works at a hardcoded depth of 4 (per player). Depths that run easily within 1 second on my machine seem to time out on the server, so I've just left it at a fairly conservative number. Presumably it would be more efficient to determine the depth conditionally, but I haven't gotten that sophisticated.

2) I've played with your Voronoi Territory idea, but I'm running with something similar, but much more basic. I'm ignoring the actual pathing and just counting squares based on their absolute distance from the bots. Then, like you, I just return a calculation of mySquares - oppSquares. This keeps my bot nice and aggressive, and he does a good job of fighting for the center. Occasionally the lack of pathing does trip him up -- mostly in the larger and more complicated maps. My next step is to make this more sophisticated.

3) I actually use different analyses depending on whether or not our bots are in the same room:

If they're together, I execute a minimax tree with the calculation described above (and if the evaluated node has them reach separate rooms, I just count the difference in the room sizes)

If the bots are already in separate rooms, I ignore the opponent and only look at my moves (so in this case, I'm looking 8 moves ahead for my bot). I also added an evaluation to determine the number of spaces that are in hallways (ie only one entrance). This code isn't perfect yet, but the combination of greater depth and hallway-aversion makes his fills reasonably efficient. I don't know much about pathing algorithms, but I wonder if it wouldn't be possible to actually determine the optimal path on maps of this size.

4) On draw aversion, I agree -- I have the draw set to 0 value, so he will always accept a draw rather than make a sub-optimal move. This means that there are a bunch of maps that he will always draw on against other strong bots.

Unfortunately, I think that's a large part of the ranking at the top -- how many times each bot happens to have played the "draw maps"... I've also thought that it would be really nice if games were played preferentially between bots of similar ranking -- that way I could see more examples of how my bot fares against others in the top ~50... right now those matches are few and far between (and not very enlightening if they're on drawing maps). Anyway, I'm also curious to see what others are doing, and maybe my strategies will give you some ideas.

[JofferLamesch]

I probably won't have more time to invest into my bot (I just spent about 5 hours total in it), so I rather share my strategy.

I'm using the Echo Alorithm (without any min/max) for the perfect shortest path to the opponent. This works really well (And I suspect the top bots to doing this as well ). If there are multiple paths, I'm choosing the one closest to the enemy (reducing the max distance in one direction between me and the enemy), or closest to a wall (So I don't waste space on my path), or the one with the highest score (based on the floodfill method at the moment)

However when you are closer to the enemy, you have to choose a different strategy, so you could use your strategies here. (My bot will follow the other bot into a trap , which happens with not perfect bots).

I was planinng to implement a min/max with a simple evaluation function, when I'm closer to the opponent.

I also evade moves that generate a crash, except I'm moving into a territority that's smaller than the opponent's teritority (which would give myself a disadvantage over the perfect opponent bot)

I was planning to add a better evaluation function for the territory size (I'm currently using the floodfill method here in the forum, but it's not optimal) and for the end game (when both bots have their own space).

You sure can improve your rank by a few positions by using the Echo Algorithm at the beginning.

[dmj]

Hi,

I guess I use the Voronoi + minimax too. I have tweaked my python code repeatedly, causing various bugs that sometimes give me funny losses. On my machine, with a wide open map, my code only goes 2-3 levels. (hence the tweaking) Originally the depth was set, but iterative deepening made things much better. As the board gets limited, it can go much deeper. The bot even had a brief stay at #1, although that was because of the luck of the draw with the game scheduling.

As for draws, I do think they should be weighted more for wins. But that is just because mine will ram anyone if it thinks it might lose. Some of the boards are more of a "the bot should at least draw" instead of "the bot can draw, but it is not obvious how to make sure of that".

Good luck to everyone, and this has been fun

[Lykos42]

I'm using it too. Though my bot is only in his beginning stage. The one I submitted last is using minmax, but I've got a new one with alpha-beta-pruning (this version will still be whithout sorting) which will be ready soon. I only have to tune him with the time limits. Surely, I will use iterative deepening soon, but not yet in this version. I don't have a survival mode, either, but that will also be one of the next steps.

[krzyk1]