<story><title>Classic Nintendo Games Are NP-Hard (2012)</title><url>http://arxiv.org/abs/1203.1895</url></story><parent_chain><item><author>headcanon</author><text>Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how &amp;quot;enjoyably challenging&amp;quot; a game is. There&amp;#x27;s a reason these games are such classics, and I dont think its entirely because of their timing, polish, and marketing. Miyamoto&amp;#x27;s games always had that special &amp;quot;something&amp;quot; (opinion, I know), maybe this has something to do with it?</text></item></parent_chain><comment><author>JoshTriplett</author><text>Probably not formally, but I do tend to find that how much I enjoy a game correlates inversely with how easily I can imagine teaching a computer to play it.  Most of the time, if I start thinking &amp;quot;I could write an algorithm for this game&amp;quot;, I very quickly lose interest in playing it.&lt;p&gt;So, I enjoy games where I feel like I can recognize patterns that have some depth and complexity, that make me feel like I can develop some skill, that don&amp;#x27;t seem trivially teachable to a computer.</text></comment>
<story><title>Classic Nintendo Games Are NP-Hard (2012)</title><url>http://arxiv.org/abs/1203.1895</url></story><parent_chain><item><author>headcanon</author><text>Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how &amp;quot;enjoyably challenging&amp;quot; a game is. There&amp;#x27;s a reason these games are such classics, and I dont think its entirely because of their timing, polish, and marketing. Miyamoto&amp;#x27;s games always had that special &amp;quot;something&amp;quot; (opinion, I know), maybe this has something to do with it?</text></item></parent_chain><comment><author>CydeWeys</author><text>What NES games aren&amp;#x27;t NP-hard?  I don&amp;#x27;t think complexity class is useful for games analysis.</text></comment>