Chess program

User projects written in or related to FreeBASIC.
fabrizio
Posts: 73
Joined: Sep 29, 2006 13:39
Location: Roma, Italy

Chess program

Postby fabrizio » Oct 02, 2006 8:10

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!
seph
Posts: 356
Joined: Apr 27, 2006 14:49

Postby seph » Oct 02, 2006 18:44

I won! =D
Dr_D
Posts: 2430
Joined: May 27, 2005 4:59
Contact:

Postby Dr_D » Oct 02, 2006 23:45

Nicew work!
Voltage
Posts: 110
Joined: Nov 19, 2005 7:36
Location: Sydney, Australia
Contact:

Postby Voltage » Oct 02, 2006 23:51

Me too. Nice start to a chess engine...

It misses immediate captures though.

What algorithm are you using to evaluate moves?
fabrizio
Posts: 73
Joined: Sep 29, 2006 13:39
Location: Roma, Italy

Postby fabrizio » Oct 03, 2006 7:24

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!
Voltage
Posts: 110
Joined: Nov 19, 2005 7:36
Location: Sydney, Australia
Contact:

Postby Voltage » Oct 04, 2006 0:51

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.
Dr_D
Posts: 2430
Joined: May 27, 2005 4:59
Contact:

Postby Dr_D » Oct 04, 2006 1:32

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
sir_mud
Posts: 1401
Joined: Jul 29, 2006 3:00
Location: US
Contact:

Postby sir_mud » Oct 04, 2006 3:20

@Dr_D: reminds me of an Othello game I had for DOS on a 386, It had a impossible setting... i don't know if it was really impossible because it took well over an hour to 'think' and i got tired of it and restarted :p
fabrizio
Posts: 73
Joined: Sep 29, 2006 13:39
Location: Roma, Italy

Postby fabrizio » Oct 04, 2006 7:42

@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...
Lithium
Posts: 298
Joined: Jun 06, 2005 17:53
Location: Nova Scotia, Canada
Contact:

Postby Lithium » Oct 08, 2006 18:02

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
jevans4949
Posts: 1158
Joined: May 08, 2006 21:58
Location: Crewe, England

Postby jevans4949 » Oct 09, 2006 4:00

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

I think you'll find that the number of permutations is too mind-bogglingly huge to make that a possibility.
fabrizio
Posts: 73
Joined: Sep 29, 2006 13:39
Location: Roma, Italy

Postby fabrizio » Oct 09, 2006 7:17

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"?
jevans4949
Posts: 1158
Joined: May 08, 2006 21:58
Location: Crewe, England

Postby jevans4949 » Oct 09, 2006 10:58

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 ...
ShadowDust
Posts: 274
Joined: Oct 13, 2005 2:05
Contact:

Postby ShadowDust » Oct 09, 2006 23:25

If you like I'll make a 3D chess board and 3D pieces, specifically for your game ;)

Image
fabrizio
Posts: 73
Joined: Sep 29, 2006 13:39
Location: Roma, Italy

Postby fabrizio » Oct 10, 2006 12:17

@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 :-)

Return to “Projects”

Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 10 guests