Programming question (not homework related)

Ivan

Some friends and I were discussing what we were going to do next year for our project.

Its basically write any program of any type, in any language.

We were just discussing how difficult/simple a chess program would be.

I was just saying that you could write a simple procedure which would store each valid move for each piece and then when its the computers turn it would just apply this procedure to see what valid moves it could make.

Then based on a set of values for each piece, i.e. 1 for a pawn, 3 for a knight, 10 for a king etc. etc.

The computer could predict its best move. Then if you wish to increase the AI abilities you could allow it to apply this procedure for you still during its turn, and then again for itself up to N turns.

Then again anaylse the possible outcomes and pick the move which would result in the best gains. I would also add some random element so the AI cannot be predicted and so you dont end up with the exact same games when the AI is told to play against itself.

Can anyone see any reason why it wouldnt work?

I know that a chess program has been something that programmers have worked on for years to get them to beat chess masters and therefore it would be one of the hardest programs to code, but I think this simple procedure (although prone to bugs) would be pretty effective.

Any thoughts?

Oh yeah, this would probably be done in C++ although I think Java might be pretty fun either.

Talliesin

One of the big problems with this basic design would be how you determine how good a position is. While mating is obviously 100% good and being mated is obviously 0% good, for positions in between it can be harder to work out.

Material advantage will be the easiest axes to calculate (use the traditional 9pawns == 1queen etc.) but tempo and position will be tricky. Of course you may choose just to ignore those parts of analysis, you will still have a good program.

I'd advise you to code in some of the most common openings and their variations because:

1. Your program is unlikely to do better than a few centuries of the best chess-playing minds in the world analysing them.
2. The openings offer the most permutations, and hence the most computation needed to make a decision.

.

One other idea would be to have it work with a clock, it might allow itself to "think" more when it has lots of time.

yossarin

why not do draughts as a basic version so you pass before you get too fancy?
it'd be the same graphics, object relationships, interface, etc,

when you had that built you could build a new AI for chess and just plug it in instead of the draughts-engine part.

bonkey

Originally posted by Ivan
Then again anaylse the possible outcomes and pick the move which would result in the best gains.

The "best gains" are usually positional, rather than simply moves which take pieces. The problem is in determining an algorithm which can determine what consitutes a good position.

Draughts isnt much easier in terms of that logic.

A much simpler problem to resolve is something like Connect4, where most of the advantageous patterns can be relatively simply determined threough pattern analysis.

jc

Evil Phil

Originally posted by bonkey
The "best gains" are usually positional, rather than simply moves which take pieces. The problem is in determining an algorithm which can determine what consitutes a good position.

One way to do this would be the ability to move on from that position. If there is lots of options then its good, if not then its bad. You could also take into account the inverse of this, if it limits the other player more than me then its also good.

Ivan

Just because the computer cant "see" positioning properly wouldnt necessarily make it a bad AI.

Its ability to make the best move for itself, i.e. resulting in the biggest "gains" or if it gets desperate enough the least "losses" and predict your best move and its best counter for that would give it a great advantage. That said, if you do not carry out its predicted best move, might throw the computer off. But I'm sure it could still pick up.

As for draughts, this is all hypothetical so far so I just picked chess because thats what we were discussing.

As for multiple options - if you assign a value to each piece from 1 - 10.

