Math as a Mathematical Formula using Matrix/Algebra?

It's an NP-complete problem; meaning that as the problem space grows the amount of time required to compute a solution becomes unreasonable. Chess is one such game where each move requires an exponential number of computations to solve for an end-game. Given that there are theoretically more board configurations than atoms in the known universe; even if one could simplify the algorithm by using pre-determined board configurations from a database, there'd be no known way to store that database.

Some quick googling will reveal that modern chess computers use a finite set of common board configurations, a set of algorithms for playing the game, and a set of heuristic algorithms. It's the heuristic algorithms that let the computer play a full game -- they provide the main algorithm with approximations of a best-guess as to which move would be the optimal move. As computing power has increased over the years, it's the heuristic algorithms that have gotten the most attention as it's one of the greatest weaknesses of a chess computer since it can never be "certain" that any one move is statistically superior than any other -- especially in the later mid-game when the board configuration is so complex that it has to rely more an more on the heuristics algorithms to provide more guesses.

Heuristic algorithms are the reason why computers are tactically superior to human players, but lack strategy. A computer at this time cannot choose an end-game or optimal game. However, it can punish creative players easily and seem to be impossible to beat since it can certainly plan an 8-move combination that will reward itself with a pawn on an undefended file. This is the main advantage and disadvantage of heuristic algorithms.

Therefore, I'd say no -- it's not possible to solve a game of chess with purely functional mathematics. We can only use algorithms to explore the problem, but never solve it.

j_king - you definitely seem to know more about the math and logistics side of current chess programs than i do, but i failed to see how you reached your conclusion that we can't solve chess with an equation. 

are you saying that because there are more chess positions than atoms in the universe, the equation would have to be impractibly large?  because my whole point behind the equation-solution is that it would not have to consider chess positions, it would simply be an equation that you can apply to any chess position.

also, if/when the perfect game of chess is discovered, the difference between tactics and strategy becomes nonexistant.  the reason is because at this point there is neither tactic nor strategy, there is simply right and wrong. 

when you say that computers lack strategy i assume that you mean that they lack the ability to recognize certain winning moves that are outside of their calculations.  as computers get better, however, they will be able to recognize more and more winning moves. whether we currently call those moves "strategy" or "tactics" is irrelevant.

if people have a semantic issue with me saying that a computer will eventually be able to make what we call a "strategic" move, i would counter that the computer did not make a strategic move, it simply recognized the tactics behind why that move is winning.    

johnny263 wrote:

j_king - you definitely seem to know more about the math and logistics side of current chess programs than i do, but i failed to see how you reached your conclusion that we can't solve chess with an equation. 

are you saying that because there are more chess positions than atoms in the universe, the equation would have to be impractibly large?  because my whole point behind the equation-solution is that it would not have to consider chess positions, it would simply be an equation that you can apply to any chess position.

also, if/when the perfect game of chess is discovered, the difference between tactics and strategy becomes nonexistant.  the reason is because at this point there is neither tactic nor strategy, there is simply right and wrong. 

when you say that computers lack strategy i assume that you mean that they lack the ability to recognize certain winning moves that are outside of their calculations.  as computers get better, however, they will be able to recognize more and more winning moves. whether we currently call those moves "strategy" or "tactics" is irrelevant.

if people have a semantic issue with me saying that a computer will eventually be able to make what we call a "strategic" move, i would counter that the computer did not make a strategic move, it simply recognized the tactics behind why that move is winning.    

Maybe you should start with glossing over the summary of NP-complete on wikipedia.

The problem is that as each piece is moved, the number of possible outcomes grows exponentially. This is an NP-complete problem because after just a handful of moves, there is no way to compute the complete series of possible outcomes within a reasonable amount of time. We know that it is theoretically possible, but we just don't have all the time in the universe to sit and make those calculations and our computers are no where near fast enough to do it for us in a reasonable amount of time either. Hence the problem's status as NP-complete.

See, it's not that the equation has to be impractically large, just that the data going into the equation becomes impractically large in short order.

