On Making a Puzzle Creation Algorithm

[n4k3dw4ff13s]

Hello all,

I saw chess.com mention how its criteria on what makes a good puzzle and I was thinking about how to go about their steps programmatically.
I first thought of determining the winningness of a position by using a Stockfish to analyze the position and compare its evaluation score with a threshold value to return a Boolean indicating if the winningness is clear. However, if we define obvious as easily discovered, seen, or understood (by the person playing-- in this case a human), and we couple this definition with the observation that Stockfish engines match human moves between 33–41% of the time and Leela engines 46% of the time as of 2020 then. An engine modification like Maia on the other hand match human moves between 46-52% of the time. Perhaps these engines by themselves are not the best tool for determining whether the final position of the puzzle is discovered, seen, or understood and thus might be helped by the Maia weights.

Here's a pseudocode example.
# Generating a Chess Puzzle
## Input
- chess game positions
## Output
- a chess puzzle position
## Steps
1. Create a list of all possible moves for the starting position
2. For each possible move:
a. Make the move
b. Generate all possible opponent moves
c. For each opponent move:
i. Make the opponent move
ii. Check if the opponent's move is terrible (i.e., puts the player in a losing position)
iii. If the opponent's move is not terrible, continue to the next step
iv. If the opponent's move is terrible, undo the opponent move and go back to step c
d. Check if there is only one good move for the player (i.e., puts the player in a winning position)
e. If there is only one good move, continue to the next step
f. If there is not only one good move, undo the player move and go back to step 2
3. Determine the Obviousness of the Final Position
a. Use the Lc0 with Maia weight 1900's policy value to analyze the position
b. Get the move with the highest probability from the policy
c. Compare the highest probability move with the move from step 2e
d. If the two moves match, return True
i. If True is returned, return the puzzle position
e. If the two moves do not match, return False
i. If False is returned, go back to step 2


Any feedback or suggestion on step three would be greatly appreciated. What do you think is the best way to determine the winningness of a chess position? My implementation of step three was written based off of my assumptions on what obvious are, but I imagine people can arrive at a different idea. A lot of you in the forum have written engines and evaluation functions of your own before and might have some insight on this based on your experiences.

[Fulvio]

I saw chess.com mention how its criteria on what makes a good puzzle

Thanks for sharing the interesting link.
Extracting tactics from real games takes time, but it is not a problem, considering that lichess publish million of new games every month.

Our algorithm “walks” the positions in all the games played until it finds a position that can be thought of as a tactical puzzle.
1. There should be only one good move for each player move (except for the last move)

I wrote this script:
https://github.com/benini/extract_tacti ... xtract.tcl

Code: Select all

# Engine configuration
set engine_options {}
lappend engine_options [list MultiPV 2]
lappend engine_options [list Threads 4]
lappend engine_options [list Hash 1024]
set engine_limits {}
lappend engine_limits [list depth 30]
lappend engine_limits [list movetime 2000]

# Create the output file
set out_file [open "tacticts.pgn" w]

# This procedure will be invoked for every position in input_database
proc analyzed_position {fen last_move} {
    # The last evaluations received from the engine are stored in a global array
    global enginePVs

    # Ignore position with only one valid move
    if {![info exists enginePVs(2)]} { return }

    # Ignore position where there are multiple good moves
    lassign $enginePVs(2) score2 score_type2
    if {$score_type2 eq "mate" || $score2 > 900} { return }

    # Ignore position where the best move is not good enough
    lassign $enginePVs(1) score1 score_type1 pv1
    if {$score_type1 ne "mate" && $score1 < 2000} { return }

    # Output the position
    puts $::out_file "\[FEN \"$fen\"\] {last_move: $last_move} $pv1"
    flush $::out_file
}

It starts an engine with 4 threads, 1024MB of memory and MultiPV set to 2.
Each position is analyzed for 2 seconds or to a maximum depth of 30.
If the best move gives an advantage of at least 2 pawns, and the second best move is less than 0.9 pawns, the fen is appended to tactics.pgn.
For example analyzing this game:
https://lichess.org/d0cR9TeT#0
produces:

Code: Select all

[FEN "7k/R4pr1/2N5/2Pp4/3bbB2/6P1/1P2B2K/6R1 b - - 7 40"] {last_move: b8c6} g7h7 f4h6 h7h6 e2h5 h6h5

How do we rate puzzles? We use a mix of machine learning and behavioral data.
How are puzzles broken down by theme? By a mix of automated technology and user votes.

I think that's the difficult task (as I wrote a few days ago https://talkchess.com/forum3/viewtopic. ... 3c96ece5d2 ).
Unfortunately they did not write what kind of machine learning they use.

[phhnguyen]

Did you study a blog’s post by Tord Romstad?

https://blog.playmagnus.com/generating- ... art-i/amp/

[n4k3dw4ff13s]

Did you study a blog’s post by Tord Romstad?

https://blog.playmagnus.com/generating- ... art-i/amp/

No; I did not know about this! Thanks for brining it to my attention!

[Fulvio]

Did you study a blog’s post by Tord Romstad?
https://blog.playmagnus.com/generating- ... art-i/amp/

Thanks for sharing!
I couldn't find Part II, but it looks like there's a general consensus that a tactic is a position where one move is significantly better.

