Hoping for lots of discussion after Friday

[Maxime81]

[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]

[barank]

[dutchflyboy]

[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]

[psb217]

[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.