New Game Dots And Polygons Is NP Hard 
Written by Mike James  
Saturday, 18 April 2020  
OK, new proofs that things are NP hard are so common that we have given up reporting on them, but this one  a new game from the Department of Mathematics and Computer Science at Eindhoven University of Technology  is fun. It's a generalization of the wellknown Dots and Boxes. It is true that given a task with even a moderately big search space it turns out to be NP hard  no great surprise there. This particular piece of research, however, introduces a variation on a Dots and Boxes to become Dots and Polygons. Not as catchy a name, but more interesting. If you have played Dots and Boxes you will know it as an irritating game that you can lose simply by not concentrating enough because it seems such a simple task. Given a regular grid of dots all you have to do is connect adjacent dots with a straight line and attempt to complete a square. As players take it in turns it has the feel of Nim, where each player tries hard not to leave a 3sided box for the next player to complete. The generalization Dots and Polygons is played on a set of points in the plane. Each player takes a turn at drawing a connection line that doesn't intersect any other point or any existing edges. The objective is to form a closed polygon and the overall winner is the one with the maximum area covered by polygons. Two variations on the game are Dots and Polygons and Holes, where polygons are allowed to contain other polygons, and Convex Dots and Polygons where they have to be convex. If you try the game you will quickly discover that the "no intersect" rule is a big part of the strategy in not leaving two sides that your opponent can connect. You can try all three versions out at: https://www.win.tue.nl/~kbuchin/proj/ruler/dotsandpolygons/ but notice that it only allows human against human. An interesting project would be to train a neural network to play the game as playing it needs spatial reasoning as well as logic  a sort of easier Go. The source code is also available. The key result of the research is that deciding if a win is possible in Dots and Polygons is NP hard  you can find the details in the paper, authored by Kevin Buchin, Irina Kostitsyna et al. If you are keen on such things then you might like the final theorem: Theorem 5. Let P be a set of n points in the plane in convex position. For n = 3, 5, 7 player R can score at least half of the area, for n = 4, 6 player B can score at least half of the area. The problem for n>7 is open.
More InformationKevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken, Jolan Rensen and Leo van Schooten https://www.win.tue.nl/~kbuchin/proj/ruler/dotsandpolygons/ Related ArticlesPancake flipping is hard  NP hard Rubik's Cube Is Hard  NP Hard Candy Crush Is Harder Than It Sounds  NP Hard Travelling Salesman  A Movie About P=NP To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@iprogrammer.info <ASIN:1871962439>


Last Updated ( Wednesday, 02 February 2022 ) 