Consider that 10^64 (a naive estimate of the number of possible board configurations) is not a small number. It's so big that no computer on Earth can store it. We can only operate on it using abstract representations of it. As mentioned, it is theoretically bigger than the number of atoms in the visible universe (or might as well be).

There isn't an equation we know of that can generate all the permutations from one state to an end-game state with that large of a range of possible permutations. Once Deep Blue makes its move, it begins to generate all the permutations from that state forward in the background while you decide what your move will be. Ten moves into a game and you could walk away and let Deep Blue think for the rest of your life and it still won't calculate every single permutation. In fact, it's more likely to run out of memory (unless the developers gave it boundaries to work within).

That's why computer scientists use heuristic algorithms. Sometimes the only way to proceed is to choose a best-guess. Otherwise, you move the first pawn and the computer will go on for longer than you can live calculating all the possible outcomes before ever moving its first piece. There are just that many variations. That's what makes it NP-complete.

http://en.wikipedia.org/wiki/Computer_chess see the section on Solving Chess. Not very comprehensive from a mathematical view, but it does cover most things.

Also, re: strategy vs tactics -- the difference is definitely distinct.

Strategy is the ability to choose an an out-come and devise a plan to achieve that goal.

Tactics is the ability to make the move that will yield the best possible result given the current state of the board.

A computer is really only capable at this point of being really good at tactics. It cannot choose a strategy or adapt that strategy unless we tell it which strategy to adopt (and how to implement it) or telling it which strategies are more favourable. Either way, a human is still superior in this realm for now. We're able to choose a strategy, adapt our strategy mid-game, and even feign a strategy to throw off our opponent. That kind of behaviour, for the time being, is beyond the realm of computers and algorithms..

johnny263 wrote:

bowanza wrote: Just because a system follows a well defined set of rules does not at all mean it can be predicted by formula.  An excellent example of this is the prime numbers.  A prime number can only be divided evenly by one and itself.  So a simple test for prime would be:  For all x from 2 to itself-1 if remainder (itself/x) =0 then prime=false.  Yet there is no known formula that generates only prime numbers, let alone predict them in order of succession.

 Bowanza, do you have another example of what it is you're trying to say?  your prime number example doesn't exactly work because there are infinite prime numbers and a finite number of chess positions.  further, i'm not looking for a formula that will give out EVERY winning chess move, i'm talking about a formula that will give out a winning chess move given an exact position. 

you gave an example of a formula for determining IF a number is prime

Bowanza: "For all x from 2 to itself-1 if remainder (itself/x) =0 then prime=false"

Similarly, i'm talking about a formula for determining IF a move is winning.  So, again, i don't think the prime number example works especially since a formula DOES exist for determining IF  a number is prime.  do you have another example?

You are confusing an alogrithm with a formula.  A formula is a mathematical computation when all the variables are known.  For example, a formula for the area of a triangle is square root of s(s-a)(s-b)(s-c) where a,b, and c are the lengths of the sides and s is the semiperimeter, 1/2 (a+b+c).  Given a,b, and c we can calculate s and then the area using the formula.

but if n=number to test for prime then

{ prime:=true;for x from 2 to x-1 if ((n mod x) == 0) then prime=false; }

is an alogrithm and it will run as long as you want it to just by choosing n large enough.  It is not a formula.  It is an algorithm.  The time for an alogorithm to finish often depends on the size of the input, and in chess is no exception.  As someone above pointed out, the run time is exponentially related to the depth of search, which would have to go to the end of the game so would be incredibly large, so large it could never be computed.

Here is another example of what you are trying to do by trying to find a formula for chess:

Suppose a man and a woman get married and have children, 4 of them to be exact.  At this point in time, their ages are 1,4,6, and 8.  Now you could find a formula in x^4 that yeilds 1 when plugging in 1, 4 when plugging in 2, 6 when plugging in 3, and 8 when plugging in 4.  In other words, you could find a function in x^4 such that

