BGonline.org Forums

The next major revolution in backgammon bots

Posted By: Timothy Chow
Date: Thursday, 10 May 2012, at 11:33 p.m.

In Response To: The next major revolution in backgammon bots (Frank Berger)

It's really solved.

TSP is NP-complete. However, just because a problem is NP-complete doesn't mean that brute force is the only way we know how to solve it exactly. People have developed lots of tricks for reducing the search space. If you set your mind to it, you can probably devise a pathological instance that defeats all the tricks, but the tricks are often very effective on problems that actually arise in the real world (and that haven't been specially designed to defeat the algorithm).

The TSP happens to be one of the NP-complete problems for which a ton of highly effective tricks have been developed.

Messages In This Thread

• The next major revolution in backgammon bots
  Timothy Chow -- Wednesday, 9 May 2012, at 12:02 a.m.
  • The next major revolution in backgammon bots
    RobertFontaine -- Wednesday, 9 May 2012, at 12:12 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 12:39 a.m.
      • The next major revolution in backgammon bots
        eXtreme Gammon -- Wednesday, 9 May 2012, at 1:56 a.m.
        • The next major revolution in backgammon bots
          Chuck Bower -- Wednesday, 9 May 2012, at 4:53 p.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Wednesday, 9 May 2012, at 5:07 p.m.
          • The next major revolution in backgammon bots
            eXtreme Gammon -- Wednesday, 9 May 2012, at 5:25 p.m.
          • The next major revolution in backgammon bots
            Frank Berger -- Wednesday, 9 May 2012, at 9:07 p.m.
        • The next major revolution in backgammon bots
          Timothy Chow -- Wednesday, 9 May 2012, at 5:40 p.m.
    • The next major revolution in backgammon bots
      Jason Lee -- Wednesday, 9 May 2012, at 12:57 a.m.
      • The next major revolution in backgammon bots
        RobertFontaine -- Wednesday, 9 May 2012, at 1:03 a.m.
        • For example 42P-43 *NM*
          RobertFontaine -- Wednesday, 9 May 2012, at 1:08 a.m.
        • The next major revolution in backgammon bots
          Stick -- Wednesday, 9 May 2012, at 1:54 a.m.
  • The next major revolution in backgammon bots
    Bob Koca -- Wednesday, 9 May 2012, at 2:01 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 5:22 p.m.
    • The next major revolution in backgammon bots
      Frank Berger -- Wednesday, 9 May 2012, at 8:59 p.m.
  • The next major revolution in backgammon bots
    Steve Mellen -- Wednesday, 9 May 2012, at 2:12 a.m.
    • The next major revolution in backgammon bots
      Stick -- Wednesday, 9 May 2012, at 2:20 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 5:27 p.m.
    • The next major revolution in backgammon bots
      Frank Berger -- Wednesday, 9 May 2012, at 8:55 p.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Wednesday, 9 May 2012, at 9:58 p.m.
      • The next major revolution in backgammon bots
        Timothy Chow -- Wednesday, 9 May 2012, at 11:52 p.m.
        • The next major revolution in backgammon bots
          Frank Berger -- Thursday, 10 May 2012, at 8:24 p.m.
          • The next major revolution in backgammon bots
            Timothy Chow -- Thursday, 10 May 2012, at 11:33 p.m.
            • The next major revolution in backgammon bots
              Jason Lee -- Friday, 11 May 2012, at 1:29 a.m.
            • The next major revolution in backgammon bots
              Frank Berger -- Friday, 11 May 2012, at 6:02 a.m.
            • The next major revolution in backgammon bots
              Sam Pottle -- Thursday, 17 May 2012, at 5:44 a.m.
              • The next major revolution in backgammon bots
                Timothy Chow -- Friday, 18 May 2012, at 12:01 a.m.
                • The next major revolution in backgammon bots
                  Snowie's Revenge -- Friday, 18 May 2012, at 12:45 a.m.
              • The next major revolution in backgammon bots
                Bob Koca -- Friday, 18 May 2012, at 1:27 a.m.
                • OT: Practical consequences of P = NP
                  Timothy Chow -- Saturday, 19 May 2012, at 9:31 p.m.
  • The next major revolution in backgammon bots
    Stein Kulseth -- Wednesday, 9 May 2012, at 10:11 a.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Wednesday, 9 May 2012, at 5:29 p.m.
  • The next major revolution in backgammon bots
    Jake Jacobs -- Thursday, 10 May 2012, at 5:59 a.m.
  • Degree of Difficulty Evaluation
    Perry Gartner -- Thursday, 10 May 2012, at 11:16 a.m.
    • Degree of Difficulty Evaluation
      Timothy Chow -- Thursday, 10 May 2012, at 12:06 p.m.
    • Degree of Difficulty Evaluation
      6stones -- Thursday, 10 May 2012, at 10:30 p.m.
    • Degree of Difficulty Evaluation
      Snowie's Revenge -- Friday, 18 May 2012, at 1:15 a.m.
  • The next major revolution in backgammon bots
    Phil Simborg -- Thursday, 10 May 2012, at 1:37 p.m.
    • Spacial Temporal Reasoning As the Crow flies *NM*
      Mr Majestyk -- Thursday, 10 May 2012, at 2:59 p.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Thursday, 10 May 2012, at 3:47 p.m.
      • The next major revolution in backgammon bots
        Phil Simborg -- Thursday, 10 May 2012, at 7:23 p.m.
        • SPAM!! *NM*
          mtuhtan -- Thursday, 10 May 2012, at 8:53 p.m.
        • The next major revolution in backgammon bots
          rew -- Friday, 11 May 2012, at 10:09 a.m.
        • The next major revolution in backgammon bots
          higonefive -- Wednesday, 16 May 2012, at 5:45 p.m.
      • The next major revolution in backgammon bots
        6stones -- Thursday, 10 May 2012, at 9:02 p.m.
  • The next major revolution in backgammon bots
    Rico -- Friday, 11 May 2012, at 3:41 p.m.
  • The next major revolution in backgammon bots
    Michael Petch -- Tuesday, 22 May 2012, at 3:59 a.m.
    • The next major revolution in backgammon bots
      Stick -- Tuesday, 22 May 2012, at 4:07 a.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Tuesday, 22 May 2012, at 4:17 a.m.
        • The next major revolution in backgammon bots
          Michael Petch -- Tuesday, 22 May 2012, at 4:20 a.m.
        • The next major revolution in backgammon bots
          Stick -- Tuesday, 22 May 2012, at 4:23 a.m.
          • The next major revolution in backgammon bots
            Casper van der Tak -- Tuesday, 22 May 2012, at 4:41 a.m.
            • The next major revolution in backgammon bots
              Frank Berger -- Tuesday, 22 May 2012, at 5:36 p.m.
              • The next major revolution in backgammon bots
                Stick -- Tuesday, 22 May 2012, at 7:02 p.m.
                • The next major revolution in backgammon bots
                  Frank Berger -- Tuesday, 22 May 2012, at 8:18 p.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Tuesday, 22 May 2012, at 5:12 a.m.
            • The next major revolution in backgammon bots
              Pilgrim -- Tuesday, 22 May 2012, at 7:49 a.m.
              • The next major revolution in backgammon bots
                Michael Petch -- Tuesday, 22 May 2012, at 8:05 a.m.
        • The next major revolution in backgammon bots
          Stick -- Tuesday, 22 May 2012, at 5:13 a.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Tuesday, 22 May 2012, at 5:28 a.m.
            • The next major revolution in backgammon bots
              Stick -- Tuesday, 22 May 2012, at 5:30 a.m.
            • The next major revolution in backgammon bots
              Casper van der Tak -- Tuesday, 22 May 2012, at 6:57 a.m.
              • The next major revolution in backgammon bots
                Michael Petch -- Tuesday, 22 May 2012, at 7:23 a.m.
                • Luck? Opening rolls?
                  mtuhtan -- Tuesday, 22 May 2012, at 7:36 a.m.
                  • Luck? Opening rolls?
                    Michael Petch -- Tuesday, 22 May 2012, at 8:01 a.m.
                    • Luck? Opening rolls?
                      mtuhtan -- Tuesday, 22 May 2012, at 8:20 a.m.
                      • Luck? Opening rolls?
                        Maik Stiebler -- Tuesday, 22 May 2012, at 8:38 a.m.
                • The next major revolution in backgammon bots
                  Casper van der Tak -- Tuesday, 22 May 2012, at 10:18 a.m.
          • The next major revolution in backgammon bots
            Bob koca -- Wednesday, 23 May 2012, at 12:56 a.m.
        • The next major revolution in backgammon bots
          steve -- Tuesday, 22 May 2012, at 5:57 a.m.
          • The next major revolution in backgammon bots
            Michael Petch -- Tuesday, 22 May 2012, at 6:01 a.m.
    • The next major revolution in backgammon bots
      BenF -- Tuesday, 22 May 2012, at 6:32 a.m.
    • The next major revolution in backgammon bots
      Matt Cohn-Geier -- Tuesday, 22 May 2012, at 8:31 a.m.
      • The next major revolution in backgammon bots
        Stick -- Tuesday, 22 May 2012, at 9:04 a.m.
    • The next major revolution in backgammon bots
      Sam Pottle -- Tuesday, 22 May 2012, at 9:23 a.m.
      • The next major revolution in backgammon bots +1
        Daniel Murphy -- Tuesday, 22 May 2012, at 2:21 p.m.
        • echo echo
          happyjuggler0 -- Tuesday, 22 May 2012, at 3:39 p.m.
    • The next major revolution in backgammon bots
      Christian Munk-Christensen -- Tuesday, 22 May 2012, at 11:22 a.m.
      • The next major revolution in backgammon bots
        mamabear -- Tuesday, 22 May 2012, at 7:03 p.m.
    • The next major revolution in backgammon bots
      higonefive -- Tuesday, 22 May 2012, at 1:31 p.m.
      • The next major revolution in backgammon bots
        mamabear -- Tuesday, 22 May 2012, at 7:21 p.m.
    • The next major revolution in backgammon bots
      neilkaz -- Tuesday, 22 May 2012, at 1:38 p.m.
      • You say you want a revolution....
        David Rennie -- Tuesday, 22 May 2012, at 2:22 p.m.
        • You say you want a revolution....
          Casper van der Tak -- Tuesday, 22 May 2012, at 4:11 p.m.
          • You say you want a revolution....
            David Rennie -- Tuesday, 22 May 2012, at 7:31 p.m.
            • You say you want a revolution....
              Casper van der Tak -- Wednesday, 23 May 2012, at 12:30 a.m.
    • The next major revolution in backgammon bots
      Mr Majestyk -- Tuesday, 22 May 2012, at 3:02 p.m.
    • The next major revolution in backgammon bots
      Timothy Chow -- Tuesday, 22 May 2012, at 3:45 p.m.
      • The next major revolution in backgammon bots
        higonefive -- Tuesday, 22 May 2012, at 5:28 p.m.
      • The next major revolution in backgammon bots
        David Rennie -- Tuesday, 22 May 2012, at 6:53 p.m.
        • The next major revolution in backgammon bots
          Timothy Chow -- Tuesday, 22 May 2012, at 10:56 p.m.
    • Home for this new bot
      mamabear -- Tuesday, 22 May 2012, at 7:04 p.m.
    • Late April Fools' Day...
      Michael Petch -- Wednesday, 23 May 2012, at 2:29 a.m.
      • Late April Fools' Day...
        happyjuggler0 -- Wednesday, 23 May 2012, at 2:50 p.m.
      • Late April Fools' Day...
        Timothy Chow -- Wednesday, 23 May 2012, at 3:14 p.m.
        • Late April Fools' Day...
          Frank Berger -- Wednesday, 23 May 2012, at 6:32 p.m.
          • Late April Fools' Day...
            Stick -- Wednesday, 23 May 2012, at 7:05 p.m.
            • Late April Fools' Day...
              Tom Keith -- Wednesday, 23 May 2012, at 9:01 p.m.
              • Late April Fools' Day...
                Bob koca -- Wednesday, 23 May 2012, at 9:06 p.m.
                • Late April Fools' Day...
                  Tom Keith -- Wednesday, 23 May 2012, at 9:10 p.m.
                  • Late April Fools' Day...
                    Stick -- Wednesday, 23 May 2012, at 9:24 p.m.
                    • Late April Fools' Day...
                      Timothy Chow -- Wednesday, 23 May 2012, at 9:35 p.m.
                      • Late April Fools' Day...
                        Casper van der Tak -- Thursday, 24 May 2012, at 5:05 a.m.
                        • Late April Fools' Day...
                          Henrik Bukkjaer -- Thursday, 24 May 2012, at 1:11 p.m.
                          • Late April Fools' Day...
                            Henrik Bukkjaer -- Thursday, 24 May 2012, at 1:47 p.m.
    • The next major revolution in backgammon bots
      leobueno -- Sunday, 11 January 2015, at 6:42 p.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Sunday, 11 January 2015, at 7:03 p.m.
        • The next major revolution in backgammon bots
          Bob Koca -- Monday, 12 January 2015, at 12:17 a.m.
    • The next major revolution in backgammon bots
      Dmitriy Obukhov -- Monday, 12 January 2015, at 1:49 a.m.
      • The next major revolution in backgammon bots
        Michael Petch -- Monday, 12 January 2015, at 2:53 a.m.