I think Tricron is correct in that with a complete game tree, and perfect information (which is the case in chess) , an outcame is predetermined if playing to win. If both players are perfect, the game will either :
- always win for white
- always win for black
- always draw
Since the game hasn''t been solved yet, we don''t know which is the case - but we do know that it must be one of those cases.

In response to the original post, that is the kind of reasoning used by most chess programs. However, in order to really determine the most favourable outcome, the program would have to look at all possible moves which is impossible in practice with current levels of technology. The best chess programs go to about 6 moves ahead (6-ply) for evaluation, use a selection of openings with proven effectiveness to get them started, and often jump to 12+ ply in particular situations like endgames.

Thanks for agreeing with me =)
As for the statement it wasn''t a joke, and I think i found it on gamedev. Don''t qoute me on that location either. I may have got it from anywhere =)

One of the biggest problems in determining the ''favourability'' of moves is that in games like chess it is often beneficial to sacrifice a piece (lose piece advantage) to gain strategic (board) advantage. This is often seen when a player will ''draw out'' the piece of another so as to weaken the opponents defense/offense. It is VERY hard to evaluate the relative strengths of piece advantage over board advantage, or even the individual strengths of these factors.

There are however limitless articles on programming computer chess. There was a very good series posted here on GD recently. Check out the articles section.

Cheers,

Timkin

Tricron, chess has NOT been solved. Period. You didn''t read this on GameDev. You did not read this ANYWHERE because it''s just not true.

Of course Argus''s statement is true... given a complete game tree it will be possible to either always force a win, or always force a draw. This is a given for any deterministic game. But you made the statement that it has already been determined that white can always win, and that''s not true.

quote: Original post by Pyabo
Of course Argus''s statement is true... given a complete game tree it will be possible to either always force a win, or always force a draw.

Or always lose. It might prove that, when both players follow optimal strategies, there is actually a disadvantage to whoever moves first.


[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

quote: Original post by Pyabo
Tricron, chess has NOT been solved.

...*snip*...

But you made the statement that it has already been determined that white can always win, and that''s not true.

Before anyone else jumps on Tricron, let''s put an end to this now.

...and just to clear up Pyabo''s error as well, Tricon2 did NOT state that chess had already been solved. He/she merely made the erroneous statement that it is possible to always win if you go first... which is, at this point in time, indeterminate.

quote: Original post by Tricon2
Actually, in chess its possible to always win... Provided you have a massive (and complete) data tree and move first.

So, let''s return the thread to its original purpose, which was to discuss the utility of chess moves.

Timkin

you can find some help in chess AI in this directory in google.

http://directory.google.com/Top/Games/Board_Games/Genres/Abstract_Strategy/Battle_Games/Chess/Software/

I believe that most or all chess programs currently evaluates each move separately and determines how much each position helps the overall tactics.

hope this is helpful in some way



Edited by - hotdog118 on February 15, 2002 12:14:40 AM

Sorry... Realized that my message didn''t really answer the topic. was in the middle of the night and my girl made me quit soda and coffee!!

The problem with just using a tree to decide what moves to make is that even though you can give the computer one move to make for each branch of the tree you''ll still end up with the player having on average 10-50 possible moves he can make per turn. The size of the tree would be enormous.

If consider an average chess game that runs from 30-40 moves. and we''ll just give each player only answering with one of 2 moves. that''s 2^40 of moves that you can attain. that''s 1,099,511,627,776 of possible moves. Now if you consider that it''s possible to store each move into 1 byte that makes it 1 terabyte of memory. and I believe it''ll take more than 1 byte to store each move. Now hopefully you''ll see why it''s not entirely feasible to just use a ''moves'' tree for a chess program.

That''s why most Chess programs use a Chess AI to consider what moves are best instead of a ''moves'' tree.

Hmmm, let me say, doing an unbeatable chess algorithm is near to impossible, it''s about as possible as quantum theory in realtime practice :\

However, you can have the computer think in a defensive and offensive way, letting allot of the thinking go towards whether the computer should perform a denfensive or offensive move.

I think the first few moves in the game are important as well, goto the library and rent out gary kasparovs collection, remember to wear a disguise though

Chess is NOT based on a 0''s and X''s theory....
Consider timed games as well... 60 seconds allowed to pull a move off or 60 minutes allowed thinking in the whole game.

Am I talking out of my ass? This is the only possible way I can think of...
p.s. What the hell is a neural network?

Actually, most chess AI systems use an "opening book", i.e. a list of the moves to start with depending on what moves the other playe makes.

When the book is useless (i.e. there are no moves which fit the current state of the board), it usually uses a min-max tree.