1 : Pawn
3: Knight
3: Bishop (+1 if you have a rook)
5: Rook
9: Queen
10: King (although you'd have to have a safety here, in case it tried to trade a king for its opponents queen and a pawn)

The bishop + 1 thing came about when we started discussing which piece was better a knight or a bishop. And it was said that the bishop is better if you have a rook to back it up.

For determining a good position. A move which allows you to take a move next turn, or turn after that without exposing your flank is a good position and also you could have a database of "good moves"

A timer seems like a good idea to prevent the computer from killing itself with calculations, but it wouldnt really be fair to say :
Right think about it and then take your best move after 30 seconds or whatever (I know thats how most people play the game but this is a computer we're talking about)

The impression I get from you Talliesin is that the only "real major difficulty" is in teaching the computer the difference between taking a valuable piece but losing a good position and vice versa.

Most common openings list is fair enough, I would expect the computer to have a database of moves such as Castling etc.
But you'd have to write the code so that the program wouldnt try to castle into a bad position.

However as part of the games main code you'd have to write a list of rules. I.e. a pawn can only move forward 2 spaces when it is taking its first move.

Now these rules would apply for the program as well as the player so that is probably a large section of the AI completed right there, no?

Any suggestions on language?

We were also discussing using Open GL and do a 3-d interface but that really is being complex for the sake of being complex, and you'd probably only get the interface done by the end of the year.

Another thing is, could you program the AI to seek specific patterns, like in Connect4?

I.e. Teach it that having your king protected by a diagonal line of pawns is good, as this is a strong defence and yet allows manoeuvrability etc. etc.

Talliesin

Originally posted by Ivan
As for multiple options - if you assign a value to each piece from 1 - 10.

1 : Pawn
3: Knight
3: Bishop (+1 if you have a rook)
5: Rook
9: Queen
10: King (although you'd have to have a safety here, in case it tried to trade a king for its opponents queen and a pawn)

You'd have to give the King a much higher value than that. At least 50 (probably simplest just to give it the highest possible value - unsigned int(-1) for instance).

The bishop + 1 thing came about when we started discussing which piece was better a knight or a bishop. And it was said that the bishop is better if you have a rook to back it up.

Get a good chess book if you want to do more than just the simplest equivalences. Around 3.5 would be more accurate for the Knights and Bishops, but they vary in value according to whether you have an open or closed position. Also a bad bishop can be worth little more than a pawn, a good bishop can be worth as much as a rook.

For determining a good position. A move which allows you to take a move next turn, or turn after that without exposing your flank is a good position and also you could have a database of "good moves"

What about the move after that, and the move after that...

Computers can think ahead far more than most players, and can therefore reasonably work out all plausible plays for the next 14 or so ply. Humans learn to judge the positional strength because it allows them to make inferences about what is likely to occur further along the game than they can imagine. The latter is the trickiest part to develop an algorithm for.

A timer seems like a good idea to prevent the computer from killing itself with calculations, but it wouldnt really be fair to say :
Right think about it and then take your best move after 30 seconds or whatever (I know thats how most people play the game but this is a computer we're talking about).

Well the normal way to play is to have a set amount of time per 24 moves, which allows you use quick "obvious" moves to gain more time for later. Letting your program determine "obvious" moves is pretty hard, and the disadvantage it would have there would offset the advantage it would have in more complicated positions.

The impression I get from you Talliesin is that the only "real major difficulty" is in teaching the computer the difference between taking a valuable piece but losing a good position and vice versa.

Nope there are a whole bunch of other difficulties. However that's the primary problem to solve at the "big picture" level.

Most common openings list is fair enough, I would expect the computer to have a database of moves such as Castling etc.
But you'd have to write the code so that the program wouldnt try to castle into a bad position.

No, castling is just another move like any other (of course there are extra rules like not being able to do it if you've move the King in that game etc.) I mean the well-known opening sequences like Ruy Lopez, Queens Gambit, Sicilian, etc.

However as part of the games main code you'd have to write a list of rules. I.e. a pawn can only move forward 2 spaces when it is taking its first move.

Now these rules would apply for the program as well as the player so that is probably a large section of the AI completed right there, no?

That's not the AI, that's the model that the AI works in. The AI isn't even begun when you have a system that only allows legal moves.

Any suggestions on language?

Gah, don't even try to answer that question until you have a good idea of what your basic structure is going to be, then use a language that suits that job.

We were also discussing using Open GL and do a 3-d interface but that really is being complex for the sake of being complex, and you'd probably only get the interface done by the end of the year.

One possibility is to first define an interface for describing chess positions and moves and then on group of people can build an Open GL interface that uses it, while another develop the Game AI. If you define your interface well then it should be possible for both groups to work in complete independence. Personally if I was examining the project I'd be more impressed by a teams ability to do that than in anything else (it's a very valuable skill in large real-world projects).

Another thing is, could you program the AI to seek specific patterns, like in Connect4?

Looking for pins, forks and skewers is valuable. Knowing how to advance pairs of pawns is very valuable.
However the gains you make in increasing it's ability to find good positions might not balance out the extra computational time it needs to do it. Sometimes brute-force works best.

Evil Phil

Another thing is, could you program the AI to seek specific patterns, like in Connect4?

In connection with a database of common openings it could also recognised the patterns of an apponents opening, like Bishops Gambit and base its stratagies on that (again from a DB?). This could reduce processing time as it would limit the programs reponses. But then you have to recognise a stratagy change and match it.

Any suggestions on language?

I think at this stage design methodologies are more of a concern, worry about the language when you have some idea of what you're going to be coding for.

hussey

You could look at a chess program as essentially a complex search program

one such heuristic for chess you be MiniMax

this is for a two person search (you + opponent)

you can look at different levels to represent game-turns.

One wants to MINimise oppents points(how good board from their point of view) and MAXimise your points

e.g. in X+0's game .. your turn is first .. you have three choices
(as rotations are the same)

X                                   Y                            Z
__|__|__  ........... and       __|X_|__              X_|__|__ 
__|X_|__                        __|__|__              __|__|__
  |  |                            |  |                  |  |

let board postions be
A1 A2 A3
B1 B2 B3
C1 C2 C3

now from this state you can work out which is the best move based on the states on the board

you could search through n levels, if n was 1 (as in you can only look at present state) then choice X would be best
based on points system .,.. one system could be possible winning combinations .. in this case X would have 4 {{A2-C2},{B1-B3},{A1-C3},{C-1-A3}}, compared to Y's 2 {{A2-C2},{A1-A3}} and Z's 3 {{A1-A3}{A1-C1}{A1-C3}}.

if N was 2 (look at opponets move), you would work out the points on oppents move, a few points system's could be
Maximise your winning combinations (as above) .. Max(n)
Minimise components winning combinations .. Min(m)
a combination of both H(n)=Max(n) - Min(m) .. as in the difference between the two

if N was 3 or more you could intoduce a Prunning System, as in dont search what oppenent/you never go into etc

couple of links

http://www.cs.vu.nl/~aske/Papers/csn.pdf
http://www.cs.berkeley.edu/~wilensky/cs188/lectures/Two-PlayerGames6topage.pdf]
http://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

Martial_Law

Hello Ivan,

I hear you are trying to write a Chess game!!! are you mad lol

I am a third year Programming student in Carlow IT and I am writing a 3D chess game with AI in VC++, OGL and 3D Studio Max for our project for third year.
You have a lot of hard work on your hands, its not an easy task...especially the AI, send me an e-mail and i'll send you a copy of my research report for Algorithms on Chess AI, I'd go with Aplha-Beta Pruning and Quiescence search. You'll need to investiage trees - game tree, your data structures (are you going to use 8x8 array or Bitboards...)

If you want any help send me an e-mail to com30001@itcarlow.ie
I hear you are in Carlow IT so send me a pegasus.

Martial Law

Martial_Law

As for Draughts being as easy to program as chess, that's not true.

In draughts:
you have up to about 8 possible moves in total at any one time.
so the complexity for draughts is 8^N ply

In chess
you have say maybe 20 moves at the start of the game, 100 moves are the middle of the game and maybe 8 moves at the end of the game, so if we give an average of about 35 moves for possible position, the complexity for chess is 35^N ply

for a 6 ply search 35^6 = 1.8 billion possible moves for looking 6 moves ahead using MinMax Algorithm.

Using Alpha-Beta, there are some moves that are completely outragous and you'd never take them, so in this way you can "Prune" them off the game tree based on the heuristic score. You assume that your opponent is playing as good as you are.

If the score is "Too Good" then you are too anxious, if it is too bad then, you may discard it ("prune it"). Using this approach you can reduce the size of the game tree to 2^(35^N)^1/2

again for a 6 ply search...about 50,000 moves.

To see which move is better than another, you need to know the board heuristics e.g. of some possible board heuristics are

Material Balance: number of pieces for both sides
Mobility: how many moves does the side to move have
King Safety: how easy is it to check your king
Pawn Heuristics: ...
Pawn King Heuristics
the list goes on and on...

You evaluation function will be the hardest to program. It took me since before Christmas just to get all the legal moves for chess and put it into a data structure for each piece saying where it can capture, move and protect now I am doing the AI.

You say you want to use C++ or java

if you had something like

Sturct Board
{
WhitePawn
BlackPawn
WhiteKnight
BlackKnight
WhtieRook
BlackRook
WhiteBishop
BlackBishop
WhiteQueen
BlackQueen
WhiteKing
BlackKing
}

Each of those could be a structure that contains a list of positions

struct WhitePawn
{
int X
int Y
List of possible moves
}

I would advise you to really think about the data structure you are going to use, how you are going to calculate the legal moves for each piece, how you are going to store them.

After that you need to generate the board heuristics, and have an overall value for the board based on the above heuristics.

Anyway...I could go on all day...

If you want some help give me a buzz

Martial Law