I’m writing a simple chess engine in LISP. I actually know how the engine decide the move, it evaluates and reads some opening books. But that’s not what i mean. This is my design.
57 58 59 60 61 62 63 64
49 50 51 52 53 54 55 56
41 42 43 44 45 46 47 48
33 34 35 36 37 38 39 40
25 26 27 28 29 30 31 32
17 18 19 20 21 22 23 24
09 10 11 12 13 14 15 16
01 02 03 04 05 06 07 08
I looked at more complicated solutions but i came out with what i believe is the simplest one. Say the bishop is on the square 23, it could move 4 possible moves, (to 16 or 14 or 32 or 30), so it moves -7 or +7 or +9 or -9.
I create an array
(make-array '(8 8) :initial-contents
'((R B N Q K B N R)
(P P P P P P P P)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL)
(P P P P P P P P))
(R B N Q K B N R)))
And move the pieces from index to index. My question is, i cannot simply tell the bishop to move +7 or whatever, if it’s an open diagonal. I need to tell it to move +9 * 1 or +9 * 2 etc. and you bishop have to decide which one to go to. I cannot write a condition and a loop for every possible square
2
Imagine you’ve got a function that evaluates the game board and returns a score, where large positive scores mean you’re doing well and large negative scores means you’re doing badly.
Now imagine that for each possible position that a piece can move to, for each piece on the board, you calculate what the score would become and choose the move that results in the best score. This isn’t too hard to do and results in an AI opponent that’s roughly equivalent to a novice human chess player.
Now; instead of finding the best score after you’ve made one move, you could find the score after you’ve made a move and the opponent has also made a move.
More importantly you can do this to “n levels” – e.g. find the score after you’ve made n moves and the opponent has made n moves. In this case “n = 3” is about equivalent to a decent human player, and extremely good human players may be equivalent to about “n = 7”.
Computers are fast enough to do up to “n = 7” relatively quickly; so that’s all relatively easy to implement.
If you want to completely and utterly destroy the game (by making it impossible for a human player to win or enjoy playing); you can go further than this. In this case you have to worry about the “pruning” stuff other people have mentioned to reduce processing time and memory consumption. My advice here is don’t bother – there’s already been far too many smart/stupid people ruining “player vs. machine” chess.
1
A bishop can go to the field numbered +7 or +9, and possibly from there to the fields numbered +14 and +18. That last part you can check with a loop: how often can you do a +7, how often a +9?
There are two limits to this: other pieces (which can be captured, but must be then removed) and the board edges. For the bishop, that means you can’t do a +7 from board position N*8+1, as that would wrap, you can’t do a +9 from board position N*8, and you can’t do any + from board position >=57. And obviously there’s also -7 and -9 with similar constraints.
Other pieces have other rules, but they’re pretty much the same: can’t cross other pieces, can’t cross edges. Some can perform only one step at a time. E.g. knights have a +15 move, but no +30, and the +15 move can only originate from fields withing the 02-08-48-42 rectangle.
As @MichaelT pointed out, you should read up on minimax search and alpha-beta pruning.
The issue here is algorithmic, and has almost nothing to do with design. At each turn you have some number of possible moves. For each of your possible moves, your opponent has some number of moves of her own. This generates the game tree that you need to search. At each node you need to be able to evaluate the position of the board to determine which outcome is most advantageous for you. The algorithm to search such trees is called minimax search. The way to avoid having to search the entire tree is called alpha-beta pruning.