f(1)=1, f(2)=2, f(3)=6, and f(4) = 8.  But the amount of time to make the computation would be more for a computer than just to look up the data in an array.

Imagine if each of those kids grew up and had familes of their own.  Lets say the first child 1 had 3 kids.  the second child had 2 kids,  the third child had 0 kids, and the fourth child had 4 kids.  And lets assume their current ages can be found in the following tables:

child 1                   child 2             child 3            child 4

kid  age                 kid   age                                 kid age

1    2                     1      4                                    1   2

2    4                     2      7                                    2   3

3    8                                                                  3   3

                                                                         4

Now some mathematician somewhere could probably find a 4th degree polynomial in (x,y) where x=child # and where y=kid # where

f(x,y)=age of the child.  Can you imagine the amount of computation that would be necessary compared to a computer accessing a two dimensional array for the ages?  And as more data is added, the formulas grow larger and larger, but the look-up time to access a data table does not increase significantly.  And this formula would have to return -1 or some illegal quantity for an age if you tried to find out the age of the first child that didn't exist, for instance the "fifth child" of the original family.

bowanza - i assume your new example of the kids and their kids is to try to explain the difference between an algorithm and a formula because it's clearly not an example to show how no formula for chess can exist. 

that being said, i think i understand what you're saying about an algorithm vs. a formula but i don't think it really affects the discussion between you and i very much at all. and here's why.

back to the prime nubmer example (which i assume is the one supposed to relate to the discussion about chess).  you have said that

"Just because a system follows a well defined set of rules does not at all mean it can be predicted by formula.  An excellent example of this is the prime numbers. . . . there is no known formula that generates only prime numbers, let alone predict them in order of succession." 

the solving chess equation is not directly comparable to a forumla for generating adn predicting prime numbers.  the solving chess formula would not be able to tell you the position of the board on move 23 or move 45.  it would simply be able to tell you the best possible move given the current position on the board.  this is much more comparable to your algorithm for determining if an individual number is prime or not. 

The problem with "solving chess" is that you basically have to calculate all variations through to mate. Calculating 20 moves deep and seeing you win a piece by force isn't enough; it could just happen to be that the opponent wins the piece back by force and draws, for example. So to solve chess, for every position, you have to make a HUGE tree of all variations and analyze them all through to a forced repetition, checkmate, stalemate or something similar.

Now suppose you want to do this from the starting position. On average, every side will have alot more than 20 moves per position, but let's just assume that number to be 20. We also know from experience, that a game will in general last at least, say, 40-50 moves before we get a result. This result is usually achieved long before checkmate (resignation, or agreed draw) so I think it's fair to say an "average" forced variation will last at least 50 moves each.

Now if we calculate how many positions the tree will have, we get 20^100 which is about 10^130 positions. You'd need a computer that is able to calculate 10^130 positions. Right now the fastest supercomputer has a speed of about 10^15 FLOPS (floating point operations per second). So that computer would need 10^115 seconds, or 3*10^107 years to compute the whole tree.

Or, say, you have a limit of 100 years of calculation, with a million computers dividing up the work. Then we'd need those computers to have a speed of 10^115 FLOPS.

No, chess isn't infinite, and yes, in principle chess is solvable. But we don't have infinite time and space so we just can't solve chess.

johnny263 wrote:

the solving chess equation is not directly comparable to a forumla for generating adn predicting prime numbers.  the solving chess formula would not be able to tell you the position of the board on move 23 or move 45.  it would simply be able to tell you the best possible move given the current position on the board.  this is much more comparable to your algorithm for determining if an individual number is prime or not. 

That's the whole problem. To see what is the best move, you DO need to look at all following positions. The only way to tell whether move A is better than move B is to compare the resulting position from both moves. But to compare those positions, you'd again have to analyze all moves from those positions. And all positions arising from all moves from those positions. And all moves from all positions arising from all moves from those positions... I assume you get the point :)

j_king:

1) so if it's theoretically possible but the problem is "that the data going into the equation becomes impractically large in short order" then it seems to me that the equation is possible, we just need to either find a way to shorten the amount of data inputs or a way to process the problem faster.  but this is probably irrelevant because:

