[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/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 - Is Warnsdorff's Algorithm useful?

It is currently Sat Jan 20, 2018 8:50 pm Advanced search

Is Warnsdorff's Algorithm useful?

Share and discuss ideas for your entries here.

Is Warnsdorff's Algorithm useful?

Postby blueiris » Mon Feb 08, 2010 2:27 pm

Has anyone looked into whether Warndsdorff's Algorithm (a heuristic for finding Knight's Tours) could be adapted to help solve the "longest connected path" subproblem of Tron?

blueiris
Cadet
 
Posts: 9
Joined: Sat Feb 06, 2010 8:53 am

Re: Is Warnsdorff's Algorithm useful?

Postby ebrahim » Tue Feb 09, 2010 8:33 am

But why, when you can do it by DFS?! It is doable on small maps. Actually I'm doing it :)
If you're going to use it as an evaluation function for minimax that's another story. DFS might be slow for that, but still i guess otherwise!
ebrahim
Lieutenant-Colonel
 
Posts: 49
Joined: Mon Feb 08, 2010 7:03 pm

Re: Is Warnsdorff's Algorithm useful?

Postby pekkakarj » Tue Feb 09, 2010 10:54 am

I think that calculating the immediate neighbors of each square is a good preprocessing step to do before using whatever search or evaluation you want to do. As I haven't written any code for that yet, my ideas are not very well formed.

But knowing which spots are bottlenecks with two neighbors or dead ends with only one can help guide your search. Perhaps some good ideas can come from Warnsdorff's Algorithm regarding this.

The most obvious thing that came to my mind is that any path can only end in at most one dead-end. This gives a formula for an upper bound for a path length. It is (free spots - dead ends + 1). This assumes the area does not have an opponent to mess things up for you.
pekkakarj
Cadet
 
Posts: 5
Joined: Sun Feb 07, 2010 3:05 pm

Re: Is Warnsdorff's Algorithm useful?

Postby ebrahim » Tue Feb 09, 2010 3:25 pm

ebrahim
Lieutenant-Colonel
 
Posts: 49
Joined: Mon Feb 08, 2010 7:03 pm

Re: Is Warnsdorff's Algorithm useful?

Postby a1k0n » Wed Feb 17, 2010 10:41 pm

I'll chime in with my two cents: yes, quite so. The application to tron is that, when doing a heuristic max-path-length greedy search, choose the node with the smallest degree so as to remove the smallest number of edges from the connected graph. This works quite well for a first approximation, but there are some other heuristic improvements which I feel give me a competitive edge at the moment :)
a1k0n
Colonel
 
Posts: 90
Joined: Fri Feb 12, 2010 3:51 am


Return to Strategy

Who is online

Users browsing this forum: No registered users and 2 guests

cron