Hi, I started writing a chess program in freeBASIC.
http://fileanchor.com/66419-d
You can play against the computer, or use it as a chess board and program different AIs and have them play one against the other.
The AI are SUB's located in a separate file and INCLUDEd in the Main. They use a kind of automatic recognition so one doesn't have to make many changes to include one.
Graphics are non existent or borrowed because I can't draw. Documentation is absent. And the present AI is a really poor player. But this is project is really big for me and I can't begin to say how much I have already learned from it.
All the comments are welcome!
Chess program
Thank you, all!
Compared to most (if not all) chess programs, it is really just a start! (The minimum goal of the project is to beat a friend of mine... and obviously I have a long way to go even for that...) But until now I mostly wrote the chess board.
@Voltage: The algorithm is based on the control players have over the sqares. So the avriables are: control over the 9 sqares around and under the opposing king; possible decrease in opponent pieces (= my capture); how many of my pieces are under my control; how many of the opponents pieces are under my control; and how many of my pieces are under the opponents control. Plus different coefficients for opening, middle game and endgame. For now it evaluates just the first ply.
It is really only global strategy, and it is lacking maneuvering and tactics. I thought it would be a lot stronger! Before introducing more plys I would like to enhance the evaluation by throwing in some tactics... and hope for the better!
Compared to most (if not all) chess programs, it is really just a start! (The minimum goal of the project is to beat a friend of mine... and obviously I have a long way to go even for that...) But until now I mostly wrote the chess board.
@Voltage: The algorithm is based on the control players have over the sqares. So the avriables are: control over the 9 sqares around and under the opposing king; possible decrease in opponent pieces (= my capture); how many of my pieces are under my control; how many of the opponents pieces are under my control; and how many of my pieces are under the opponents control. Plus different coefficients for opening, middle game and endgame. For now it evaluates just the first ply.
It is really only global strategy, and it is lacking maneuvering and tactics. I thought it would be a lot stronger! Before introducing more plys I would like to enhance the evaluation by throwing in some tactics... and hope for the better!
Nice :) I really like the idea of having the goal of beating your buddy. Very motivating goal.
Do you do a material count for each side?
K = 100, Q=9, R=5, N/B = 3.3, P=1
Then for each given move, calc then new material count.
I know this leaves a few doors unopened, but it would at least "recommend" a queen capture if one was available.
Do you do a material count for each side?
K = 100, Q=9, R=5, N/B = 3.3, P=1
Then for each given move, calc then new material count.
I know this leaves a few doors unopened, but it would at least "recommend" a queen capture if one was available.
I haven't made a chess game, but I was doing something like this for my checkers game:
Make a copy of the board, and send it to an evaluation sub.
For each piece, check all available moves and keep a record of what happened with each move, such as capturing a rival piece, stopping in a vulnerable position, check, etc...
Then, check that pieces moves against all other moves for itself, keep only the move with the highest score.
After you have scanned all the pieces, check the final move of each piece, against the final move of all the other pieces, and take the one with the highest score.
It's virtually impossible to beat, but you can always add some "fudge" coefficients as a difficulty level.
Of course, this might not even work well at all for chess. It wouldn't really have a strategy, unless you checked the status of every piece that could actually benefit by moving this piece to some position... Boy, that could become a wildly complicated algo. lol
Make a copy of the board, and send it to an evaluation sub.
For each piece, check all available moves and keep a record of what happened with each move, such as capturing a rival piece, stopping in a vulnerable position, check, etc...
Then, check that pieces moves against all other moves for itself, keep only the move with the highest score.
After you have scanned all the pieces, check the final move of each piece, against the final move of all the other pieces, and take the one with the highest score.
It's virtually impossible to beat, but you can always add some "fudge" coefficients as a difficulty level.
Of course, this might not even work well at all for chess. It wouldn't really have a strategy, unless you checked the status of every piece that could actually benefit by moving this piece to some position... Boy, that could become a wildly complicated algo. lol
@Voltage: Yes I do material count (K = 100, Q=9, R=5, N/B = 3, P=1). But I think I messed up because I wanted to calculate the % advantage of eating, over the present situation of the opponent (so that eating a strong piece towards the end would become a must) but I think I wrote it completely the other way round (lines 180-200 of computermove).
Plus I think I have troubles in weighting the %. I'm rewriting the stuff...
@Dr_D: This is exactly how I reasoned. Only, I make a single list for all pieces and pick the best.
Then for all my moves I will make a list to evaluate all the opponent's responses using the same evaluating function (only used in reverse). And I will replicate this for some moves, completing a table (which is just a selection of all possible nodes). It is not state of the art brute force beacuse it ignores a lot of nodes, but one has to simplify...
Plus I think I have troubles in weighting the %. I'm rewriting the stuff...
@Dr_D: This is exactly how I reasoned. Only, I make a single list for all pieces and pick the best.
Then for all my moves I will make a list to evaluate all the opponent's responses using the same evaluating function (only used in reverse). And I will replicate this for some moves, completing a table (which is just a selection of all possible nodes). It is not state of the art brute force beacuse it ignores a lot of nodes, but one has to simplify...
I would like to write chess AI sometime... I beleive it can be done using backtracking (or recursive search)...
Basically, check all possible moves that the AI can make, and then simulate all possible counter moves the apponient can make, and do this recursively for X number of steps (for how hard you want your AI X> and ballance that with a reasonable playing speed X<)
The speed for such an algorithm would be... Y(number of moves), Z(number of responses), so basically ((Y*Z)^X)
but as long as you're optimizing the algorithm well, your AI should be able to run.. maybe 3,4,5? steps ahead at a reasonable speed? (That was just a guess)
Another optimization that could be made is storring the different permutations of chess boards in a file, to implement some Dynamic Programming... In effect that would make it "learn" too think faster lol
Anyway.. hope that helps
Basically, check all possible moves that the AI can make, and then simulate all possible counter moves the apponient can make, and do this recursively for X number of steps (for how hard you want your AI X> and ballance that with a reasonable playing speed X<)
The speed for such an algorithm would be... Y(number of moves), Z(number of responses), so basically ((Y*Z)^X)
but as long as you're optimizing the algorithm well, your AI should be able to run.. maybe 3,4,5? steps ahead at a reasonable speed? (That was just a guess)
Another optimization that could be made is storring the different permutations of chess boards in a file, to implement some Dynamic Programming... In effect that would make it "learn" too think faster lol
Anyway.. hope that helps
-
jevans4949
- Posts: 1186
- Joined: May 08, 2006 21:58
- Location: Crewe, England
I think you'll find that the number of permutations is too mind-bogglingly huge to make that a possibility.Lithium wrote:Another optimization that could be made is storring the different permutations of chess boards in a file, to implement some Dynamic Programming... In effect that would make it "learn" too think faster
Does anybody know how they calculate the full value of the first move, given the values of all the nodes depending from it? I was thinking of discounting the values of the nodes, by applying a discount rate to each successive move, like what it is done (for successive periods) in discounted cash flow models.
@Lithium and jevans4949: Is this what they call "pondering"?
@Lithium and jevans4949: Is this what they call "pondering"?
-
jevans4949
- Posts: 1186
- Joined: May 08, 2006 21:58
- Location: Crewe, England
I don't know a great deal about this subject, except some fairly general theory.
I suppose one way of optimising would be, after you have worked out to a depth of n-ply and made your optimum move , don't throw away the possible game states you have worked out until after the opponent makes his move. Keep the one he used, then you only have to work out one more ply.
I think I read somewhere that some algorithms give greater weight to controlling the centre of the board rather than the edges.
If you are in a position where you cannot work out the whole of another ply level, you could prioritise those states where the opponent's choice is most limited (after those that give you maximum benefit).
Trouble is, you can never tell whether there is some killer move at ply n+1 ...
I suppose one way of optimising would be, after you have worked out to a depth of n-ply and made your optimum move , don't throw away the possible game states you have worked out until after the opponent makes his move. Keep the one he used, then you only have to work out one more ply.
I think I read somewhere that some algorithms give greater weight to controlling the centre of the board rather than the edges.
If you are in a position where you cannot work out the whole of another ply level, you could prioritise those states where the opponent's choice is most limited (after those that give you maximum benefit).
Trouble is, you can never tell whether there is some killer move at ply n+1 ...
-
ShadowDust
- Posts: 274
- Joined: Oct 13, 2005 2:05
- Contact:
@ShadowDust: Wow! :-O
Now this would be reeeeeaaaaally cool! Please do! Thanx!
http://fileanchor.com/69273-r.bmp
Of course I'm changing the coordinates of the board :-)
Now this would be reeeeeaaaaally cool! Please do! Thanx!
http://fileanchor.com/69273-r.bmp
Of course I'm changing the coordinates of the board :-)