Answers.Body: <p>Without question it possible to build a mechanical <a href="https://en.m.wikipedia.org/wiki/NAND_gate" rel="nofollow noreferrer">NAND gate</a>.</p>
  <p>Basic 1st year computer science tells us that any type of logic gates can be made by combining NAND gates.</p>
  <p>Lets assume unlimited money, so we can then assume size is not a limiting factor.</p>
  <p>We would need at least hundreds of thousands of these mechanical NAND gates, but practically we know a few of them would always break down. I can't think of a way to avoid this.</p>
  <p>(Most of the NAND gates would be used for the memory rather the CPU.)</p>
  <p>But due to non-fictional materials limitations there is a limit to how fast a mechanical logic gate can work, so the &quot;clock rates&quot; would likely be hours per cpu instruction rather then thousands of instructions per second.</p>
  <p><strong>Did you require the system to make more than one move a year?</strong></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-06T22:54:16.570Z
Answers.Text: The most complex actual mechanical devices are calculators purpose built for one task. Still the processing required for any chess engine algorithm would essentially require a CPU of some kind.
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-07T12:38:41.053Z
Answers.Text: @qwr is a Turing Machine a CPU?
Answers.UserDisplayName: Ian Ringrose
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-10T12:49:44.660Z
Answers.Text: No, it's a theoretical model of computing that can be physically built, and has been done so before, but is impractical in large amounts of calculation.
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-10T20:15:08.323Z
Answers.Text: @qwr the question says "possible" not "practical", so no requirement for a proof of a solution to show the solution is practical.
Answers.UserDisplayName: Ian Ringrose
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-10T21:30:32.253Z
Answers.Text: I don't have proof a Turing machine of gargantuan size is possible to build.
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-06T08:10:31.317Z
Answers.LastActivityDate: 2024-06-07T12:32:42.967Z
Answers.LastEditDate: 2024-06-07T12:32:42.967Z
Answers.UserDisplayName: Ian Ringrose
Answers.Body: <p>I would like to try answer this question even though I'm not an expert, because unlike other answerer/commenters, I think the best approach is not to build a general purpose computing device like a CPU and then executing a chess algorithm, but to design a single-purpose device only capable of one task (chess) with a built-in relatively simple algorithm. The closest real-life reference may be El Ajedrecista, which uses simple electric and mechanical technology and only plays an endgame with hard-wired logic, but then it was built in an era without the advanced knowledge of chess engines and algorithms of today. It's possible with algorithmic and engineering hindsight, a much better machine can be built without electronics.</p>
  <p>Here's an outline of what I think is possible. One way to use low tech to achieve more play strength might be to make a mechanical neural network. It will be small by today's neural network standards, and the parameters need to be trained elsewhere and hard-wired, but can be implemented with simpler components like gears and latches. For example the internal board representation as an 8x8 grid, where each square has mechanical switches than can be put into different positions to encode whether it's empty and what color/type of piece is there. A grid of gears lock onto the switches and rotate based on the switch positions, feeding the activation into the next layer of gears, and so on. This neural network will be rather large, but is presumably much more efficient and parallelizable than hand-crafted logical rules as in El Ajedrecista. Such a neural network can be a policy network that generates candidate moves directly (eg. the highest activation in the last layer is detected by a touch-based mechanism and translated into moves), or can be a value network that only evaluates a position and returns an analog value.</p>
  <p>Another approach is to somehow implement search mechanically. This is obviously harder since mechanical &quot;memory&quot; and processing speed is very limited, but not completely impossible if we only look a low depth and a small number of candidate moves (using the mechanical neural network to generate moves for example). At worst, even looking one move ahead with 2-3 possible moves each is better than nothing. To perform a search mechanically, there could be a stack of board representations (like small metal plates with switches as above) augmented with extra switches to encode candidate moves from the current position, and a numerical pointer to the future position in the stack to logically represent a search tree. A reader/execution head reads the plates and either generates more moves/positions using the policy network when there are blank plates available, or go through the tree to select the best move using the evaluation of the final leaf position (with the value network) using minmax algorithm by going up and down the stack as needed. This should hopefully be able to look at a couple dozen positions or a few moves ahead, and if the neural networks are any good, should be able to beat some beginners.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-06T23:55:56.207Z
