Author: Renze Steenhuisen
Date: 07:57:08 04/20/04
Go up one level in this thread
On April 20, 2004 at 10:47:09, James Murphy wrote: >Hi, > >I have written a two player chess program in Java and I am in the process of >evaluating it i.e. performing tests and measures on how well it accomplishes its >objectives. Since one of the objectives of the program is to play chess, an >obvious evaluation would be to porve that the program actually does play chess. >To do this, I would have to establish some correctness properties of a >chess-playing program (for a particular input, a certain output is exptected) >and prove that my program holds true for them. I believe the correctness >properties of a chess-playing program are: > >1) Pieces can only move and capture in certain ways; illegal moves are not >permissible >2) Check requires a player to move out of check >3) Game terminations (checkmate/stalemate) should be correctly detected > >Can anyone suggest anymore if there are any? > >There are two ways to prove a chess program is correct; testing and formal >proofs. Full testing is impractical as not every input can be tested against >every output because it would take too long (10^38 seconds I think. Not sure if >thats right). Therefore equivalance testing is used where we say that if a piece >passes a move test, it will pass for a similar range of values on the chess >board. If it fails, it will also fail for a range of values on the chessboard. >This will therefore prove that the program is correct. > >To increase our confidence in these test, formal proofs could also be used. A >formal proof requires a little more work to construct however. Does anyone have >any advice on how to construct a formal proof for a chess program. I have some >idea but I'm not totally clear where to start on it. I guess I must have to >reason about the code or something using induction perhaps. All help >appreciated. > >Also if any of my reasoning above is incorrect I would also appreciate your >corrections/additions. > >Thanks First get your program to be compiled error free and warning free. Start by performing tests on the basic funtions and macro's of your program, define input conditions and define what output should be when legal input is fed to the function. Do that for every function! but start with the easiest, or lowest in the hierarchy. After that, check the initial value of every variable you are using, and every constant as well, are they all what they should be? After the basic functions and variables and constants are tested you can start testing the more complex functions, from basic to more complex and NOT the other way around! If all is working well -you think- you can do a perft test (google: computer chess perft) and do multiple perfts on different positions. If these perfts do not give the same result as the numbers listed on those "perft pages", than you need to go back to testing more intensly because you missed something. If you are interested in real testing I can give you an advise: buy a very good book on testing software systems! Happy Debugging ;-) Cheers! Renze
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.