But, I have to disagree with the manually tuned hard code approach for selecting "good" tactics.
It reminds me of the old wizardry used to tune the evaluation function of chess engines, and it can easily go out of hand (https://github.com/ornicar/lichess-puzz ... er/cook.py).
It also does not seem to produce satisfying results: I'm bored by both the tactical training available on chess.com and lichess.

[phhnguyen]

Did you study a blog’s post by Tord Romstad?
https://blog.playmagnus.com/generating- ... art-i/amp/

Thanks for sharing!
I couldn't find Part II, but it looks like there's a general consensus that a tactic is a position where one move is significantly better.

I could not find that part either and guessed the author has not published it yet.

However, I guess that part is about building trees to find full solutions since PV lines sometimes are cut short and be not full solutions. The author may use the shapes of trees to cut off some uninteresting puzzles.

But, I have to disagree with the manually tuned hard code approach for selecting "good" tactics.
It reminds me of the old wizardry used to tune the evaluation function of chess engines, and it can easily go out of hand (https://github.com/ornicar/lichess-puzz ... er/cook.py).
It also does not seem to produce satisfying results: I'm bored by both the tactical training available on chess.com and lichess.

IMHO, Tord's method is the best one so far, at least counted in practicableness.

On the other hand, we may not totally agree how interesting/bored a puzzle is. My children love/prefer simple, straightforward puzzles. Many members in this forum prefer much harder/longer-solution puzzles to feed their brains and/or engines. You may get bored with puzzles on those websites but I knew some of their members worry about how many puzzles they can be given per day.

[Fulvio]

IMHO, Tord's method is the best one so far, at least counted in practicableness.

On the other hand, we may not totally agree how interesting/bored a puzzle is. My children love/prefer simple, straightforward puzzles. Many members in this forum prefer much harder/longer-solution puzzles to feed their brains and/or engines. You may get bored with puzzles on those websites but I knew some of their members worry about how many puzzles they can be given per day.

But that's exactly the problem of that method!
It arbitrarily decides that a mate in 1 is too easy, but I saw many kids miss a mate in 1!

[Ferdy]

Hello all,

I saw chess.com mention how its criteria on what makes a good puzzle and I was thinking about how to go about their steps programmatically.
I first thought of determining the winningness of a position by using a Stockfish to analyze the position and compare its evaluation score with a threshold value to return a Boolean indicating if the winningness is clear. However, if we define obvious as easily discovered, seen, or understood (by the person playing-- in this case a human), and we couple this definition with the observation that Stockfish engines match human moves between 33–41% of the time and Leela engines 46% of the time as of 2020 then. An engine modification like Maia on the other hand match human moves between 46-52% of the time. Perhaps these engines by themselves are not the best tool for determining whether the final position of the puzzle is discovered, seen, or understood and thus might be helped by the Maia weights.

Here's a pseudocode example.
# Generating a Chess Puzzle
## Input
- chess game positions
## Output
- a chess puzzle position
## Steps
1. Create a list of all possible moves for the starting position
2. For each possible move:
a. Make the move
b. Generate all possible opponent moves
c. For each opponent move:
i. Make the opponent move
ii. Check if the opponent's move is terrible (i.e., puts the player in a losing position)
iii. If the opponent's move is not terrible, continue to the next step
iv. If the opponent's move is terrible, undo the opponent move and go back to step c
d. Check if there is only one good move for the player (i.e., puts the player in a winning position)
e. If there is only one good move, continue to the next step
f. If there is not only one good move, undo the player move and go back to step 2
3. Determine the Obviousness of the Final Position
a. Use the Lc0 with Maia weight 1900's policy value to analyze the position
b. Get the move with the highest probability from the policy
c. Compare the highest probability move with the move from step 2e
d. If the two moves match, return True
i. If True is returned, return the puzzle position
e. If the two moves do not match, return False
i. If False is returned, go back to step 2


Any feedback or suggestion on step three would be greatly appreciated. What do you think is the best way to determine the winningness of a chess position? My implementation of step three was written based off of my assumptions on what obvious are, but I imagine people can arrive at a different idea. A lot of you in the forum have written engines and evaluation functions of your own before and might have some insight on this based on your experiences.

There was an idea from Uri about this. Check positions from games, and find that position where a player blundered or committed a mistake or some suboptimal moves. Who is this player? What is the rating of this player? If this is Hikaru or anybody then this position must be interesting at that rating level. This position must be complicated that Hikaru has difficulties analyzing it. This position passed the first level of determining a good puzzle. We can verify it if it is good, save it to a puzzle database along with the rating info.

One advantage of this method is that, we already have the rating of the player who played the suboptimal move. So when we test a player on the puzzles and this player has a rating of say 2000, we just pick up a puzzle suitable for that player from a database that has a rating of say [1900, 2100].

I have a web application of this system. Even if I am only around 1900 FIDE, I can train with puzzles at 2300 to 2500 level with this app. I can feel these positions are not easy at all.

Sample:
I am lucky, got the best move Qe2.



I also have a puzzle creator scripts in github, just in case you are interested.

Continue with what you plan. The important thing is to check if the results are good.

In chess stackexchange, there was one guy who asked how to determine a brilliant move, the chess.com way. It involves material sacrifice and other things. I tried to implement it but not yet done. I got a nice results so far. I was able to find some material sacs from the 85th Tata Steel Masters games.