I started writing a program to play checkers. Usually drafts games are programmed with algorithms based on incomplete enumeration (minimax and others). Are there any other approaches (really programmable) that do not require brute force and play well?

    3 answers 3

    For the endgame there is an approach “from the end position”, it is just optimal. The bottom line is that the program is repelled by the class "0" - positions with the victory of one of the parties (conditionally - white). Further, all positions are generated, of which there is a move to the position of the class “0” - these are the positions of the class “1” in which White wins in one move. The following are selected all positions that, in any course of black, lead to the positions of the class "1" - these are the positions of the class "2", etc.

    If there are few checkers on both sides (for example, in simple ladies' endgames), then it is possible to classify all positions except the draws. And playing with a sign of winning positions is simple:
    1) If the position is in the plate, then it is necessary to transfer it to the position of the class by one less (the winning one - because it will not work faster, and the losing one - to prolong the resistance);
    2) If the position is not in the plate, then you should not get into this plate with your own power. Because of a draw you can only get into losing.

      There is an approach based on neural networks with memory. You can read on the page JĂĽrgen Schmidhuber'a . There is a publication dedicated to the programming of the game in Go . But, frankly, these things are far from simple and for the sake of a learning task it is better not to take them, but to do minimax in the old fashioned way.

        As recommended above, use the classics. Plus, generate endgame bases, the program will become much smarter