Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualHodgman

Posted 03 September 2012 - 12:34 AM

If we skip past how you actually get there and focus on the end result -- we're talking about making a black box where the input is the state of a chess board, and the output is a chess move that is valid for that board-state.

We know that the number of chessboard states is bounded (somewhere between 10^43 and 10^47), and we can build algorithms that choose moves as well as a grandmaster (see IBM v Kasparov).
So in theory, if you iterated through all of those valid board-states and used these algorithms to pick the best move for each one, you could build a huge database that is a "solution to chess" -- this is ideally what your NN is trying to emulate. Each entry in this theoretical solution table has a 256bit key and a 12bit value. The total table size is at least 297539770599541952833533287048 petabytes.

Instead of a table, you could also encode the exact same data as a hugely complex linear equation (which is all that a NN is). If your equation encoded the full table without errors, it would probably require similar storage to the above table. If your equation only approximated the table instead of representing it exactly, then your NN will be smaller, but won't always output a valid or 'good' move.
Whenever the approximated equation produces an invalid move, you've got to modify the equation (via NN training techniques) and try again, and repeat until it does produce a valid move (even if it's not very good). If the internals of the NN aren't big enough to map the entire state-space of chess (billions of petabytes?), then this retraining will necessarilly make it 'forget' some information and produce worse answers to other board-states.

As Dave said, when asking "given this 256bit input, what 12-bit output move should I make?", getting fuzzy/general/"near enough" outputs isn't very useful, which is all that a realistically sized NN can produce for this question.
NN's might be useful for smaller questions, such as what kind of algorithm would be ideal for choosing the next move, or classifying whether you're in the early/mid/late game, or determining whether the 'white' player on a specific board-state is in an aggressive stance or not, or looking at a defensive pattern and choosing which type of unit is the best to attack it, or selecting a suitable opening gambit from a playbook, etc...

#6Hodgman

Posted 03 September 2012 - 12:29 AM

If we skip past how you actually get there and focus on the end result -- we're talking about making a black box where the input is the state of a chess board, and the output is a chess move that is valid for that board-state.

We know that the number of chessboard states is bounded (somewhere between 10^43 and 10^47), and we can build algorithms that choose moves as well as a grandmaster (see IBM v Kasparov).
So in theory, if you iterated through all of those valid board-states and used these algorithms to pick the best move for each one, you could build a huge database that is a "solution to chess" -- this is ideally what your NN is trying to emulate. Each entry in this theoretical solution table has a 256bit key and a 12bit value. The total table size is at least 297539770599541952833533287048 petabytes.

Instead of a table, you could also encode the exact same data as a hugely complex linear equation (which is all that a NN is). If your equation encoded the full table without errors, it would probably require similar storage to the above table. If your equation only approximated the table instead of representing it exactly, then your NN will be smaller, but won't always output a valid or 'good' move.
Whenever the approximated equation produces invalid move, you've got to modify the equation (via NN training techniques) and try again, and repeat until it does produce a valid move (even if it's not very good). If the internals of the NN aren't big enough to map the entire state-space of chess (billions of petabytes?), then this retraining will necessarilly make it 'forget' some information and produce worse answers to other board-states.

As Dave said, when asking "given this 256bit input, what 12-bit output move should I make?", getting fuzzy/general/"near enough" outputs isn't very useful, which is all that a realistically sized NN can produce for this question.
NN's might be useful for smaller questions, such as what kind of algorithm would be ideal for choosing the next move, or classifying whether you're in the early/mid/late game, or determining whether a the 'white' player on a specific board-state is in an aggressive stance or not, or looking at a defensive pattern and choosing which type of unit is the best to attack it, or selecting a suitable opening gambit from a playbook, etc...

#5Hodgman

Posted 03 September 2012 - 12:27 AM

If we skip past how you actually get there and focus on the end result -- we're talking about making a black box where the input is the state of a chess board, and the output is a chess move that is valid for that board-state.

We know that the number of chessboard states is bounded (somewhere between 10^43 and 10^47), and we can build algorithms that choose moves as well as a grandmaster (see IBM v Kasparov).
So in theory, if you iterated through all of those valid board-states and used these algorithms to pick the best move for each one, you could build a huge database that is a "solution to chess" -- this is ideally what your NN is trying to emulate. Each entry in this theoretical solution table has a 256bit key and a 12bit value. The total table size is at least 297539770599541952833533287048 petabytes.

Instead of a table, you could also encode the exact same data as a hugely complex linear equation (which is all that a NN is). If your equation encoded the full table without errors, it would probably require even more storage than the above table does. If your equation only approximated the table instead of representing it exactly, then your NN will be smaller, but won't always output a valid or 'good' move.
Whenever the approximated equation produces invalid move, you've got to modify the equation (via NN training techniques) and try again, and repeat until it does produce a valid move (even if it's not very good). If the internals of the NN aren't big enough to map the entire state-space of chess (billions of petabytes?), then this retraining will necessarilly make it 'forget' some information and produce worse answers to other board-states.

