For my third and final year at computer engineering, we have to do a project and work on it over 2 semesters (around 6 month). Since I do find game programming and particularly AI interesting, I thought I could base project on that. However as I have little experience with games (the only one I've done is Naughts and Crosses), I dont exactly know what to choose. I have some knowledge of C up to linked lists, etc, and I have recently started learning C++ on my own. I would be very greatful if you could help me to come up with some ideas for my project. Something that is feasible for the final year, yet not too complicated to take forever to finish it. Thank you for your time [edited by - pars on September 30, 2002 5:54:29 PM]

I say go for tetris. I have made about 4 tetris clones (2 were in 2d , the other 2 were in 3d) and have to say that tetris is mighty easy to program. Now for the AI. Use whatever AI scheme you like best (I choose nueral nets) and make the computer learn to play tetris on its own. With the right AI you can make the computer never lose (i.e. there is no sequence of pieces such that no matter how you placed them you would eventually lose). This is NOT easy to do. My nueral net still doesnt play forever, but it can get scores in the 3 to 5 million range =]

Thats my 3.1415... cents and i want exact change

[edited by - jplocster on September 30, 2002 5:34:31 PM]

pars:

How much time will you have to spend on your project? Days/Hours?

jplocster:

Neural nets for Tetris... neat!

Could you write a few sentences about how you trained your networks please? I''m sure many of us would be interested. I''d also be interested to know the topology of your network. What the inputs are, the outputs, and how many hidden units. Thanks.

fup:

If I want to give an average I would say around 3 hours (maybe more) a day, since I got other subjects. However, it all depends on how complicated the project will be. I will spend more time on it if the game is more complicated. I will try to work on it everyday.

2D Tetris sounds like a very good idea, particularly if you do the whole game; i.e., GUI, AI, sounds, multiple levels, etc. I''d estimate that you could spend about 150 hours over 2 semesters (if you didn''t want your other subjects to suffer) and this should be plenty of time of put together a tetris game. Just make sure you go through all of the stages of proper development. Write a design spec, user spec & function spec. These can all form part of your final report for the subject, so don''t see them as a waste of time, but rather an early start on the report! You''ll be able to get plenty of help from the various forums here at GameDev and that should make things go more smoothly for you.

Good luck!

Cheers,

Timkin

My suggestions would be:

Pacman: For that you would have to learn stuff like:

Finite State Machines
Pathfinding
Data structures (graphs)

Boggle: This is a popular word game. To create an AI that searches for the maximum score you would learn about:

Data structures(trees, hash tables)
Genetic Algorithms
Other search algorithms

If you want something more ambitious, how about using an evolutionary approach to evolve a Chinese Checkers player (or Othello). This has a much stronger AI base and it would be an interesting path for you to travel. You would have to learn about:

Minimax algorithms
Neural Networks
Genetic Algorithms.
Data structures

Learning enough about these subjects to produce such an AI is certainly possible given the amount of time you have. If this interests you, you would be wise to buy David Fogel''s book: Blondie24, or at the very least read his papers. (or email me, I have a copy of the article David wrote for the ''Intelligence'' journal that he was kind enough to send me).

The benefit of the latter two suggestions is that the front end is easy to program - no troublesome graphics to learn or draw!

I suppose, in the end, it''s all going to come down to your programming experience. If you are confident about your skills then you can tackle something more ambitious. If not go for something simple.





ai-junkie.com

Thanks a lot for your help guys. If you have any further suggestions Im more than willing to hear them

[edited by - pars on October 1, 2002 8:00:18 AM]

fup:
Could you write a few sentences about how you trained your networks please? I'm sure many of us would be interested. I'd also be interested to know the topology of your network. What the inputs are, the outputs, and how many hidden units. Thanks.

Sure! I am not that great with NN lingo so please forgive if i use the wrong jargon =]. The net was trained without supervision (although the game gives you the ability to give the AI "hints". There are 9 inputs that I came up with(and i am sure there are many others that could make it even smarter):

How many occupied squares are on the board
The highest occupied location
The average occupied location
The number of pits which can only be filled by the line piece
The deepest pit mentioned above
The number of flat surfaces (at least 2 blocks wide)
The largest flat surface
The number of holes (unoccupied spots covered by pieces)
The Lowest unoccupied spot

Those were the inputs and the hidden layer really just computes a best board state (only one hidden layer).

There is one output which is an index into a list of possible moves.

It is of course a little more complicated than this, but even this simple model can get awesome scores with only a few days of learning. =] Any suggestions on how to improve it would be appreciated!

jplocster@hotmail.com



[edited by - jplocster on October 1, 2002 12:42:22 PM]

[edited by - jplocster on October 1, 2002 12:42:49 PM]

[edited by - jplocster on October 1, 2002 12:43:35 PM]