It is currently Mon Mar 25, 2019 10:53 pm Advanced search

49 posts
• Page **4** of **5** • 1, 2, 3, **4**, 5

I have an algorithm to calculate the number of accessible squares from my position, and I deacrease with the number of dead ends and "only paths" to dead ends.

It can be done about 20.000 times per second.

My "unconnected with the opponent" algorithm is: start with depth 1: start a list with 4 positions N E S W and make the move in board compute the number above. if I lose in any just delete the position. start to original position after each attempt.

for each iteration, append 4 new strings to list ending in NESW each. ( I use a list of lists to make things faster).

after each iteration I compute the max, so I get the best possible path with depth "number of iterations". To untie, I choose the path that makes less walls (to force the wall hugger, that works well). Usually it can see ahead 9/10 depth in one second.

Not perfect, but works very well.

It can be done about 20.000 times per second.

My "unconnected with the opponent" algorithm is: start with depth 1: start a list with 4 positions N E S W and make the move in board compute the number above. if I lose in any just delete the position. start to original position after each attempt.

for each iteration, append 4 new strings to list ending in NESW each. ( I use a list of lists to make things faster).

after each iteration I compute the max, so I get the best possible path with depth "number of iterations". To untie, I choose the path that makes less walls (to force the wall hugger, that works well). Usually it can see ahead 9/10 depth in one second.

Not perfect, but works very well.

- BlackWave
- Cadet
**Posts:**5**Joined:**Mon Feb 08, 2010 2:28 pm

Vladan Majerech, a Czech graph theorist, has sent me the sketch of a proof that an algorithm that can play Tron survival mode optimally can also be used to solve 3SAT via a polynomial reduction. Therefore Tron survival mode is NP-hard. If at least one person requests it, I will try to reproduce his proof here in terms intelligible to the mathematical layman.

- Fritzlein
- Colonel
**Posts:**81**Joined:**Thu Feb 18, 2010 9:20 pm

If you could sketch the proof, that would be awesome.

