Chess Optimisation Algorithm Needed For New Quantum Computer

[towforce]

There is a new commercial quantum computer available (click here) - but it will only do optimisation problems - not general programming. So how do we turn chess into an optimisation problem? What is optimal about the best line in chess?

This is more difficult than it first looks: if, for example, you say, "The optimal line is one in which neither player loses a piece", the output would be a sequence of moves in which neither player loses a piece - but because you're optimising for both sides simultaneously, there is no "optimisation pressure" to find a line in which neither player CAN lose a piece - only one in which neither player actually DOES.

n.b. if we can think up a sound way in which the best line is optimal, then we can make a linear programming model for it. Again, this would almost certainly be able to see a lot deeper than any computer today running a game-tree search (assuming that we're not closer than we think to the depth of search that will almost always obtain a draw no matter how good the opponent - an assumption that may not necessarily be sound).

[Sven]

The "optimal" path is starting with the move that puts the opponent into the worst situation, even if he chooses the "optimal" continuation from his viewpoint. Therefore some sort of "negamax" thinking will be necessary at least, i.e. the costs of the path to a node are the negated minimum of the costs from that node to all its successors, if I assume that optimisation means minimising costs (equivalent to maximising evaluation). The costs of the path to a leaf node could be defined as the negated static evaluation of that leaf node, where each node is always evaluated from the perspective of the moving side, and where a large negative value means that the moving side is winning, and vice versa. (Nothing new here except for the flipped sign ...)

I'm pretty sure, though, that you would end up in writing some sort of a traditional chess program, only expressed in different terms and with a different way of searching the solution.

You need a board, a move generation, a make (and possibly unmake) move function, an evaluation function, a detection of legality/check/mate/draw, ... You need to keep track of the game history. You certainly need something like move ordering since you would not want to start optimising with a path beginning like "queen takes defended pawn". Therefore SEE and killer heuristic come into mind immediately. It may also make sense to have a hash table which usually helps a lot in move ordering - this in turn requires all the usual stuff for zobrist keys etc. Selectivity, like in quiescence search, could be necessary, too, for nodes with a sufficiently long distance to the start node but where some successor moves exist (e.g. checks, non-losing captures) that make the static evaluation function unreliable.

I guess it could be difficult for an LP model of chess not to make use of all of this.

Also a lot of useful things for debugging and testing will be required like in traditional programs, since I believe that writing a bug-free LP model for chess is not significantly easier than writing a bug-free C/C++ chess program, and having no bugs is really essential.

The big question would be, should we expect that LP can beat today's alpha-beta search with extensions/pruning/reductions?

Since overall complexity of chess and available processing resources do not allow to look ahead from an average opening or middlegame position until 6-men/7-men tablebase positions are reached (you will agree that you can't do that even with LP), the key problems will remain the same as in our traditional search:
- decide which paths to follow and which not,
- decide where to stop going further, and
- define the costs by estimating (evaluating) the probable game-theoretic outcome at a node where you stop going further.

Nevertheless, since I remember how often in the past you were able to quickly come up with a decent LP model for some nice puzzle, and that its solution time usually was quite competitive against the brute force methods, I think that you have chosen a challenging task which I believe is not as "hopeless" as it may sound initially.

Looking forward to your research!

Sven

[nanochess]

I couldn't find useful information about how to code or what are the qu-bits capabilities. You should start with something more simple, like Tic-Tac-Toe, would be great if you can show to Talkchess how to translate a tree-based search of Tic-Tac-Toe to the requirements of this quantum computer.

Let me say I'm still sceptic about quantum computers, appears that I remember that Scientific American says that the greatest capacity is of 16 qu-bits.

[rbarreira]

This quantum computer, has it been proven not to be vaporware or deceitful marketing?

What size of problems can it handle? Anything non-trivial that couldn't be easily solved by a modern computer?

[Dirt]

There is a new commercial quantum computer available (click here) - but it will only do optimisation problems - not general programming. So how do we turn chess into an optimisation problem?

Quantum computers probably will not help with chess, but that is not certain. I'm pretty sure that proving or disproving that is a very difficult problem.

[towforce]

I'm pretty sure, though, that you would end up in writing some sort of a traditional chess program, only expressed in different terms and with a different way of searching the solution.

You need a board, a move generation, a make (and possibly unmake) move function, an evaluation function, a detection of legality/check/mate/draw, ... You need to keep track of the game history. You certainly need something like move ordering since you would not want to start optimising with a path beginning like "queen takes defended pawn". Therefore SEE and killer heuristic come into mind immediately. It may also make sense to have a hash table which usually helps a lot in move ordering - this in turn requires all the usual stuff for zobrist keys etc. Selectivity, like in quiescence search, could be necessary, too, for nodes with a sufficiently long distance to the start node but where some successor moves exist (e.g. checks, non-losing captures) that make the static evaluation function unreliable.

I guess it could be difficult for an LP model of chess not to make use of all of this.

Look at Swami's river crossing puzzle - click here. This is a problem that could be solved by constructing a game tree (though, as the Wikipedia article points out, there are better ways). Imagine what the game tree C program would look like.

Now take a look at my linear programming (LP) solution - click here: notice that it looks NOTHING WHATSOEVER like a game tree program. The same would be true of an LP model of chess.

The big difference, of course, is that in a river crossing problem, there is a single number to optimise (the same is true of the travelling salesman problem - for which linear programming holds the current record of 33,810 destinations - a search space of 33,810!=1.5E138446). Likewise, you would need to have a single number to optimise to use linear programming in chess.

I do not know if this restriction would apply to the new quantum computer though - it may be able to optimise over multiple variables for all I know.

[Sven]

I'm pretty sure, though, that you would end up in writing some sort of a traditional chess program, only expressed in different terms and with a different way of searching the solution.

You need a board, a move generation, a make (and possibly unmake) move function, an evaluation function, a detection of legality/check/mate/draw, ... You need to keep track of the game history. You certainly need something like move ordering since you would not want to start optimising with a path beginning like "queen takes defended pawn". Therefore SEE and killer heuristic come into mind immediately. It may also make sense to have a hash table which usually helps a lot in move ordering - this in turn requires all the usual stuff for zobrist keys etc. Selectivity, like in quiescence search, could be necessary, too, for nodes with a sufficiently long distance to the start node but where some successor moves exist (e.g. checks, non-losing captures) that make the static evaluation function unreliable.

I guess it could be difficult for an LP model of chess not to make use of all of this.

[...]
Now take a look at my linear programming (LP) solution - click here: notice that it looks NOTHING WHATSOEVER like a game tree program. The same would be true of an LP model of chess.

What I mentioned was not the "game tree" part of a chess program, it was the part which you cannot ignore, like implementing the rules, making a move, or detecting obviously bad moves. That is quite a bit. You will write it down differently for LP, of course, but you will have it.

The big difference, of course, is that in a river crossing problem, there is a single number to optimise (the same is true of the travelling salesman problem - for which linear programming holds the current record of 33,810 destinations - a search space of 33,810!=1.5E138446). Likewise, you would need to have a single number to optimise to use linear programming in chess.

The "single number" could be the value (costs) of the principal variation for a given position.

Sven

[towforce]

What I mentioned was not the "game tree" part of a chess program, it was the part which you cannot ignore, like implementing the rules, making a move, or detecting obviously bad moves. That is quite a bit. You will write it down differently for LP, of course, but you will have it.

Actually, you wouldn't have bad move detection. If an LP chess program is possible, though, I strongly suspect that some code which is not theoretically needed might be needed to break symmetry: in integer problems in LP ("integer programming"), solvers tend to struggle in a large search space that has a lot of symmetry - so one often sees symmetry breaking code added.

However - if I could come up with a single number to optimise, and I wrote a chess LP model, I would first try to construct it using real numbers only. Again, this might not be possible due to restrictions like having to pick a single move.

The big difference, of course, is that in a river crossing problem, there is a single number to optimise (the same is true of the travelling salesman problem - for which linear programming holds the current record of 33,810 destinations - a search space of 33,810!=1.5E138446). Likewise, you would need to have a single number to optimise to use linear programming in chess.

The "single number" could be the value (costs) of the principal variation for a given position.

How would one place a value on a particular variation, though?

[Sven]

The big difference, of course, is that in a river crossing problem, there is a single number to optimise (the same is true of the travelling salesman problem - for which linear programming holds the current record of 33,810 destinations - a search space of 33,810!=1.5E138446). Likewise, you would need to have a single number to optimise to use linear programming in chess.

The "single number" could be the value (costs) of the principal variation for a given position.

How would one place a value on a particular variation, though?

By evaluating the terminal node of that variation, and applying the correct sign to the result depending on the side to move there and the side to move at the starting node.

Sven

[towforce]

The "single number" could be the value (costs) of the principal variation for a given position.

How would one place a value on a particular variation, though?

By evaluating the terminal node of that variation, and applying the correct sign to the result depending on the side to move there and the side to move at the starting node.

Ask an optimiser to produce the variation which results in the highest valuation for white, and the output will be black throwing away pieces and marching his king into danger!