Hacker News Reader

pretty sure computing moves is in NP so probably yep

Nope, finite number of pieces and finite number of viable moves to check on each. Not sure what you're thinking of, but the entire concept of complexity class only applies if there is some axis of scaling (n-size chess board?).

I think you might be misunderstanding:

Yes the instance of chess is finite but the problem of computing moves is inherently in NP.

The key is that just because a problem is in NP it does't mean that its difficult to solve the instances with small parameters.

See the famous coloring, SAT, or any other equal NP problem...

When we talk about what class a problem belongs in, we have to define the problem with respect to some scaling axis. For example, coloring with K=3 colors is NP-complete with respect to N = # nodes in the graph, but not with fixed N and scaling K. But I think it would actually be an interesting and non-trivial exercise to define a variant of chess with a scaling axis such that computing a list of valid moves for one player is NP-complete. Just scaling board size won't do it. Any suggestions?

Sorry I think I was talking about a different thing. With depth as scaling axis it should be NP-complete, but not with depth=1 which is what was being talked about. My bad.

Reply on news.ycombinator.com