So who knows C++?

[SLH]

lolz i wrote a TTT program too. Did yours have an AI? I used jon von neumann's Minimax, which is mathematically unbeatable, so techinically speaking you can't beat my program.

In TTT it is unbeatable because of the nature of the game, however the algorithm its self isn't unbeatable.

 

[JellyWorld]

In TTT it is unbeatable because of the nature of the game, however the algorithm its self isn't unbeatable.

What do you mean????

You cannot lose a game with Minimax.

Edit: nvm I get it. Technically with sufficient computing power Minimax is unbeatable even for more complex games like chess.

 

[SLH]

What do you mean????

You cannot lose a game with Minimax.

Edit: nvm I get it. Technically with sufficient computing power Minimax is unbeatable even for more complex games like chess.

I was thinking about that, and i'm not sure that is true (i'm about 50-50 either way).

Even if you got the algorithm to explore the entire game tree (all levels, no time limit) its still working on the assumption that you will make the move that it would make in the same position (always picking the move resulting in the highest score / best outcome).

What are your thoughts?

 

[JellyWorld]

Well if you do not select the optimal move for yourself, then the value of the Computer's optimal move will be increased, so the computer will have an even greater chance of winning.

 

[SLH]

Well if you do not select the optimal move for yourself, then the value of the Computer's optimal move will be increased, so the computer will have an even greater chance of winning.

When you have a complete move tree that is the case (so i now agree that the computer will always get the best result (win or draw depending on the game start configuration), given a complete tree). When you don't then that is not always true.

 

[JellyWorld]

When you have a complete move tree that is the case (so i now agree that the computer will always get the best result (win or draw depending on the game start configuration), given a complete tree). When you don't then that is not always true.

yup. And with tic tac toe you can always obtain the complete game tree without too much computation.

 

[SLH]

yup. And with tic tac toe you can always obtain the complete game tree without too much computation.

Yeah, but i'm talking about the MiniMax algorithm generally, TTT is a very trivial problem.

 

[JellyWorld]

Minimax is the basic algorithm, but there are many enhancements which can cut down on the computing time significantly, mostly by filtering out nodes which are unlikely to produce good moves.

 

[SLH]

Minimax is the basic algorithm, but there are many enhancements which can cut down on the computing time significantly, mostly by filtering out nodes which are unlikely to produce good moves.

Yeah, i'm aware of many of the optimizations, i've implemented a checkers/draughts opponent myself. Even with these optimizations, you'd need a powerfull computer, or a VERY large database/cache to get a complete tree.

 

[JellyWorld]

most optimizations don't bother to retrieve the whole tree. btw, do you know any sites with a list of algorithms and optimizations for computer chess etc? I'm writing a chess engine for my school project, its due in august.

 

[SLH]

Sounds good, i'd be interested to see how it turns out. One of the major problems you'll face is the fact that the tree is going to be very, very wide (lots of moves from a given position). Think very hard about your use of bitboards before you start.

Here's some good sites:

http://chess.verhelst.org/1997/03/10/search/
http://www.cs.ualberta.ca/~jonathan/Grad/Papers/TR94-19.ps

 

[MjM]

I made PacMan in java. But i think java is easy to learn.

 

[JellyWorld]

Sounds good, i'd be interested to see how it turns out. One of the major problems you'll face is the fact that the tree is going to be very, very wide (lots of moves from a given position). Think very hard about your use of bitboards before you start.

Here's some good sites:

http://chess.verhelst.org/1997/03/10/search/
http://www.cs.ualberta.ca/~jonathan/Grad/Papers/TR94-19.ps

I thought bitboards were for 64-bit CPUs only? Thanks for the links anyway.

 

[SLH]

I thought bitboards were for 64-bit CPUs only? Thanks for the links anyway.

They would work better on a 64-bit CPU because of representation (for chess you need 64 bits per bitboard, one bit for each square). They can be used by any CPU though.

If you wern't planning on using them i strongly recommend researching the topic since it's agreed to be the best method of representation for that sort of game.

For example in my chechers game i used 3 bitboards, each 32 bits big (since that's how many possible piece positions there are). One board for the location of each player's pieces, and one board for all kings. Then i was able to use various (very fast) bit operations to calculate and perform possible moves and work out piece positions.

Chess is obviously more complex, but the same principes apply.

 

[JellyWorld]

yeah i read something on bitboards a few months back, better go refresh my memory.

 

[SLH]

If you have any questions i'll be happy to answer them.

 

[Cole]

Did yours have an AI? I used jon von neumann's Minimax, which is mathematically unbeatable, so techinically speaking you can't beat my program.

It was my first program through 2 days of reading about C++.
No AI was included.