As Dave said, when asking "given this 256bit input, what 12-bit output move should I make?", getting fuzzy/general/"near enough" outputs isn't very useful, which is all that a realistically sized NN can produce for this question.
NN's might be useful for smaller questions, such as what kind of algorithm would be ideal for choosing the next move, or classifying whether you're in the early/mid/late game, or determining whether a the 'white' player on a specific board-state is in an aggressive stance or not, or looking at a defensive pattern and choosing which type of unit is the best to attack it, or selecting a suitable opening gambit from a playbook, etc...

#4Hodgman

Posted 03 September 2012 - 12:23 AM

If we skip past how you actually get there and focus on the end result -- we've got a machine where the input is the state of a chess board, and the output is a chess move that is valid for that board-state.
We know that the number of board-states is bounded (somewhere between 10^43 and 10^47), and we can build algorithms that choose moves as well as a grandmaster.
So in theory, if you iterated through all of those valid board-states and used these algorithms to pick the best move, you could build a huge database of a "solution to chess" -- this is ideally what your NN is trying to emulate. Each entry in this table has a 256bit key and a 12bit value. The total table size is at least 297539770599541952833533287048 petabytes.

Instead of a table, you could also encode the exact same data as a hugely complex linear equation (which is all that a NN is). If your equation encoded the full table without errors, it would probably require even more storage than the above table does. If your equation only approximated the table instead of representing it exactly, then your NN will be smaller, but won't always output a valid or 'good' move.
Whenever the approximated equation produces invalid move, you've got to modify the equation (via NN training techniques) and try again, and repeat until it does produce a valid move (even if it's not very good). If the internals of the NN aren't big enough to map the entire state-space of chess (billions of petabytes?), then this retraining will necessarilly make it 'forget' some information and produce worse answers to other board-states.

As Dave said, when asking "given this 256bit input, what 12-bit output move should I make?", getting fuzzy/general/"near enough" outputs isn't very useful, which is all that a realistically sized NN can produce for this question.
NN's might be useful for smaller questions, such as what kind of algorithm would be ideal for choosing the next move, or classifying whether you're in the early/mid/late game, or determining whether a the 'white' player on a specific board-state is in an aggressive stance or not, or looking at a defensive pattern and choosing which type of unit is the best to attack it, or selecting a suitable opening gambit from a playbook, etc...

#3Hodgman

Posted 03 September 2012 - 12:15 AM

If we skip past how you actually get there and focus on the end result -- we've got a machine where the input is the state of a chess board, and the output is a chess move that is valid for that board.
We know that the number of boards is bounded (somewhere between 10^43 and 10^47), and we can build algorithms that choose moves as well as a grandmaster.
So in theory, if you iterated through all of those valid boards and used these algorithms to pick the best move, you could build a huge database of a "solution to chess". Each entry has a 256bit key and a 12bit value. The total table size is at least 297539770599541952833533287048 petabytes.

Instead of a table, you could also encode the exact same data in a NN (which is really just representing it as a huge linear equation). If your linear equation encoded the full table without errors, it would necessarily be larger than the above size. If your linear equation only approximated the table instead of representing it exactly, then your NN will be smaller, but won't always output a valid or 'good' move.

As Dave said, when asking "given this 256bit input, what 12-bit output move should I make?", getting fuzzy/general/"near enough" outputs isn't very useful, which is all that a realistically sized NN can produce for this question.
NN's might be useful for smaller questions, such as what kind of algorithm would be ideal for choosing the next move, or classifying whether you're in the early/mid/late game, or determining whether a the 'white' player on a specific board is in an aggressive stance or not, or looking at a defensive pattern and choosing which type of unit is the best to attack it, or selecting a suitable opening gambit from a playbook, etc...

#2Hodgman

Posted 03 September 2012 - 12:14 AM

If we skip past how you actually get there and focus on the end result -- we've got a machine where the input is the state of a chess board, and the output is a chess move that is valid for that board.
We know that the number of boards is bounded (somewhere between 10^43 and 10^47), and we can build algorithms that choose moves as well as a grandmaster.
So in theory, if you iterated through all of those valid boards and used these algorithms to pick the best move, you could build a huge database of a "solution to chess". Each entry has a 256bit key and a 12bit value. The total table size is at least 297539770599541952833533287048 petabytes.

Instead of a table, you could also encode the exact same data in a NN (which is really just representing it as a collection of linear equations). If your NN encoded the full table without errors, it would necessarily be larger than the above size. If your linear equations only approximated the table instead of representing it exactly, then your NN will be smaller, but won't always output a valid or 'good' move.

As Dave said, when asking "given this 256bit input, what 12-bit output move should I make?", getting fuzzy/general/"near enough" outputs isn't very useful, which is all that a realistically sized NN can produce for this question.
NN's might be useful for smaller questions, such as what kind of algorithm would be ideal for choosing the next move, or classifying whether you're in the early/mid/late game, or determining whether a the 'white' player on a specific board is in an aggressive stance or not, or looking at a defensive pattern and choosing which type of unit is the best to attack it, or selecting a suitable opening gambit from a playbook, etc...

PARTNERS