2)why do you keep talking about how many chess positions there are?  this is irrelevant to our discussion.  let's take a mate in 8 example.  we've both seen mate in 8 puzzles and can agree that there can be a solution to a mate in 8 position.  further we should both be able to agree that we don't have to memorize every possible position that could result from the initial mate in 8 position in order to solve the position.  we can simply say "if i move here and he doesn't move to 'X', then it's mate in 4 NO MATTER WHAT.  conversely, if he does move to 'X' then on the next move, if i move here and he doesn't move to 'Y' then it's mate in 5 NO MATTER WHAT.  etc. etc.  the mate in 8 is solved without analyzing all possible board positions.

3) if strategy is the ability to choose an an out-come and devise a plan to achieve that goal, then i would say for a computer, that strategy is winning.  so you're right, the computer can't choose a strategy and it can't adapt a strategy or "feign a strategy to throw off an opponent" because it's strategy is always to win.  the goal is always checkmate.  there is no reason though to say that ocmputers will always be weaker than humans in this realm.  if, on the other hand, your definition of strategy only applied to positional goals (like a strong king-side advance, etc.), then your argument again becomes semantic. 

Phobetor wrote:

johnny263 wrote:

the solving chess equation is not directly comparable to a forumla for generating adn predicting prime numbers.  the solving chess formula would not be able to tell you the position of the board on move 23 or move 45.  it would simply be able to tell you the best possible move given the current position on the board.  this is much more comparable to your algorithm for determining if an individual number is prime or not. 

 Phoebatar, i think you meant the only way WE KNOW OF.  i agree that it's definitely easier to think of a solution to chess in terms of a complete tree of possible variations from a given position, but this does nothing towards implying that it is the ONLY way to find a solution. 

johnny263 wrote:

bowanza - i assume your new example of the kids and their kids is to try to explain the difference between an algorithm and a formula because it's clearly not an example to show how no formula for chess can exist. 

You still seem to be confusing an algorithm with a formula.

The point of my example of the kids is to show that even though a formula could be developed to predict a result, it is not always desireable, and in the case of the kids become ridiculous very quickly.  If you noticed how quickly the equations became unweildy at the second generation, imagine trying to make a formula to cover 10 generations all with families having 20 or 30 kids!  But that is what must be done to prove you have found the best move within 10 plys.  And then it still wouldn't be guaranteed to be the best move, only the best it can see within its search, no doubt a very strong move and probably the strongest, but still not known for sure. 

If a formula for chess were possible, there would also have to exist a formula for just a white king and pawn versus the black king.  Lets say we numbered the squares of the board from 1 to 64.  The formula would have 4 inputs.  1 for whose move it is, call it m which could be 0 or 1, 1 for the position of the white king,wk ,one for the position of the white pawn, called p, and one for the position of the black king, bk.  Castling and en passant need not be considered in this case.  So your function would look something like

f (m,wk,p,bk,)  = ??????????????????????????????????????????????????????

How do you suggest you add, subtract, multiply, or divide the inputs to produce its output, a number from 1 to 64?  (By the way, you would also need another function, again of the same four varibles, to tell you the proper piece to move)

Now you could consult a database and produce a table with all the best moves stored in there.  This table would have roughly 2*64*57*48 entries.  Thats a table with 350,208 entries.  If you thought it was difficult to make a formula for the two generations of families I invented above (about 12 entries) imagine what the equation would look like just for the two kings and a pawn.

johnny263 wrote:

Phobetor wrote:

johnny263 wrote:

the solving chess equation is not directly comparable to a forumla for generating adn predicting prime numbers.  the solving chess formula would not be able to tell you the position of the board on move 23 or move 45.  it would simply be able to tell you the best possible move given the current position on the board.  this is much more comparable to your algorithm for determining if an individual number is prime or not. 

 Phoebatar, i think you meant the only way WE KNOW OF.  i agree that it's definitely easier to think of a solution to chess in terms of a complete tree of possible variations from a given position, but this does nothing towards implying that it is the ONLY way to find a solution. 