Answers.Text: How would you train such a neural network? Backpropagation is just chain rule with dynamic programming, which comes down to a lot of matrix multiplies.
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-06T23:57:18.040Z
Answers.Text: @qwr Train it separately on a modern computer, just like any other neural network. Only the final parameters need to be hard-wired.
Answers.UserDisplayName: alices_and_bobs
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-06T23:58:12.713Z
Answers.Text: Oh I see. Mechanical, but with all the technology of today? Then what is the point?
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-07T00:02:57.987Z
Answers.Text: @qwr Modern technology and algorithms make it easier, but it's not like totally impossible for someone determined enough back then to figure it out (old mathematicians and inventors were pretty good without computers). If just proving the Turk was possible if given enough resources and hand-tuning effort isn't a good enough reason, then at least there can be practical applications today, for example to build a completely 3d-printed mechanical smart chess set that would presumably be a great conversation piece, and to apply the tech in other ways in extreme environments where electronics fail.
Answers.UserDisplayName: alices_and_bobs
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-06T23:42:53.080Z
Answers.LastActivityDate: 2024-06-06T23:42:53.080Z
Answers.UserDisplayName: alices_and_bobs
Answers.Body: <p>Expanding on @alices_and_bobs answer, one approach would be to create an actual mechanical model of the board directly, and perform some kind of stack based lookahead. Although some form of mechanical AI weightings could be used as mentioned elsewhere, I would propose a good old-fashioned tree search with pruning.  The model would be constructed such that each piece would be individually fixable so that it would be possible to &quot;unlock&quot; each piece on turn and iterate through all legal moves it could make. The board and pieces would not resemble an actual board and pieces but would be optimized for fast mechanical movement of the pieces themselves as well as detecting the current board state for position analysis. The actual movement of the pieces would be based on mechanical allowance - that is, the mechanism would attempt to move the piece in each direction but the piece would only be <em>able</em> to make legal moves.  As an example, the first order of allowance is that a piece can move into a square if it is not occupied. This would be the easiest to accomplish mechanically as an occupying piece would simply prevent another piece from occupying the square.  The next step would be to allow a piece to capture another. This could perhaps use some form of magnets such that pieces of the same color would repel while opposite colors would attract and thus allow the attacked piece to &quot;move aside&quot; and be captured.  There is also the encoding of the knight's move, which could perhaps be accomplished by something along the lines of the shapes of the pieces, for instance, perhaps normal pieces would have a cube shape and knights would be spherical and then able to roll or &quot;jump&quot; over another piece, but not stop there if the colors were the same due to magnetic repulsion. Or perhaps pieces would have slanted edges with mechanical grooves that only allowed knights to pass over. A knight's move would also be more complicated because it would not be able to stop at one of the interim squares so would have to somehow be pushed to continue along until it finished its move.   On the other hand, kings, and knights would have only a single move that could be made in any &quot;direction&quot;, while rooks, bishops, and queens would potentially have many for open ranks, files, and diagonals, so this would have to be mechanically accomodated as well.  Pawns would have an extra possible move the first time, but this would probably be the easiest special case to accomodate, as the board itself could be notched in a way that pawns could move one or two squares on their first move but that other pieces would not notice.  Likewise with capturing, some kind of grooves could be used to allow pawns to only capture diagonally and otherwise only move in a straight line.</p>
  <p>Now we come to the harder parts.  Castling can only occur once in the game, and only if the king and rook in question haven't moved.  It might be best to keep this in some external flip flop, which then acts to allow or prevent castling from taking place.  Promotion would require some extra logic to allow the different promotion types to be iterated through.  Things like the 50 move rule and draw by repeated positions would require external logic.  Disallowing moves when the king is in check unless it removes the check would also require some external logic.  All of this external logic would need to control some kind of &quot;master override&quot; which would apply to all or some squares and would slow the game down. However, stalemate and checkmate would be easy to detect.</p>
  <p>Once the mechanics had produced a new valid board position, some kind of evaluation function would need to be applied to get a relative status of the game.  This could be a completely analog value, and could be performed by any number of heuristics which directly imprinted the board state and did some kind of weighting, perhaps with springs.  This analog value would then be compared to the best value found so far, and if it improved it, the current move would be recorded as the best so far.  If the value was far enough below the current best it could prune the current search.</p>
  <p>This setup would work best with depth first recursion, as this would be simpler than breadth first.  In this mechanism it would only be necessary to keep a stack of moves which would be unwound, rather than needing to keep a stack of board states.  However, this would likely require limiting how many plys of lookahead were used based on worst case move time. The speed of a move would be limited by how fast a mechanical move could be made and the corresponding imprint and analysis to update the legal move overrides, as well as to generate the current point status for the purpose of determining if a better move had been found or an unpromising line pruned. Since the board itself is essentially analog it could be much faster than implementing the solution entirely in mechanical logic gates. For instance, it seems reasonable to assume that the machine could evaluate 10 moves per second, and it this rate it could consider its move and all possible counter-moves in under a minute.  However to consider its second possible move and all possible responses to that could take over 5 hours, although depending on how aggressive pruning was done it might be greatly reduced.  The machine would likely not play very strongly but could be passable as a form of entertainment, assuming that it is still the 1800s.  Also, while considering 10 moves per seconds is mechanically doable, it would likely be necessary to maintain the machine after each game to inspect it for wear and replace anything as needed to try to prevent it from breaking down during a game.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-07T14:50:03.710Z
