4 ms·
"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the inpu
by lozenge 8y ago
"By contrast, the chess problem must be solved by brute force, and the number of steps this takes increases in proportion to an exponential function of the input. "
What is this input? Board size?
- cluoma 8y agoUsually it would be number of legal moves. Of course this would also change throughout the game as pieces are removed.
- philipov 8y agoThe number of legal moves is an intermediate calculation. The input is the initial game state, and the output is usually the number of possible final game states.
- philipov 8y agoIt is board size for Go, because the starting condition is an empty board. For chess, I would expect the complexity to also be a function of the number of pieces, and possibly the types of pieces.
- adrianN 8y agoIf you generalize chess to an N*N board, it becomes PSPACE complete to decide which player has a winning strategy: https://www.sciencedirect.com/science/article/pii/0022000083900302?via%3Dihub https://www.sciencedirect.com/science/article/pii/0022000083...
- boomlinde 8y agoI think that the number of positions that need to be considered for a brute force exhaustive search are roughly proportional to an exponential function of the number of moves made, so the statement holds true for that. In reality, the number of possible moves is not constant and depends on the current position.