I''m going to do a big work for finishing high school (well, gymnasium actually since i''m from europe) next year. I have about 6 months time for it (for working out a presentation and a product), and additionally ~3 months for learning some stuff on my own now if necessary (which will be learning C++ for me). Of course I can''t work full time those 6 months, more like 80hrs schooltime and at home of course. We can chose ANY subject, but we have to do something on our own in addition to just bringing material together and telling something about the subject. My idea is the following: I''m going to chose the subject "artificial intelligence" and I will program a chess computer which can handle basic to semi-advanced chess tactics. It doesn''t have to be a genious nobel-prize winning work, it should just be showing how an AI can be built up (i''ll include something like a "think" output from the chess computer) and it should be at least a BIT challenging for an average chess player. My questions are the following: - i''ve worked with Visual Basic and QBasic quite a bit in the past, but i''ll do this project in C++. Since my C++ knowledge is not that good yet (i know the basics, how to do arrays, file outputs, cout and cin etc. I can basically do simple console running programs, nothing with graphic interface yet), i''m asking myself if those ~3 months will be enough to gather enough programming knowledge for my project? I have a book to read, but it''s not that great as I found out (i already read a beginners book which was good, but not advanced). Any experiences about how good at C++ i have to be for programming a chess computer? - I have no AI experience at all yet, but i am very interested and i can learn a lot if i have to (and i will have to ). I just want to ask one general question, so i won''t get to a point on which i''ll have to say "oh my, what have i got into here!": Is it VERY hard to code a good chess computer? thank you!

all I can say is choose a different project NOW!
Artificial Intelligence is an extremely difficult field. I don''t think 6 months is enough to learn C++ enough to do any substantial AI project beyond TIC TAC TOE, and deffinitely not enough time to learn graphics programming.

You could stick to Visual Basic or QBasic to work your project. You may have enough time to do something with Genetic Algorithms (www.generation5.org is where I learned about GA)

Chess is an extremely difficult game to program even with a random AI. I would do a simpler game, I mentioned TIC TAC TOE before, or possibly an AI Snake, Blackjack, or Poker. With a card game, you could even do an analysis of most probable outcomes (ex. if you''re playing 5 card draw poker, and you through away 2 cards, what are the odds that your next 2 cards are kings).

hm, i see your point, thanks. But isn''t there something else that I could do than e.g. Tic Tac Toe? I''m not a TOTAL beginner in C++, and I don''t need to do a lot of graphics for this i think (i''ll just use windows GDI). Besides i can learn quite fast i think. What else can I do if tic tac toe is maybe a little too easy for this project and chess is too hard?

I agree with capt_midnight, chess is not something youd want to get into. Chess is a extremly difficult game to comprehend as it is. Adding AI to it will make it even worse.

I think there are alot of other fascinating projects you could do though. Why not make a program that finds ways out of labyrinths (wosspelled), solves math problems or something like that. Or even avoidance & pathfinding? Maybe a pacman where the AI is to play the game?

To do some AI for a complex game like chess will be a pretty difficult task I guess. And C++ itself isnt a simple language, I doubt you can just learn it from a book, you need a lot of experience to learn when to use which feature. You might be able to write a chess playing agent in a elegant way in OO-style, but I think for such complex task you would need more experience than you can gain in only about 3 month.

I did some work on Neural Networks for my final exams as well. But I started to be interested in that theme already 2 years earlier and started systematically to learn that stuff about 1 year earlier. Then I had about 1 year to work on my project. ( I already began coding 4 or 5 years earlier, although it might have been more intensive, but at that time my learning wasnt aimed at some work, it was just for fun )

You can read the german text of my project here : http://www.lampel.net/johannes/bll137.html

Ugh. Chess AI is hell. The first time I made one, it looked over every possible move that could be made for the next 30 moves, and calculated everything from there. It was unbearably slow, but it always won. Because I suck at chess, but still..


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Flamebait of the week club! This weeks flamebait:
YOUR BIBLE IS FULL OF LIES!

EXTREME MODERATOR COMPLIANCE!

quote:

---

Ugh. Chess AI is hell. The first time I made one, it looked over every possible move that could be made for the next 30 moves, and calculated everything from there. It was unbearably slow, but it always won. Because I suck at chess, but still..

---

First off, you''re lying. No program known to man can look 30 moves ahead in the FULL WIDTH search. Maybe you are talking about the search including quiescence search and extentions, but you''re not talking about full-width search. That is simply impossible on today''s hardware. Even with the best programs, on the fastest hardware, at a long time control, we''re only talking MAYBE 14 or 15 ply. Ruffian is the strongest amateur chess engine currently publicly available, and it can *only* search to a depth of 12 in 2 minutes 38 seconds on my PC (P3 733). So on faster hardware it might be able to hit 14 ply in a reasonable game time (say, 3 minutes). It takes 15 minutes to get to 14 ply on my machine.