Sry to say ... But its getting a little ridiculous now

It's possible, but it's going to take a while. Chess, though the amount of variations is many, is still limited. There might be a possible algorithm that only computers can use. I mean, the Rubix Cube has been cracked for algorithms easily enough, and people before said it was impossible. So wait and see...

Chess is psychological to us airbreathers. We see the situation OTB and it provokes a response that is emotional/mental. I think when you talk about chess abstractly like this topic you are missing the practical point about chess.

Yes it is intresting to give our power over to the computer's "hands", but then were left watching twittling our thumbs. Chess is game by game, there are no hard and fast rules, just like there are no perfect human beings to constuct perfect computers to play perfect chess. Were getting better, but I think of it more as an evolution-chess will always be, its us that does the changing.

I was not thinking about a formula that discovers the best chess moves. That is what the algorithmic chess machines are attempting. I was thinking of a formula that in the given 64 square matrix describes all possible chess moves. Such a formula would provide no solutions per se but merely describe all possible moves in this matrix. Such an equation, if it could be devised, would be descriptive, and yet the existence of such an equation might lead to some interesting outcomes although I am not sure what they are until this is accomplished.

For example, the mapping of prime numbers created a landscape which showed some periodocity that mirrored Fourier series in some way if I remember my reading from a book on Riemann's hypothesis although I am not sure if I am recalling correctly. At any rate, the formula did lead to certain usable observations and turned out to be usable in cryptography which is for many purposes including banking. Prime number formulae I am pretty sure also turned out to mirror some physical phenomenon in the real world. I'm not saying that a chess move formula will show anything, but I'd be curious what would turn up and how it might be used.

johnny263 wrote:

Phobetor wrote:

johnny263 wrote:

the solving chess equation is not directly comparable to a forumla for generating adn predicting prime numbers.  the solving chess formula would not be able to tell you the position of the board on move 23 or move 45.  it would simply be able to tell you the best possible move given the current position on the board.  this is much more comparable to your algorithm for determining if an individual number is prime or not. 

 Phoebatar, i think you meant the only way WE KNOW OF.  i agree that it's definitely easier to think of a solution to chess in terms of a complete tree of possible variations from a given position, but this does nothing towards implying that it is the ONLY way to find a solution. 

It IS the only way to solve chess. I'm sure it has been proven before that it's a PSPACE problem, which proves that it CANNOT be solved faster, easier, simpler.

Anyway, it's obviously no use to convince you there is no faster way, since you won't take our word for it. And agreed, it's a very complex matter which is both hard to explain and hard to understand. And it's good to be critical and not just accept someone's word for it. But you'll have to trust the hundreds of years of science experience that they knew what they were saying when they said there's no other way :)

Else, if you're still totally unconvinced, try to find a counterexample. If you give us another quicker method of solving chess, we'll try to refute it ;)

darius wrote:

I was not thinking about a formula that discovers the best chess moves. That is what the algorithmic chess machines are attempting. I was thinking of a formula that in the given 64 square matrix describes all possible chess moves. Such a formula would provide no solutions per se but merely describe all possible moves in this matrix. Such an equation, if it could be devised, would be descriptive, and yet the existence of such an equation might lead to some interesting outcomes although I am not sure what they are until this is accomplished.

For example, the mapping of prime numbers created a landscape which showed some periodocity that mirrored Fourier series in some way if I remember my reading from a book on Riemann's hypothesis although I am not sure if I am recalling correctly. At any rate, the formula did lead to certain usable observations and turned out to be usable in cryptography which is for many purposes including banking. Prime number formulae I am pretty sure also turned out to mirror some physical phenomenon in the real world. I'm not saying that a chess move formula will show anything, but I'd be curious what would turn up and how it might be used.

Maths is just great, and yes, from simple problems like the prime numbers you can get alot of new, seemingly totally unrelated information.