As I asked in my other thread (which was locked, even though it's a bit of a different topic than this one)...did anyone *solve* the longest-paths problem?

Sure it's NP-complete, but on a dense 15x15 graph I'm sure it could be solved with a smart algorithm, and maybe on a slightly bigger one too.

As I asked in my other thread (which was locked, even though it's a bit of a different topic than this one)...did anyone *solve* the longest-paths problem?

Sure it's NP-complete, but on a dense 15x15 graph I'm sure it could be solved with a smart algorithm, and maybe on a slightly bigger one too.

- luv2run
- Lieutenant
**Posts:**11**Joined:**Sun Feb 28, 2010 4:57 pm

Rats, you called my bluff, barxool. Now I'll have to see whether I can understand Majerech's proof. I'll post here again when I have ironed out the details.

Luv2run, to answer your question smart-ass style, yes, I *solved* the longest path problem. The solution is to enumerate all possible paths and select the longest. Thus, any bot that exhaustively searches ahead will solve any endgame at some point when the territory is small enough or the bot thinks long enough. There were even non-searchers that found the longest path in a big chamber if the shape was easy enough.

Your question needs to be carefully quantified to be meaningful. To answer one form of it: I don't think that anyone in the competition had an algorithm to always find the longest path in half of a 15-by-16 board, regardless of the shape, in under one second. But a combination of tree-of-chambers, checkerboard upper bound, and other heuristics very rarely made errors in survival mode during the tournament. It's telling to see bots that played an excellent endgame on the small maps try to handle the large, cluttered maps on dhartmei's server and fall apart to varying degrees.

Luv2run, to answer your question smart-ass style, yes, I *solved* the longest path problem. The solution is to enumerate all possible paths and select the longest. Thus, any bot that exhaustively searches ahead will solve any endgame at some point when the territory is small enough or the bot thinks long enough. There were even non-searchers that found the longest path in a big chamber if the shape was easy enough.

Your question needs to be carefully quantified to be meaningful. To answer one form of it: I don't think that anyone in the competition had an algorithm to always find the longest path in half of a 15-by-16 board, regardless of the shape, in under one second. But a combination of tree-of-chambers, checkerboard upper bound, and other heuristics very rarely made errors in survival mode during the tournament. It's telling to see bots that played an excellent endgame on the small maps try to handle the large, cluttered maps on dhartmei's server and fall apart to varying degrees.

- Fritzlein
- Colonel
**Posts:**81**Joined:**Thu Feb 18, 2010 9:20 pm

Indeed. Janzert is definitely stronger than my entry on those gigantic cluttered maps. My endgame code isn't very good, TBH. It has a bug where a deeper search will sometimes return a worse result than an earlier search had found, so something is clearly messed up with it.

- a1k0n
- Colonel
**Posts:**90**Joined:**Fri Feb 12, 2010 3:51 am

The proof Fritzlein presents here is based on fact Hamiltonian path is NPComplete even for planar undirected graph with vertices of degree at most 3.

I have presented another continuation, but his scaling vertices to chambers is very nice trick to finish the proof.

I am really not sure where the reduction from SAT to Hamiltonian cycle in directed bipartite planar graph with veritces in one partite having indegree 2 and outdegree 1 and vertices in the other have indegree 1 and outdegree 2 originates. Remaining reductions (undirecting, cycle->path step) are easy standard tricks.

It seems to me I have read the proof in a book with name simillar to "Graph Theory" from Slovak author Plesnik, but that was around 18 years ago.

I must look if I find the book somewhere if it was there and if the further pointer to the author of the proof is there.

So may see the transformation from (3) SAT to planar undirected graph with vertices of degree at most 3 in the Fritzlein proof.

(I hope it will be OK. So far I could say he was inspired by my "zipped sketch of the proof" and I am wiling to see how this would end.)

Vladan Majerech

P.S.: Not exactly ... the clauses part used chamber with higher degree. It may be simplification to the vertex->chamber translation.

Finally: http://www.aya.or.jp/~babalabo/DownLoad ... 92-196.pdf Plesnik was original author of the proof I know. (Simillar proof http://www.cs.princeton.edu/courses/arc ... tonian.pdf was probably inspiration).

... oh yes, it is cited as [3].

I have presented another continuation, but his scaling vertices to chambers is very nice trick to finish the proof.

I am really not sure where the reduction from SAT to Hamiltonian cycle in directed bipartite planar graph with veritces in one partite having indegree 2 and outdegree 1 and vertices in the other have indegree 1 and outdegree 2 originates. Remaining reductions (undirecting, cycle->path step) are easy standard tricks.

It seems to me I have read the proof in a book with name simillar to "Graph Theory" from Slovak author Plesnik, but that was around 18 years ago.

I must look if I find the book somewhere if it was there and if the further pointer to the author of the proof is there.

So may see the transformation from (3) SAT to planar undirected graph with vertices of degree at most 3 in the Fritzlein proof.

(I hope it will be OK. So far I could say he was inspired by my "zipped sketch of the proof" and I am wiling to see how this would end.)

Vladan Majerech

P.S.: Not exactly ... the clauses part used chamber with higher degree. It may be simplification to the vertex->chamber translation.

Finally: http://www.aya.or.jp/~babalabo/DownLoad ... 92-196.pdf Plesnik was original author of the proof I know. (Simillar proof http://www.cs.princeton.edu/courses/arc ... tonian.pdf was probably inspiration).

... oh yes, it is cited as [3].

Last edited by Hippo on Wed Mar 03, 2010 10:13 pm, edited 2 times in total.

- Hippo
- Lieutenant-Colonel
**Posts:**49**Joined:**Wed Mar 03, 2010 6:42 pm

49 posts
• Page **4** of **5** • 1, 2, 3, **4**, 5

Users browsing this forum: No registered users and 1 guest