Anon. poster is right. You cant make an unbeatable chess AI, as to be certain of winning the computer would need to look at all the possible boards that could develop out of its next move- my maths is pretty awful but one of my lecturers did the maths and and showed us that to be certain of winning the game the computer would have to spend an amount of time long relative to the age of the Universe on the first move..
The solution is (as is mentioned above) have a number of set opening moves, and every time the computer has to move subsequent to the first move it only looks at the boards that are seven or so moves ahead- and then could just use a simple aglorithm to calculate the total value of the peices left on the board to find which move is going to lead to the most preferable set of boards..
Jon


In OOP no one can hear you scream..

quote: Original post by Tricron2
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 =)

Tricron2 might have gotten the "solved" designation from me on my site. I put chess in the "solved" category with checkers and tic-tac-toe more because there have been so many papers and treatises written on the subject. There are a thousand ways to approach the game but no way (yet) to truly "master" it. That doesn''t mean that an AI can''t be written to beat 99.99% of players--look at any "average" chess program. Go isn''t there yet but it will follow without a doubt.

For the record, games like Go and chess are extremely complex but they''re clearly "solvable". The terrain is flat and the complexity comes from the way the pieces move and the constraints of the board. I would argue that the most simple wargame, however, is infinitely more complex than either. To paraphrase Eric from a GDC several years back, "Chess is hard, Go is harder, wargames are hard cubed".



Ferretman

ferretman@gameai.com
www.gameai.com
From the High, Cold, Snowy Mountains of Colorado

Let''s think about the implication of an "unbeatable AI"
in games. After all, that''s why we''re here right? To
make games, I mean.

Sure it''s interesting to research the possbility of
an "unbeatable AI" for any given game, but, well, it''s
of ZERO practical use.

Why?

The "unbeatable AI" won''t be very entertaining to players.
Games are meant to be fun. People have fun when they "win".

There is no point in playing a game in which you are
100% certain you are going to lose because the game
has "unbeatable AI".

You can make your AI as hard as you want. The feeling of
accomplishment for beating it will be great. Just don''t
go to the extreme make it "unbeatable" (even if it''s
possible).


Premature optimizations can only slow down your project even more.

I think that chess can be solved... Eventually ^_^ Thing is, you shouldn''t look at the "game" that is played, or the moves that have been made, but rather towards possible layouts of the board. And really, you can cut down a *lot* of ''possible'' sets, becuase they are either impossible to get in-game, or terribly unlikely (even because it would put the computer at a disadvantage). And then you wouldn''t have to store them all, but rather store a "few favourable" positions that the computer should try to attain at certain points during the game. When the player moves a "different" piece, the computer would just have to search for a new "favourable" set that can be attained, and move towards that set...

Thats about the same approach as a real chess player uses (or at least, those that I know). You try to move your own pieces into such a formation that the enemy can''t do a thing. Every player has his own set of preferred formations, but most good chess players know a lot of them. Usually, they aren''t fazed much by what the enemy does. When the enemy takes a move, they just calculate the amount of time it would take the enemy to get a favourable position (more or less), and compare it to their own. When they are "in the lead", they try to attain their positions. When the enemy is in the lead, they try to "dismember" the enemies formation, buying them enough time to get to their location... Etc. etc.

So... You should be able to do with a bit less then 1 terrabyte of memory ^_^

-Maarten Leeuwrik
=================
[Illiad] J.R.R TOLKIEN ACHIEVES 40,000 RPM IN GRAVE

quote: Original post by Ferretman
For the record, games like Go and chess are extremely complex but they''re clearly "solvable". The terrain is flat and the complexity comes from the way the pieces move and the constraints of the board. I would argue that the most simple wargame, however, is infinitely more complex than either. To paraphrase Eric from a GDC several years back, "Chess is hard, Go is harder, wargames are hard cubed ".

In the interest of giving credit where credit is due, Bruce Wilcox (at 3DO at the time),
while working on the game ArmyMen presented a lecture at GDC entitled
"Chess is Easy, Go is Hard", in which he discussed his AI work for the game Go. After attending
Bruce''s excellent lecture, I got into a usenet discussion with someone who thought that
designing and building AI for computer wargames was easy (of course he had never done one)
and during the conversation I offered up the above derivitive to Bruce''s orginal title.

Steve must have been lurking there.

Eric