Answers.LastActivityDate: 2024-06-07T14:50:03.710Z
Answers.UserDisplayName: Michael
Body: <p>We all know the Mechanical Turk was a dummy machine controlled by human players. However, given technology has progressed, it theoretically possible to build a purely mechanical (no modern electronics) automated chess set/chess machine that moves its own pieces and plays decently well? How might it be built, and what kinds of designs and technologies would be used to make the AI work?(Or if the Mechanical Turk was real, how would it work?)</p>
  <p>I'm not concerned about extra features like answering questions or edge cases like protecting itself from the human opponent playing illegal moves (like Napoleon) or violently attacking it/flipping the board. It just needs to be able to play normal chess.</p>
  <p>Edit: &quot;decent AI&quot; is by the standards of pre-modern times, doesn't have to be comparable to modern engines or strong human players. As long as it works without human player help, feel free to choose the user interface and form factor. It can be much bigger than the Turk if needed. If a relation between its size and rating can be established, that's even better.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-06T23:00:06.010Z
Comments.Text: This question is probably more suitable for a non-chess stack exchange. Mechanical is not feasible but electromechanical is.
Comments.UserDisplayName: qwr
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-06-07T12:37:29.970Z
Comments.Text: @qwr  The Turing Machine would like to disagree with you.
Comments.UserDisplayName: Ian Ringrose
Tags: <engines><history><human-versus-machine>
Title: Is a mechanical, Turk-like, purely mechanical self-moving chess set with decent AI possible?
ThreadText: # Is a mechanical, Turk-like, purely mechanical self-moving chess set with decent AI possible?
  
  (Asked by: username_0 on 2024-06-06)
  
  We all know the Mechanical Turk was a dummy machine controlled by human players. However, given technology has progressed, it theoretically possible to build a purely mechanical (no modern electronics) automated chess set/chess machine that moves its own pieces and plays decently well? How might it be built, and what kinds of designs and technologies would be used to make the AI work?(Or if the Mechanical Turk was real, how would it work?)
  
  I'm not concerned about extra features like answering questions or edge cases like protecting itself from the human opponent playing illegal moves (like Napoleon) or violently attacking it/flipping the board. It just needs to be able to play normal chess.
  
  Edit: "decent AI" is by the standards of pre-modern times, doesn't have to be comparable to modern engines or strong human players. As long as it works without human player help, feel free to choose the user interface and form factor. It can be much bigger than the Turk if needed. If a relation between its size and rating can be established, that's even better.
  
  **Tags:** engines, history, human-versus-machine
  
  > **Comments:**
  > **username_1**: This question is probably more suitable for a non-chess stack exchange. Mechanical is not feasible but electromechanical is.  
  > **username_2**: @username_1  The Turing Machine would like to disagree with you.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2024-06-06. Score: 2
  
  Without question it possible to build a mechanical [NAND gate](https://en.m.wikipedia.org/wiki/NAND_gate).
  
  Basic 1st year computer science tells us that any type of logic gates can be made by combining NAND gates.
  
  Lets assume unlimited money, so we can then assume size is not a limiting factor.
  
  We would need at least hundreds of thousands of these mechanical NAND gates, but practically we know a few of them would always break down. I can't think of a way to avoid this.
  
  (Most of the NAND gates would be used for the memory rather the CPU.)
  
  But due to non-fictional materials limitations there is a limit to how fast a mechanical logic gate can work, so the "clock rates" would likely be hours per cpu instruction rather then thousands of instructions per second.
  
  **Did you require the system to make more than one move a year?**
  
  > **Comments:**
  > **username_1**: The most complex actual mechanical devices are calculators purpose built for one task. Still the processing required for any chess engine algorithm would essentially require a CPU of some kind.  
  > **username_2**: @username_1 is a Turing Machine a CPU?  
  > **username_1**: No, it's a theoretical model of computing that can be physically built, and has been done so before, but is impractical in large amounts of calculation.  
  > **username_2**: @username_1 the question says "possible" not "practical", so no requirement for a proof of a solution to show the solution is practical.  
  > **username_1**: I don't have proof a Turing machine of gargantuan size is possible to build.  
  
  ---
  
  ### Answer by username_0 on 2024-06-06. Score: 1
  
  I would like to try answer this question even though I'm not an expert, because unlike other answerer/commenters, I think the best approach is not to build a general purpose computing device like a CPU and then executing a chess algorithm, but to design a single-purpose device only capable of one task (chess) with a built-in relatively simple algorithm. The closest real-life reference may be El Ajedrecista, which uses simple electric and mechanical technology and only plays an endgame with hard-wired logic, but then it was built in an era without the advanced knowledge of chess engines and algorithms of today. It's possible with algorithmic and engineering hindsight, a much better machine can be built without electronics.
  
  Here's an outline of what I think is possible. One way to use low tech to achieve more play strength might be to make a mechanical neural network. It will be small by today's neural network standards, and the parameters need to be trained elsewhere and hard-wired, but can be implemented with simpler components like gears and latches. For example the internal board representation as an 8x8 grid, where each square has mechanical switches than can be put into different positions to encode whether it's empty and what color/type of piece is there. A grid of gears lock onto the switches and rotate based on the switch positions, feeding the activation into the next layer of gears, and so on. This neural network will be rather large, but is presumably much more efficient and parallelizable than hand-crafted logical rules as in El Ajedrecista. Such a neural network can be a policy network that generates candidate moves directly (eg. the highest activation in the last layer is detected by a touch-based mechanism and translated into moves), or can be a value network that only evaluates a position and returns an analog value.
  
  Another approach is to somehow implement search mechanically. This is obviously harder since mechanical "memory" and processing speed is very limited, but not completely impossible if we only look a low depth and a small number of candidate moves (using the mechanical neural network to generate moves for example). At worst, even looking one move ahead with 2-3 possible moves each is better than nothing. To perform a search mechanically, there could be a stack of board representations (like small metal plates with switches as above) augmented with extra switches to encode candidate moves from the current position, and a numerical pointer to the future position in the stack to logically represent a search tree. A reader/execution head reads the plates and either generates more moves/positions using the policy network when there are blank plates available, or go through the tree to select the best move using the evaluation of the final leaf position (with the value network) using minmax algorithm by going up and down the stack as needed. This should hopefully be able to look at a couple dozen positions or a few moves ahead, and if the neural networks are any good, should be able to beat some beginners.
  
  > **Comments:**
  > **username_1**: How would you train such a neural network? Backpropagation is just chain rule with dynamic programming, which comes down to a lot of matrix multiplies.  
  > **username_0**: @username_1 Train it separately on a modern computer, just like any other neural network. Only the final parameters need to be hard-wired.  
  > **username_1**: Oh I see. Mechanical, but with all the technology of today? Then what is the point?  
  > **username_0**: @username_1 Modern technology and algorithms make it easier, but it's not like totally impossible for someone determined enough back then to figure it out (old mathematicians and inventors were pretty good without computers). If just proving the Turk was possible if given enough resources and hand-tuning effort isn't a good enough reason, then at least there can be practical applications today, for example to build a completely 3d-printed mechanical smart chess set that would presumably be a great conversation piece, and to apply the tech in other ways in extreme environments where electronics fail.  
  
  ---
  
  ### Answer by username_3 on 2024-06-07. Score: 0
  
  Expanding on @alices\_and\_bobs answer, one approach would be to create an actual mechanical model of the board directly, and perform some kind of stack based lookahead. Although some form of mechanical AI weightings could be used as mentioned elsewhere, I would propose a good old-fashioned tree search with pruning. The model would be constructed such that each piece would be individually fixable so that it would be possible to "unlock" each piece on turn and iterate through all legal moves it could make. The board and pieces would not resemble an actual board and pieces but would be optimized for fast mechanical movement of the pieces themselves as well as detecting the current board state for position analysis. The actual movement of the pieces would be based on mechanical allowance - that is, the mechanism would attempt to move the piece in each direction but the piece would only be *able* to make legal moves. As an example, the first order of allowance is that a piece can move into a square if it is not occupied. This would be the easiest to accomplish mechanically as an occupying piece would simply prevent another piece from occupying the square. The next step would be to allow a piece to capture another. This could perhaps use some form of magnets such that pieces of the same color would repel while opposite colors would attract and thus allow the attacked piece to "move aside" and be captured. There is also the encoding of the knight's move, which could perhaps be accomplished by something along the lines of the shapes of the pieces, for instance, perhaps normal pieces would have a cube shape and knights would be spherical and then able to roll or "jump" over another piece, but not stop there if the colors were the same due to magnetic repulsion. Or perhaps pieces would have slanted edges with mechanical grooves that only allowed knights to pass over. A knight's move would also be more complicated because it would not be able to stop at one of the interim squares so would have to somehow be pushed to continue along until it finished its move. On the other hand, kings, and knights would have only a single move that could be made in any "direction", while rooks, bishops, and queens would potentially have many for open ranks, files, and diagonals, so this would have to be mechanically accomodated as well. Pawns would have an extra possible move the first time, but this would probably be the easiest special case to accomodate, as the board itself could be notched in a way that pawns could move one or two squares on their first move but that other pieces would not notice. Likewise with capturing, some kind of grooves could be used to allow pawns to only capture diagonally and otherwise only move in a straight line.
  
  Now we come to the harder parts. Castling can only occur once in the game, and only if the king and rook in question haven't moved. It might be best to keep this in some external flip flop, which then acts to allow or prevent castling from taking place. Promotion would require some extra logic to allow the different promotion types to be iterated through. Things like the 50 move rule and draw by repeated positions would require external logic. Disallowing moves when the king is in check unless it removes the check would also require some external logic. All of this external logic would need to control some kind of "master override" which would apply to all or some squares and would slow the game down. However, stalemate and checkmate would be easy to detect.
  
  Once the mechanics had produced a new valid board position, some kind of evaluation function would need to be applied to get a relative status of the game. This could be a completely analog value, and could be performed by any number of heuristics which directly imprinted the board state and did some kind of weighting, perhaps with springs. This analog value would then be compared to the best value found so far, and if it improved it, the current move would be recorded as the best so far. If the value was far enough below the current best it could prune the current search.
  
  This setup would work best with depth first recursion, as this would be simpler than breadth first. In this mechanism it would only be necessary to keep a stack of moves which would be unwound, rather than needing to keep a stack of board states. However, this would likely require limiting how many plys of lookahead were used based on worst case move time. The speed of a move would be limited by how fast a mechanical move could be made and the corresponding imprint and analysis to update the legal move overrides, as well as to generate the current point status for the purpose of determining if a better move had been found or an unpromising line pruned. Since the board itself is essentially analog it could be much faster than implementing the solution entirely in mechanical logic gates. For instance, it seems reasonable to assume that the machine could evaluate 10 moves per second, and it this rate it could consider its move and all possible counter-moves in under a minute. However to consider its second possible move and all possible responses to that could take over 5 hours, although depending on how aggressive pruning was done it might be greatly reduced. The machine would likely not play very strongly but could be passable as a form of entertainment, assuming that it is still the 1800s. Also, while considering 10 moves per seconds is mechanically doable, it would likely be necessary to maintain the machine after each game to inspect it for wear and replace anything as needed to try to prevent it from breaking down during a game.
  
  
  ---
  
  