Hoping for lots of discussion after Friday

[Maxime81]

I later changed to an A* implementation where my heuristic was the euclidean distance from me to the opponent.

This caught my eye , since you especially mentioned euclidean distance. Is there any specific reason you used Euclidean distance over Manhattan distance?
As far as i know ; MD is generally used over ED in A* , especially if environment doesn't let diagonals , mainly because of the cost of "square root". And if you get rid of square root and use h = x^2 + y^2 ( instead of h^2 = x^2 + y^2 ) ; your heuristic will be a lot higher than your g which will kinda ruin A* and turn it into greedy best search first.

I'm also using a A* to know where's my opponent and at a moment I'd tried with the euclidean distance (not exactly in the A* but anyway..) because I wanted my bot to alternate between directions (no : NNNNNWWWW but NWNWNWN...). But it was only a try 'cause it's dirty.
My solution to this problem is in my evaluation function to add the maximum of any direction. For example the shorter path is "NWWWSWWNN", there are 3 N, 5 W and 1 S so the maximum is 5. And in my previous example "NNNNNWWWW", my bot will try to have the same number of N and W all the time. The penalty is really low so it's just in case of an equality between choices of course.

[barank]

Maxime81 -
Oh i also had that problem for a time. I used A* in decision process for a short time ; after that it was all about "if isolated" and count territories while checking isolation etc.
And in that time , I used a tie-breaker for that. With a little tie-breaker which i cant exactly remember right now ; it always preferred the squares closer to opponent ( actually , not the closer ones. More like ; it'll choose the square closer to , direct line between me and opponent ). Really hard to describe ; so lemme just find it..... ugh can't find it , my coding folders are total mess i'll just try here ;

x1 = current_square.x - opponent.x
y1 = current_square.y - opponent.y
x2 = my.x - opponent.x
y2 = my.y - opponent.y
h = h+ (x1*y2 - x2*y1) *0.001 // kk i thought i would be easier to understand like this but doesn't seem so now eh?

This is kinda , "best of both worlds". It'll move diagonally in maps like "empty-room" or "huge-room" but it'll also prefer "NNNNWWWW" like movement (any word to describe this? ) in maps like "joust".

Still i don't think A* is a crucial part of anybodies bot so it's just a little enhancement.

[dutchflyboy]

but it'll also prefer "NNNNWWWW" like movement (any word to describe this? )

Straight? Square? I think both describe it quite well.

But could you explain where the formula comes from? It seems some crossing of a few formulas. BTW, have you tried using the manhattan distance? I found it to work quite well, and I think it's the fastest way to get a correct approximation of the distance. (MD = abs(x1-x2)+abs(y1-y2))

[barank]

but it'll also prefer "NNNNWWWW" like movement (any word to describe this? )

Straight? Square? I think both describe it quite well.

But could you explain where the formula comes from? It seems some crossing of a few formulas. BTW, have you tried using the manhattan distance? I found it to work quite well, and I think it's the fastest way to get a correct approximation of the distance. (MD = abs(x1-x2)+abs(y1-y2))

Yes actually i used MD , that little code was just a tie breaker. Check my previous post about MD

MD + Tiebreaker is to keep movement smoother as Maxime81 said. How does it works?
First of all , i didn't calculated myself ; just don't wanna look like trying to get credit for it
And then , its just a vector cross product. As far as i remember , its simplified determinant. Not really sure tho , didn't work on the proof ; but only checked if it works. If you try it on small map like 5x5 , you'll see squares will give smaller tie-breaker values as they get closer to the vector between Me&Opponent. Since it's h += tie-breaker ( or h = MD + tiebreaker if you will ) ; you'll end up with smaller h , thus smaller f ( f = g+h ) etc.

ps : just curious if i am the only one who likes talking&discussing about algorithm more than writing it

[dutchflyboy]

ps : just curious if i am the only one who likes talking&discussing about algorithm more than writing it

Nope, don't worry, you're not alone. Ok, now I understand what the code is for. I never thought of it, but now I'm looking at it, it's quite neat: it encourages the bot to get on the same diagonal as the opponent.

[psb217]

One thing that I haven't seen mentioned yet is any variable weights being given to the vertices "dominated" by each player when doing any of the various voronoi-based heuristics. I wrote my bot in Python and it seemed to be doing fairly well with respect to the other Python bots, despite only achieving 2-3 plies of minimax, with the occasional 1-ply search on large maps.

One of the largest jumps in my bot's apparent performance came with the introduction of variable weighting for each vertex within a player's voronoi region. Basically, I counted each vertex with 1 neighbor in the region as 0 points, "..." with 2 neighbors as 1 point, etc. I thought of this as representing the overall "robustness" of the region that each player controlled, and it implicitly includes the "move to least neighbored neighbor" heuristic while somewhat maximizing the degrees of freedom within a controlled region. It also helped avoid the growth of "abscesses" around single-neighbored vertices to which some algorithms seemed prone. This weighting provided a significant boost over simple vertex counting.

Unfortunately, my algorithm was pretty general and didn't properly account for either the grid structure of the graphs represented by tron game boards. This really killed my evaluation time when I extended my algorithm to use the "tree of chambers" approach, as I was unaware of efficient algorithms for calculating articulation vertices in general graphs, so I brute forced it by checking neighbor connectivity after removal of each vertex. This made things really slow. I wish I had known of some of the techniques that kduleba was using, as I would have had to worry less about some of the dramatic horizon effects that have to be accounted for when you can't be certain that an algorithm will achieve more than one step of lookahead...

Hopefully my bot can hang on and do alright, though it wasn't until Friday morning that I got around to adding the articulation vertex and tree-of-chambers code, so I didn't have time to fully work the kinks out before my final submission. Though, later testing shows that performance shouldn't be _worse_ than my previous attempt (with the strange exception of the quadrant map).

[a1k0n]

One of the largest jumps in my bot's apparent performance came with the introduction of variable weighting for each vertex within a player's voronoi region. Basically, I counted each vertex with 1 neighbor in the region as 0 points, "..." with 2 neighbors as 1 point, etc. I thought of this as representing the overall "robustness" of the region that each player controlled, and it implicitly includes the "move to least neighbored neighbor" heuristic while somewhat maximizing the degrees of freedom within a controlled region.

This is one of the reasons I believe my bot did so well and I totally failed to mention it thus far. For every square in the region a given player controls, I count the square and its number of edges with different weights. I wasn't sure what the best weight was, so I took a machine learning approach: I wrote a utility (just a variant of my existing bot) which analyzes an arbitrary game when fed in end-to-start, and wrote a perl utility (a pastebin link was up on this forum) to fetch an arbitrary game id from the contest site which could optionally show the game backwards. My analysis tool found the point at which the players "separated", figured out the maximum possible fillable space in each region (ignoring how well the actual players filled it), and then outputted some statistics for every turn prior to that. The goal was to find, given certain indicators about the controlled space, what the statistically likely endgame looks like.

I never came up with anything smarter than a simple, very approximate, linear model. The difference in endgame moves after separation is roughly equal to K1 * (player 1 fillable squares - player 2 fillable squares) + K2 * (player 1 sum of edges - player 2 sum of edges) + K3 * (irrelevant factor). "Fillable squares" is roughly 2*min(red_count, black_count) plus/minus whatever adjustment for starting/ending squares. "sum of edges" is the number of neighbors in the region. irrelevant factor was nodes that are likely to become articulation vertices. After fitting the linear model on ~12000 of the games played by top-100 players with a quick and dirty perl script (model1.pl... did I remember to commit that? I'll check) I found K1 to be about 0.050, K2 about 0.150, and K3 less than 0.009. Hence I consider the third factor pretty much irrelevant. I use integer scores, so I multiplied through by 1000 and that was my heuristic before separation, with 10000*(difference of fillable area) as the heuristic after separation.

I was kind of surprised that the number of edges (which was about three times higher) had about three times more weight than the number of squares, but it's likely that it's a peculiarity of the least squares estimation as the two are highly correlated, obviously. I wanted to do some more statistical stuff with board evaluation but I didn't really have time. The model is pretty sketchy, to be honest... the graph of the raw data is a huge barely correlated blob. But picking numbers based on data is a lot better than picking them randomly.

[psb217]

I never came up with anything smarter than a simple, very approximate, linear model. The difference in endgame moves after separation is roughly equal to K1 * (player 1 fillable squares - player 2 fillable squares) + K2 * (player 1 sum of edges - player 2 sum of edges) + K3 * (irrelevant factor).... I found K1 to be about 0.050, K2 about 0.150, and K3 less than 0.009.

Interestingly enough, I added an ad-hoc fudge factor to my edge count measure, which was approximately 0.25 * (dominated vertex count). Surprisingly close to your 3-to-1 relative weighting between edge count and vertex count.

[luv2run]

I also weighted the squares, but surprisingly did not see much difference in ranking before and after doing so.
I gave each square a name:
DEADEND = surrounded on 3 sides by walls
TUNNEL = surrounded by walls on 2 opposite sides
CORNER = surrounded by walls on 2 adjacent sides
TRI = a wall on only one side
QUAD = no walls on any side
Scores:
DEADEND: 0.01 because you can only ever use one of these, so an area with 99 of them is no better than an area with 1.
TUNNEL: 1 because once you go through, you can't come back unless there's a tunnel back.
CORNER: 2 good square to use usually.
TRI: 2.5
QUAD: 3

Very ad-hoc but the scores seemed logical to me.

[a1k0n]

Actually you'd need to multiply the edges by 3, not by 0.25... The edges totally dominate the heuristic value. Dunno why, but it seems to work. It definitely keeps it from cluttering up its own space though.