[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Survival Mode

It is currently Thu Apr 27, 2017 4:45 pm Advanced search

Survival Mode

Share and discuss ideas for your entries here.

Re: Survival Mode

Postby BlackWave » Sat Feb 27, 2010 2:25 pm

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.
BlackWave
Cadet
 
Posts: 5
Joined: Mon Feb 08, 2010 2:28 pm

Re: Survival Mode

Postby Fritzlein » Tue Mar 02, 2010 4:31 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

Re: Survival Mode

Postby barxool » Tue Mar 02, 2010 10:32 pm

I request it !
barxool
Lieutenant
 
Posts: 13
Joined: Wed Feb 10, 2010 9:22 pm

Re: Survival Mode

Postby luv2run » Tue Mar 02, 2010 11:49 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.
luv2run
Lieutenant
 
Posts: 11
Joined: Sun Feb 28, 2010 4:57 pm

Re: Survival Mode

Postby Fritzlein » Wed Mar 03, 2010 12:22 am

Rats, you called my bluff, barxool. Now I'll have to see whether I can understand Majerech's proof. :shock: 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.
Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Survival Mode

Postby a1k0n » Wed Mar 03, 2010 12:38 am

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

Re: Survival Mode

Postby Fritzlein » Wed Mar 03, 2010 1:51 am

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

Re: Survival Mode

Postby Fritzlein » Wed Mar 03, 2010 7:30 am

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

Re: Survival Mode

Postby Fritzlein » Wed Mar 03, 2010 5:56 pm

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

Re: Survival Mode

Postby Hippo » Wed Mar 03, 2010 7:04 pm

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

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron