Linear Programming Will See MUCH Deeper Than Alpha-Beta

Discussion of anything and everything relating to chess playing software and machines.

Moderator: Ras

User avatar
towforce
Posts: 12514
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by towforce »

For linear problems (of which chess is an example) integer linear programming (ILP) enables optimal values to be found relatively quickly in large search spaces. For example, the very largest proven TSP (travelling salesman problem) solutions uses variants of this method: the record is 85,900 towns - a search space of 85900!=9.6e386526. One man has even claimed to have found a way to solve TSP in polynomial time (click here) - though AFAIK this claim hasn't been peer-reviewed yet. ILP solvers are improving rapidly at this time. At the German ILP problem library, you'll see that in 2003 they had to introduce a new set of much more difficult problems, because newer solvers were able to solve the old ones too quickly!

I gave an example of applying ILP to a river-crossing problem which, like chess, is a series of consecutive states, here. The first thing you'll notice is that, to solve a simple combinatorial problem, I created a 90-line model. The corresponding model I wrote for a 20-man river crossing problem was 1, 500 lines long. Representing chess would require an absolutely huge model.

That's the easy part of the problem!!!

The medium part of the problem is getting the model to converge to a good optimum. The chess tree is full of symmetries, which would have to be broken. There's a paper on breaking ILP symmetries here. Getting large ILP models to converge is often difficult anyway. There are various methods available - the cutting-plane method, branch and bound, branch and cut, and delayed column generation for example - it would, of course, be a case of finding out what combination of known methods works best for a chess tree.

The hard part of the problem is that before getting started at all, it will be necessary to take an ILP solver, and rewrite it to allow not one objective function (the expression that linear programming tries to optimise), but two. I can see no mathematical reason why this should be a show-stopper - but it will be necessary because of the existence of an opponent - whose "objective function" will be approximately the opposite of what our side's will be. As an example, our objective function might be:

* maximise white king safety

* minimise black king safety

* maximise white piece mobility

* minimise black piece mobility

* maximise white piece value

* minimise black piece value

To get the opponent's objective function, simply take the above objective function and reverse each term!

If I were to use the above objective function for white, and somehow got the model to converge in a solver to a good solution over, say, 5 moves, the solution would simply consist of 5 "good" white moves and 5 obviously bad black moves. What is actually required, though, is to find the "best line" - a sequence of moves optimised for both the black and the white pieces. One way might be to take an open-source ILP program and make a fork of it that can take two objective functions - one to be applied to half the expressions in the model and the other to be applied to the other half. Doing this will take both programming and mathematical know-how.

A big job then. :(

The reward, though, will be a chess program that can see much more deeply into the chess tree than anyone today would imagine to be possible. :D
Human chess is partly about tactics and strategy, but mostly about memory
Pradu
Posts: 287
Joined: Sat Mar 11, 2006 3:19 am
Location: Atlanta, GA

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by Pradu »

Alpha-beta is a branch and bound optimization algorithm and works well for a chess tree. Could you give an example of how an iterative deepening chess-program could be formulated as a linear programming problem? Namely, how would you put it in the form

minimize c<transpose> x subject to Ax = b.

How would you formulate the elements of c, A and b? What would x be (I would assume it would be a move somehow ...)?
User avatar
towforce
Posts: 12514
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by towforce »

Pradu wrote:Alpha-beta is a branch and bound optimization algorithm and works well for a chess tree.
I am guilty of greatly simplifying the issue and leaving lots of stuff unexplained!!!

In ILP, when people talk about branch and bound, it goes without saying that they mean branch and bound combined with linear programming (using the simplex or interior-point algorithms).
Could you give an example of how an iterative deepening chess-program
Sorry - but as far as I can see the iterative-deepening would have to go. One would be obliged to pick a fixed-depth and work on that. One could still have improving solutions popping up, though - there's always an option to report interim results, each one more optimal than the last, on all the ILP solvers that I am aware of.
could be formulated as a linear programming problem? Namely, how would you put it in the form

minimize c<transpose> x subject to Ax = b.

How would you formulate the elements of c, A and b? What would x be (I would assume it would be a move somehow ...)?
Ah - you want details on how to formulate the model! :lol:

I haven't got that far yet - sorry!

However - I did solve a couple of river-crossing problems which, like chess, are a sequence of states. For example, click here. This should give you a rough idea on how consecutive states can be represented when each state depends on the previous state. There's a 1995 paper on formulating river-crossing problems as ILP models here (a postscript file in a winzip wrapper).

When I wrote a sudoku solver as an ILP model, I learned from experts at forums that the best way to represent the board for an ILP solver was to have 9 variables for each square - each one being a binary variable that specified ""true" or "false" to each of the numbers 1..9 being present. Maybe such a representation could also be applied for a chess game - 12 variables (one for each type of piece) per square, each one being binary (true or false).
Human chess is partly about tactics and strategy, but mostly about memory
BubbaTough
Posts: 1154
Joined: Fri Jun 23, 2006 5:18 am

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by BubbaTough »

It is not trivial to do this for adversarial multi-player problems. They are quite different from all the problems you mentioned. If you manage to get a working chess program, even if it is not very good, I would be interested in seeing your formulation. Good luck.

-Sam
Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 10:01 pm
Location: Irvine, CA, USA

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by Dirt »

towforce wrote:
could be formulated as a linear programming problem? Namely, how would you put it in the form

minimize c<transpose> x subject to Ax = b.

How would you formulate the elements of c, A and b? What would x be (I would assume it would be a move somehow ...)?
Ah - you want details on how to formulate the model! :lol:

I haven't got that far yet - sorry!
Perhaps you could try a much simpler game.
User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 3:54 am
Location: San Jose, California

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by Bill Rogers »

There apears to be something wrong with this picure as I see it. I was always under the impression that chess was linear to begin with. I am familiar with the traveling saleman finding the shortest route and with the exception that it is much smaller than a chess tree the same type of logic is used for both.
Bill
User avatar
towforce
Posts: 12514
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by towforce »

Bill Rogers wrote:I am familiar with the travelling salesman finding the shortest route and with the exception that it is much smaller than a chess tree the same type of logic is used for both.
It is unrealistic to think that chess could be solved to the same scale as the TSP (travelling salesman problem) - but just to show you that scale, let's assume that the average chess position has 30 choices of move (if you disagree with this assumption, I have no problem whatsoever - just substitute your own number - I'm just showing what the "magic" of linear programming is capable of).

The equivalent ply depth in chess to what has actually been achieved in TSP would be:

30^n = 85900!

Working that out using logs:

logbig: sum(float(log(i)), i, 1, 85900)

(%i6) logbig/log(30),numer;
(%o6) 261675.8655591263


Let me be perfectly clear that there is no way that a search depth of 262,000 ply is going to be achieved in chess - I am just showing you what has been achieved in TSP using linear programming methods.
Human chess is partly about tactics and strategy, but mostly about memory
User avatar
towforce
Posts: 12514
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by towforce »

Dirt wrote:Perhaps you could try a much simpler game.
It's not so much a simpler game required here to make a working prototype as a ready-made ILP solver that can apply different objective functions to different expressions. Believe me - if this was a trivial problem, I wouldn't be describing a method for doing it in public - I'd be working on it! I do think that I could do it - but I'm not sure how I'd feed my family while I was doing it.

If anyone knows somebody who can afford to pay me, and pay ILP specialists to be periodically hired on a contract basis, I have a proven ability to manage multi-disciplinary problems to conclusion on time and on budget - and I would be more than willing to take on this problem. There would have to be a lot of slack in the project plan in this case though, I'm afraid.
Human chess is partly about tactics and strategy, but mostly about memory
Pradu
Posts: 287
Joined: Sat Mar 11, 2006 3:19 am
Location: Atlanta, GA

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by Pradu »

Comparing TSP nodes (and number of choices to other TSP nodes) to nodes in chess (and number of choices to other chess nodes) is not realistic. The traveling salesman problem is quite different than a two-player game. For a general asymmetric traveling salesman problem (cost going one way may be different than the cost going the other way) you formulate it as an problem where your solution (with elements "x_ij") says whether you travel from node i to j (1 if you do, 0 if you don't <integer constraint on x_ij>). Then you add equality constraints so that you arrive and leave from each node exactly (sum x_ij=1 for arriving/leaving path) and then you have to add some more constraints to remove disjoint subtours. In chess however, the nodes and costs of traveling nodes are not previously known (unless you generate them explicitly). Lets say you could somehow formulate chess as a linear programming problem in a similar fashion to TSP. You first have to generate the nodes. Here's the first problem:

Which nodes to generates? All nodes to depth n? If you do that, the efficiency of this kind of algorithm already drops to that of minimax in the just the generation of the problem (not even the solution). In the time that it takes to generate nodes alphabeta has already evaluated all the nodes in approx. sqrt the time. So the generation of the problem is not quite as trivial as you make it out to be in the first post.

For your calculation on comparing branching factor and depth with TSP, I don't think the comparison is realistic. For TSP all the nodes are known and are of a small number (85900 lets say) and at every choice you have all the previous choices you had at the previous node-1. In chess however you obtain approximately on the order of millions of new nodes every second. After a move you have choices that lead to new nodes for the opponent. Quite a different problem...

Nevertheless, it would still be interesting to see a formulation of chess as a linear programming problem. You will first have to find a way to iteratively pose/generate the problem efficiently and this step is quite different from other problems such as TSP where the problem is given to you. Then you will have to find a way to pose the objective function (how to handle minimaxing strategy). Then you have to find a way to state the constraints (rules on how to traverse nodes, checkmate, fifty-move, draws...).
Last edited by Pradu on Sun Jan 04, 2009 1:20 pm, edited 1 time in total.
User avatar
towforce
Posts: 12514
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: Linear Programming Will See MUCH Deeper Than Alpha-Beta

Post by towforce »

Pradu wrote:Lets say you could somehow formulate chess as a linear programming problem in a similar fashion to TSP. You first have to generate the nodes. Here's the first problem:
Agreed - generating the nodes in chess is absolutely out of the question.

Given the number of LP expressions that would be required to play chess, I think that it's a fair bet that the delayed column generation method would have to be used - and probably combined with symmetry-breaking and cutting-plane methods as well - so you are quite right - it would be ridiculous to think that the chess tree could be searched to 262,000 plies - and if I sounded as though I was intending to imply that it could, then I apologise. I am confident that ILP could out-search current methods by a massive margin, though.
Then you have to find a way to state the constraints (rules on how to traverse nodes, checkmate, fifty-move, draws...).
The only "traversing nodes" would be on the problem polytope (see the wikipedia linear programming article). If one can see far enough ahead, one need not bother with check checking. For awkward rules like draw by repetition or 50-move, I would envisage using a standard chess program to alert the risk, so that the LP model could be modified to avoid the problem.
Human chess is partly about tactics and strategy, but mostly about memory