Anyway, to the original poster. You say you want to make a chess program that is capable of challenging the average chess player. Almost any chess program out there (except the most very basic, basic ones) will be able to thrash the average chess player, and in fact it will give a good beating to anyone less than a candidate master most of the time. So as far as creating a chess program goes, accomplishing what you want shouldn''t be hard. However, creating even a simple chess playing program is not trivial, but you won''t need anything more than a simple program, so that is the good news (if you decide to go with chess).

One advantage you have if you choose chess is that you will have a great amount of resources to learn from, because computer chess has been a topic that people have been studying for several decades. There are plenty of freely available websites that describe the basic features of how most modern chess programs work. There are many open source chess programs that you can view the complete source code of. There are also message boards and newsgroups that are solely dedicated to computer chess. There you can find all kinds of people who have programmed chess, and they can answer any question you have (most likely). There are even some authors of commercial chess programs that post to some of them. So any question you, as a beginning chess programmer, will have should be easily answerable by many people.

I have written a chess program, and having done so, I can say that it is a lot of hard work, but I don''t think it''s something you should totally avoid if you''re interested in it. Creating the AI part of a simple chess program (like you need) is not any more difficult than creating the AI for a tic-tac-toe program. The reason is because they use the same algorithms for the most part. They both use a recursive search to look ahead as many moves as the program can, and then it evaluates the game and picks a move. The hard part of a chess program is not "AI". The hard part of a chess program is getting started and writing things like a function that will generate a list of legal moves that the program can play, and a function to make that move in your game, and a function to undo the move in that game. There are a few more things that are needed, such as a function to determine if the king is in check so you can determine if the game has ended, or if an illegal move has been played. Other than that, it''s not too hard, but those functions are certainly not easy to write.

I have been learning about computer chess since I was in high school (I''m 21 now), and at this point I could probably write an entire program that would beat everyone up to master level in one sitting if I had to (but it wouldn''t be fun).

I think the two biggest obstacles you will have will be:

1. Writing a bug free legal move generator (this will only be hard in chess, and maybe checkers. in tic-tac-toe and connect-4 this is simple)
2. Understanding the search algorithm

I would suggest diving in, reading websites about chess programming, taking a look at some simple chess programs (Tom''s Simple Chess Program is a good one), and seeing if any of it makes sense. If it doesn''t, try to understand it, and then go ask questions. There are tons of people on the places below that will try to explain how things work. If you try and are completely overwhelmed, maybe you could try a simpler game. Part of the problem will probably be that you are having a hard time understanding the search algorithm while you''re also trying to write a legal move generator for chess, and you''ll feel overwhelmed. So it might be a good idea to try a simpler game. Checkers is simpler than chess, but there are still a few tricky things in it (like how a piece can jump multiple enemy pieces, which can be hard to program, especially if you''re new to C++). You could also try tic-tac-toe, or maybe connect-4.

Basically, my advice to you is to give chess a look if that''s what interests you, and if that mountain is a bit too steep at this point, give tic-tac-toe or connect-4 a try first. That way, you can learn how the search algorithm works, and it will be simple (well, simpler than chess) to write a move generation function, so you can focus on learning how the AI works. Think about it. In tic-tac-toe, to generate a list of legal moves you just look at every square and say, "if this square is empty, then putting a piece here is a legal move, so add this to my list." Chess gets WAY more complicated, and there are a lot of special cases to consider (capturing a piece, castling, pawn promotion, pawn promotions that are also a capture, en passant capturing, etc.). So if that sounds like like too much, try a simpler game first, then learn how the minimax search algorithm works and write a simple program, then learn about the alpha-beta algorithm, which is an improvement upon minimax.

If you''re interested in chess programming:

www.talkchess.com is without question the best message board going for computer chess.
Google Groups will let you read newsgroups. Try rec.games.chess.computer at Google Groups and they can answer questions also.
Gamedev''s Chess Article is good also.
Creating a Digital Grandmaster is a good chess programming website by James Swafford.
Bruce Moreland''s Website has some very good articles on various topics relating to computer chess. He is the author of one of the strongest programs in the world.
This page has some good links (some to the links I already gave).
This page has a list of many chess programs. The ones with the red "S" next to them come with the source code. As you can see, there are some in many different languages.

And as always, a google search for "chess programming" or "computer chess" will give you a lot of results. And this forum is also helpful.

Good luck,
Russell

connect-4 sounds like a good idea too!

[edited by - tfinazzi on December 22, 2002 1:31:03 PM]

Don''t listen to these duffers who tell you not to do it -- go for it! And in general, ignore any advice that takes the form of "I did that once and it wasn''t worth it." Anyone who says that is clearly lacking a good perspective on how they themselves learned about a subject, in this case artificial intelligence.

Learning is about going down the wrong paths.

starchy may be right ... I think it depends on your teachers view. If you do a documentation of your work, where you show what you did, what you learned and which approaches you tried, some teachers may still give you a good mark, although you maybe completely failed to finally reach your aim. Other teachers are a bit ignorant and just want you to get where you wanted to get according to your plans.

I think you cannot really fail as long as you really work on that topic and show what you did. Although that might be difficult with this c++ learning period, maybe you have to focus more on the philosophical background in this case, this might be more save.