I doubt it works with chess though. If you take an 8x8 matrix to be the position on the board, and you want moves to be functions from position A to position B, then those functions are not linear. The move e2-e4 from the starting position cannot be represented by a matrix C such that C * A = B, since it's not linear.

So you'd end up with 20 ugly functions to decribe the 20 different moves. And for the next move, you'd get another 20 ugly and different functions.

Here is a good question, this goes with the guy that said there are plenty of different positions that a computer does not need to calculate.

How many different positions do you think one can come up with that one person has 2 white squared bishops, 3 white squared bishops, 4 white square bishops. Can one even imagine how many completely useless positions need to be stored? Now say that you dump every useless position on the board. Now if playing a computer and you actually get to promote a peice, say you just mess with it by promoting it to a bishop and the computer does not have those positions, just have the computer see it as a queen unless it's a knight.

Don't you guys think we could shrink that number greatly by ruling out completely outragous positions such as a man that sacrafises all pawns besides one and wins a knight by taking out a rook? I think it's possible to break chess, on games where a player does complete nonsense maybe the computer can just go back to old school algorithms. Just drop all possitions where a player is down a substantial amount of peices with no positional grounds. If GM's have a hard time playing computers without a handicap could you imagine a computer knowing every line but hopeless positions? Why bother calculating nonsense when it's not needed? Sure it's not 100% cracked but I would call it 99.999999% cracked.

Anyways, back to me first question, is there anyone that could calculate the obviouse nonsense like I stated at first, how many possible positions can you come up with when players have multiple rooks, and bishops?

johnny263 wrote:

j_king:

1) so if it's theoretically possible but the problem is "that the data going into the equation becomes impractically large in short order" then it seems to me that the equation is possible, we just need to either find a way to shorten the amount of data inputs or a way to process the problem faster.  but this is probably irrelevant because:

2)why do you keep talking about how many chess positions there are?  this is irrelevant to our discussion.  let's take a mate in 8 example.  we've both seen mate in 8 puzzles and can agree that there can be a solution to a mate in 8 position.  further we should both be able to agree that we don't have to memorize every possible position that could result from the initial mate in 8 position in order to solve the position.  we can simply say "if i move here and he doesn't move to 'X', then it's mate in 4 NO MATTER WHAT.  conversely, if he does move to 'X' then on the next move, if i move here and he doesn't move to 'Y' then it's mate in 5 NO MATTER WHAT.  etc. etc.  the mate in 8 is solved without analyzing all possible board positions.

3) if strategy is the ability to choose an an out-come and devise a plan to achieve that goal, then i would say for a computer, that strategy is winning.  so you're right, the computer can't choose a strategy and it can't adapt a strategy or "feign a strategy to throw off an opponent" because it's strategy is always to win.  the goal is always checkmate.  there is no reason though to say that ocmputers will always be weaker than humans in this realm.  if, on the other hand, your definition of strategy only applied to positional goals (like a strong king-side advance, etc.), then your argument again becomes semantic. 

http://en.wikipedia.org/wiki/Endgame_tablebase

http://en.wikipedia.org/wiki/Perfect_play#Perfect_play

http://en.wikipedia.org/wiki/Game_complexity#Complexities_of_some_well-known_games (Which lists chess as EXPTIME-Complete, not necessarily NP-Complete since chess has a definite complete state, but the number of moves is exponential to the size of the board).

Everything I have said is relevant as the above links show. I haven't made anything up. If after studying all of that and you still believe you're right, I'd like to hear how you would approach the problem and we can debate that.

phobetor

yes ugly functions; and as per discussion above perhaps I am asking the wrong question or describing a situation that cannot exist. The moves would not be defined as an equation whereby something equals something, and I am not looking for an algorithm that tries to achieve a goal. I am looking first for a desccriptor and then wondering what might I do with it--whether it could be used in any way in the game of chess or relate to anything else. Perhaps I should not have asked the question before thinking through clearly what I had in mind and providing a good example of what I meant. Lemme think it through a while.