honestly, a chess program is something very very [...] very ambitious to start with. maybe 4-in-a-row is a - also very difficult - better start?
well, you decide :-)
here are my two cents:
game programming needs an algorithm which builds a tree of all possible moves. each node of the tree (say: position) is then subclassed by each possible move from this position, and so on. pure capacity and computing power determines the depth of the tree. each end-node of the tree is then judged by the computer, and it simply tries to reach this position by following the path down to the best node.
(simplified description ;-)
the problem is that the tree gets very very big. the science of programming a chess-engine is to determine - as early as possible - which branches of the tree are not worth following. if you are not looking for a dissertation, i'd say that's beyond the scope of us "normal" coders. (the other challenging part is telling a good position from a bad one)
anyhow, my point is the following - it's the wrong approach to determine the level of computer play by it's computing time.
instead, you should specify how deep it calculates the game tree. later, when everything works (more or less), you can still cut calculation time down, but as a start, you should restrict the tree, not the runnign time of a thread :-)
btw: why am i recommending 4 in a row? because all pieces are equal (no pawns, kings, queens,...), the number of possible moves per situation is limited (7, german rules), and so is the number of movements per game (42, german rules). but: the strategy itself is exactly the same, start from a certain position, compute all moves, find the best and go ahead :-)
good luck & lots of fun, jan
Joined: Feb 03, 2004
oops, just reading that you already wrote a chess program.
Joined: Apr 11, 2005
Thanks for the info... I have a nice working GUI and my program uses rotated bitboards, in conjuction with alpha-beta pruning in NegaMax form.
I'm also using deBrujin multiplication method to basically get log2 of a number which is necessary when using bitboards (This actually almost doubled program speed)
It's evaluating around 2.2 million positions per second, which is around 6 to 7 ply depth for an average position in about 30 seconds, but when you get down to 3 pieces the ply can be boosted upto 10.
I've implemented checkmate and stalemate too, so it will force mate as quick as possibly if it can.
As you correctly said the nature of search is exponential... What I would like to do is set a fixed time for the computer to search it moves... There is a nice way to do this, first search depth 1, then get the best move. Then depth 2, get best move, then depth 3, and so on... Keep going till you run out of time, and then output the last best move found.
It might seem like a waste of time searching to those previous depths, but if depth 6 takes 20 times as long as depth 5, and same with depth 5 to 4... You will be only increasing the time taken by a small amount, so its almost negligible.
My question is if I use a timer in the background while I search depth 1, depth 2, depth 3,... will the timer slow down the search at all, or is it just a negligible amount?
I think internally a timer just sleeps for some amount of time which ought to be very low overhead. What will you have it do when it wakes up? Interrupt a thread that is looping while not interrupted? That makes sense.
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi