<h2>Easiest solution: Let people play those layouts</h2>
<p>The best estimator for how human precept difficulty is, well... humans.  If you can let human players play then their <em>win-rate[%]</em> along with <em>time taken</em> and <em>backtracks</em> should produce a very accurate difficulty function.</p>
<h2><strong>Reverse engineering</strong> spots the hardest difficulty level</h2>
<p>I manually solved 3 layouts from each of the 6 difficulty levels and store their initial card layouts. Then used <a href="https://github.com/thecharlieblake/Solvitaire" rel="nofollow noreferrer">Charlie's Solvitaire</a> to solve those layouts.  I Hoped to be able to distinguish between all 6 difficulties using the output of the solver.  However only the Grandmaster level produce distinct outcomes. The differences between the others 5 levels in terms of Solvitaire output were somewhat ambiguous.</p>
<h2><strong>Second attempt: Compare optimal solutions</strong></h2>
<p>Solvitaire finds <em>a solution</em>, I thought that a better comparison will be to compare the <em><strong>optimal solution</strong></em>, by optimal I mean least number of moves.   So I adjusted Solvitaire from DFS to search <a href="https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search" rel="nofollow noreferrer">ID-DFS</a> (start with a solution from DFS, then use bounded-DFS that search for a solution with less steps. Repeated with smaller and smaller bounds until there is no solution, which means that the last solution is optimal).</p>
<p>Comparing <em>optimal solutions</em> did not produce better separating results.<br />
However I think that this process could work if it uses more data and better difficulty function.</p>
<p>Solvitaire output has those 10 parameters:</p>
<ol>
<li>is solvable?</li>
<li>States searched</li>
<li>Unique states searched</li>
<li>Backtracks</li>
<li>Dominance moves</li>
<li>Final stats in cache</li>
<li>final buckets in cache</li>
<li>maximum search depth</li>
<li>final search depth</li>
<li>time taken</li>
</ol>
<p>I used parameters #1,2,3,5,9,10 from the DFS solution and #1,2,3,5,9 from the ID-DFS</p>
<p>Solvitaire (DFS)
<a href="https://i.sstatic.net/GaicF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GaicF.png" alt="enter image description here" /></a></p>
<p>I modified Solitaire to find the optimal solution using iterative-deepening (IDDFS)
<a href="https://i.sstatic.net/rgpp1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rgpp1.png" alt="enter image description here" /></a></p>
<p>Made a difficulty function using the marked parameters:
<a href="https://i.sstatic.net/Efjkv.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Efjkv.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2024-09-02T18:26:52.610Z
By any chance is the code for your version of IDDFS Solvitaire public? I'd love to take a look!
Tytrox
CC BY-SA 4.0
2024-09-03T05:26:54.610Z
Unfortunately it is not public, I did it as a project to a gaming company that made a commercial version of solitaire.  However it is not too hard to transform Solvitaire into IDDFS, I remember there was one pitfall: Solvitaire store the nodes that were found to be a dead-end in order not to open them again, however in a bounded version of it a node could seems a dead end if it has only X moves left but to be part of a solution if it has X+Y moves left.  So If it got to the dead-end-node with less moves it should try to open it.
Cohensius
CC BY-SA 4.0
2024-09-03T05:31:05.727Z
I will explain it better with an example:   Say you do bounded DFS with a bound of 85 moves.  And say you got to node 'x' after 82 moves, then the DFS found no solution in any of the 3 moves from 'x', so he mark 'x' as a dead-end.  Latter the algorithm gets to 'x' after 70 moves.  But without a update in the code, it will not look if there is a solution from 'x' since 'x' is marked a dead-end.  I added to that check the number of moves it got the node, and if the current visit is lower, is still open up the tree from that node.
Cohensius
CC BY-SA 4.0
2020-11-30T09:27:33.797Z
2023-03-07T09:26:34.307Z
2023-03-07T09:26:34.307Z
Cohensius
<p>From a human perspective I suppose one's interpretation of difficulty is quite subjective: what one person might find difficult another may find easy. If, for our purposes, we use a rough definition along the lines of, &quot;how much time the average player spends on a layout&quot;, then there are a few interesting things we can say about the relationship between a layout's difficulty and its general features.</p>
<p>As your first point suggests, the solvability of the layout (i.e. does a sequence of legal moves exist that results in a win) is obviously key. Let's consider this case first:</p>
<h2>Unsolvable Layouts</h2>
<p>If a layout is not solvable then in one sense it's infinitely difficult. However, even for unsolvable layouts, the depth of the <a href="https://en.wikipedia.org/wiki/Search_tree" rel="noreferrer">search tree</a> can reflect a kind of difficulty.</p>
<p>In the extreme case, if to begin with there are no legal moves available in the tableau (main cards) or the stock, then although the layout isn't solvable, in a sense it is easy because you can immediately give up. Alternatively, a layout may have a huge number of promising moves, only to turn out to be unsolvable in the end.</p>
<p>Using a tool like <a href="https://github.com/thecharlieblake/Solvitaire" rel="noreferrer">Solvitaire</a> (full disclosure: I am one of the authors of Solvitaire) can identify unsolvable layouts and record the number of unique states that needed to be searched to prove that there's no solution (often a very large number of states!). Another good solver is <a href="https://github.com/ShootMe/Klondike-Solver" rel="noreferrer">Klondike-Solver</a>, although I'm not aware of what metrics it reports.</p>
<p>This isn't a perfect measure by any means. Humans aren't computers, and our brains probably aren't using depth-first search in the way a solver might. Without looking at human gameplay data though, this is probably the best heuristic of difficulty for unsolvable layouts.</p>
<h2>Solvable Layouts</h2>
<p>As was the case for unsolvable layouts, if one has access to human gameplay data then that's almost certainly going to be the best source of understanding how difficult humans will find a layout.</p>
<p>Let's assume though, that we don't have this data available, but we do have a computerised solver. Just looking at the static cards in the starting layout is unlikely to tell us much, but by running the solver we can deduce more about a deal's difficulty (for a human).</p>
<p>Here are some heuristics one could use instead:</p>
<h3>Size of Search Tree</h3>
<p>For a computer this is important, but in the solvable case it may not tell us much about human play. For instance, the search tree for a layout could be huge, but have one solution that's very obvious to a human. We would not want to classify such a layout as difficult just because it has a large search tree.</p>
<h3>Depth of Shallowest / Best Solution</h3>
<p>Based on the above logic, the depth of the shallowest (i.e. &quot;best&quot;) solution in the search tree is perhaps a better measure. However, this still may not be ideal. We might label a layout as easy because it has a shallow solution, but if this solution is extremely hard for a human to spot then our heuristic will be misleading.</p>
<h3>Number of different solutions</h3>
<p>This heuristic could be quite accurate, although it's hard to say. Having a lot of different solutions in the search tree would suggest a human player is likely to come across a solution sooner, but there is no guarantee. This would certainly be something worth exploring further.</p>
<h3>Number of states searched until first solution</h3>
<p>This is probably the most obvious heuristic: how many states did it take before the solver came across the first solution? However, this measure can be deeply flawed. There is no guarantee that computerised solvers search in anything like the kind of order a human would search in (Solvitaire certainly doesn't).</p>
<p>Say move &quot;A&quot; obviously leads to a solution in a few moves, whereas move &quot;B&quot; leads in a very different direction. There is no guarantee the solver picks &quot;A&quot; first; it might instead pick &quot;B&quot; and try thousands or even millions more moves before it backtracks to the point where it thinks to try &quot;A&quot;.</p>
<p>To make this kind of method work one needs a policy for which moves to try. For Solvitaire, which just wants to explore <em>all possible</em> moves, this doesn't matter, but for determining difficulty this is very important! If one could come up with a  policy which reflected closely how an average human would play, then the number of states searched until the first solution would be an excellent metric. But coming up with such a metric is hard, complex work.</p>
<h2>What Is A Move: Dominances and K+</h2>
<p>In all of these discussions we've talked about moves and states. But how we define a move in Klondike is actually not trivial.</p>
<p>Firstly, consider the stock. The standard rules require we turn over 3 cards in one go. A consequence of this is that at different times there are different groups of cards that are effectively &quot;available&quot; to us.</p>
<p><a href="http://web.engr.oregonstate.edu/%7Eafern/papers/solitaire.pdf" rel="noreferrer">Bjarnason et al.</a> use a solver which can move any of the available stock cards into the tableau in a single move (they call this the <strong>K+ representation</strong>). For a human, this is like saying &quot;I remember there's a 5H in there, so I'll just loop back over the stock to get it&quot;. From the point of considering difficulty, one may wish to consider this sort of thing to be a single move, rather than several separate moves.</p>
<p>Finally, in <a href="https://arxiv.org/pdf/1906.12314.pdf" rel="noreferrer">our paper on Solvitaire</a> we consider something called <strong>dominances</strong>. These are cases in which we can prove that one of the available moves is <em>guaranteed</em> to be a good move. For instance, sometimes it can clearly be shown that &quot;putting up&quot; say an ace, is always the right thing to do. This is often obvious to a human player and one might not wish to count this as a move (Solvitaire doesn't count this as an extra move).</p>
<h2>In summary:</h2>
<ul>
<li>One must first consider solvability</li>
<li>Then if a layout is solvable, one can begin with easier, but probably less accurate methods like the number of possible solutions, or the depth of the best solution</li>
<li>Finally, and <em>only</em> if one can craft a good (human-like) policy for moves to try at each search step, a better approach may be to measure the number of states the solver searches until the fist solution</li>
</ul>

CC BY-SA 4.0
2020-11-27T16:09:42.940Z
2020-11-27T16:09:42.940Z
Charlie Blake
<p>I want to measure the <strong>difficulty</strong> of different layouts in Klondike-Solitaire.  My question is, <strong>what are the parameters that determine the difficulty of a layout?</strong>
<a href="https://i.sstatic.net/BXqOf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/BXqOf.png" alt="enter image description here" /></a></p>
<p>By layout I mean the permutation of the cards.  The difficulty is also a matter of the rules (deal-1 or deal-3 cards from the stock to waste (talon), assume the rules are fixed on one of the options)</p>
<p>At <a href="https://games.ca.zone.msn.com/en/mssolitairecollection/default.htm?intgid=hp_card_1" rel="nofollow noreferrer">Microsoft Solitaire Collection</a>, there are 6 difficulty levels.  From my personal experience, the differences between the first 5 are minor compare to the huge difficulty difference between the second hardest (Master) and the hardest level (Grandmaster).</p>
<p>I thought about the following parameters:</p>
<ol>
<li>Solvable?</li>
<li>number of moves till solution</li>
<li>number of undo's</li>
<li>time taken (for a given user/solver)</li>
</ol>

CC BY-SA 4.0
2020-11-26T23:19:18.870Z
Knowing which percentage of folks who finished a level vs the population who tried that level would seem to give a good approximation of difficulty.
chicks
CC BY-SA 4.0
2020-11-29T16:49:54.593Z
@chicks, that might be the easiest and most accurate solution.  However it needs many players to play that level.  I want to get a difficulty estimation before letting players to play, then adjusting my estimation based on their results.
Cohensius
<solitaire><klondike-solitaire>
How to measure the difficulty of a deal in Klondike-Solitaire?
Cohensius
# How to measure the difficulty of a deal in Klondike-Solitaire?

(Asked by: username_0 on 2020-11-26)

I want to measure the **difficulty** of different layouts in Klondike-Solitaire. My question is, **what are the parameters that determine the difficulty of a layout?**
[![enter image description here](https://i.sstatic.net/BXqOf.png)](https://i.sstatic.net/BXqOf.png)

By layout I mean the permutation of the cards. The difficulty is also a matter of the rules (deal-1 or deal-3 cards from the stock to waste (talon), assume the rules are fixed on one of the options)

At [Microsoft Solitaire Collection](https://games.ca.zone.msn.com/en/mssolitairecollection/default.htm?intgid=hp_card_1), there are 6 difficulty levels. From my personal experience, the differences between the first 5 are minor compare to the huge difficulty difference between the second hardest (Master) and the hardest level (Grandmaster).

I thought about the following parameters:

1. Solvable?
2. number of moves till solution
3. number of undo's
4. time taken (for a given user/solver)

**Tags:** solitaire, klondike-solitaire

> **Comments:**
> **username_1**: Knowing which percentage of folks who finished a level vs the population who tried that level would seem to give a good approximation of difficulty.  
> **username_0**: @username_1, that might be the easiest and most accurate solution.  However it needs many players to play that level.  I want to get a difficulty estimation before letting players to play, then adjusting my estimation based on their results.  

---

## 2 answers

### Answer by username_3 on 2020-11-27. Score: 8 | Accepted answer

From a human perspective I suppose one's interpretation of difficulty is quite subjective: what one person might find difficult another may find easy. If, for our purposes, we use a rough definition along the lines of, "how much time the average player spends on a layout", then there are a few interesting things we can say about the relationship between a layout's difficulty and its general features.

As your first point suggests, the solvability of the layout (i.e. does a sequence of legal moves exist that results in a win) is obviously key. Let's consider this case first:

## Unsolvable Layouts

If a layout is not solvable then in one sense it's infinitely difficult. However, even for unsolvable layouts, the depth of the [search tree](https://en.wikipedia.org/wiki/Search_tree) can reflect a kind of difficulty.

In the extreme case, if to begin with there are no legal moves available in the tableau (main cards) or the stock, then although the layout isn't solvable, in a sense it is easy because you can immediately give up. Alternatively, a layout may have a huge number of promising moves, only to turn out to be unsolvable in the end.

Using a tool like [Solvitaire](https://github.com/thecharlieblake/Solvitaire) (full disclosure: I am one of the authors of Solvitaire) can identify unsolvable layouts and record the number of unique states that needed to be searched to prove that there's no solution (often a very large number of states!). Another good solver is [Klondike-Solver](https://github.com/ShootMe/Klondike-Solver), although I'm not aware of what metrics it reports.

This isn't a perfect measure by any means. Humans aren't computers, and our brains probably aren't using depth-first search in the way a solver might. Without looking at human gameplay data though, this is probably the best heuristic of difficulty for unsolvable layouts.

## Solvable Layouts

As was the case for unsolvable layouts, if one has access to human gameplay data then that's almost certainly going to be the best source of understanding how difficult humans will find a layout.

Let's assume though, that we don't have this data available, but we do have a computerised solver. Just looking at the static cards in the starting layout is unlikely to tell us much, but by running the solver we can deduce more about a deal's difficulty (for a human).

Here are some heuristics one could use instead:

### Size of Search Tree

For a computer this is important, but in the solvable case it may not tell us much about human play. For instance, the search tree for a layout could be huge, but have one solution that's very obvious to a human. We would not want to classify such a layout as difficult just because it has a large search tree.

### Depth of Shallowest / Best Solution

Based on the above logic, the depth of the shallowest (i.e. "best") solution in the search tree is perhaps a better measure. However, this still may not be ideal. We might label a layout as easy because it has a shallow solution, but if this solution is extremely hard for a human to spot then our heuristic will be misleading.

### Number of different solutions

This heuristic could be quite accurate, although it's hard to say. Having a lot of different solutions in the search tree would suggest a human player is likely to come across a solution sooner, but there is no guarantee. This would certainly be something worth exploring further.

### Number of states searched until first solution

This is probably the most obvious heuristic: how many states did it take before the solver came across the first solution? However, this measure can be deeply flawed. There is no guarantee that computerised solvers search in anything like the kind of order a human would search in (Solvitaire certainly doesn't).

Say move "A" obviously leads to a solution in a few moves, whereas move "B" leads in a very different direction. There is no guarantee the solver picks "A" first; it might instead pick "B" and try thousands or even millions more moves before it backtracks to the point where it thinks to try "A".

To make this kind of method work one needs a policy for which moves to try. For Solvitaire, which just wants to explore *all possible* moves, this doesn't matter, but for determining difficulty this is very important! If one could come up with a policy which reflected closely how an average human would play, then the number of states searched until the first solution would be an excellent metric. But coming up with such a metric is hard, complex work.

## What Is A Move: Dominances and K+

In all of these discussions we've talked about moves and states. But how we define a move in Klondike is actually not trivial.

Firstly, consider the stock. The standard rules require we turn over 3 cards in one go. A consequence of this is that at different times there are different groups of cards that are effectively "available" to us.

[Bjarnason et al.](http://web.engr.oregonstate.edu/%7Eafern/papers/solitaire.pdf) use a solver which can move any of the available stock cards into the tableau in a single move (they call this the **K+ representation**). For a human, this is like saying "I remember there's a 5H in there, so I'll just loop back over the stock to get it". From the point of considering difficulty, one may wish to consider this sort of thing to be a single move, rather than several separate moves.

Finally, in [our paper on Solvitaire](https://arxiv.org/pdf/1906.12314.pdf) we consider something called **dominances**. These are cases in which we can prove that one of the available moves is *guaranteed* to be a good move. For instance, sometimes it can clearly be shown that "putting up" say an ace, is always the right thing to do. This is often obvious to a human player and one might not wish to count this as a move (Solvitaire doesn't count this as an extra move).

## In summary:

* One must first consider solvability
* Then if a layout is solvable, one can begin with easier, but probably less accurate methods like the number of possible solutions, or the depth of the best solution
* Finally, and *only* if one can craft a good (human-like) policy for moves to try at each search step, a better approach may be to measure the number of states the solver searches until the fist solution


---

### Answer by username_0 on 2020-11-30. Score: 2

## Easiest solution: Let people play those layouts

The best estimator for how human precept difficulty is, well... humans. If you can let human players play then their *win-rate[%]* along with *time taken* and *backtracks* should produce a very accurate difficulty function.

## **Reverse engineering** spots the hardest difficulty level

I manually solved 3 layouts from each of the 6 difficulty levels and store their initial card layouts. Then used [username_3's Solvitaire](https://github.com/thecharlieblake/Solvitaire) to solve those layouts. I Hoped to be able to distinguish between all 6 difficulties using the output of the solver. However only the Grandmaster level produce distinct outcomes. The differences between the others 5 levels in terms of Solvitaire output were somewhat ambiguous.

## **Second attempt: Compare optimal solutions**

Solvitaire finds *a solution*, I thought that a better comparison will be to compare the ***optimal solution***, by optimal I mean least number of moves. So I adjusted Solvitaire from DFS to search [ID-DFS](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) (start with a solution from DFS, then use bounded-DFS that search for a solution with less steps. Repeated with smaller and smaller bounds until there is no solution, which means that the last solution is optimal).

Comparing *optimal solutions* did not produce better separating results.  
However I think that this process could work if it uses more data and better difficulty function.

Solvitaire output has those 10 parameters:

1. is solvable?
2. States searched
3. Unique states searched
4. Backtracks
5. Dominance moves
6. Final stats in cache
7. final buckets in cache
8. maximum search depth
9. final search depth
10. time taken

I used parameters #1,2,3,5,9,10 from the DFS solution and #1,2,3,5,9 from the ID-DFS

Solvitaire (DFS)
[![enter image description here](https://i.sstatic.net/GaicF.png)](https://i.sstatic.net/GaicF.png)

I modified Solitaire to find the optimal solution using iterative-deepening (IDDFS)
[![enter image description here](https://i.sstatic.net/rgpp1.png)](https://i.sstatic.net/rgpp1.png)

Made a difficulty function using the marked parameters:
[![enter image description here](https://i.sstatic.net/Efjkv.png)](https://i.sstatic.net/Efjkv.png)

> **Comments:**
> **username_2**: By any chance is the code for your version of IDDFS Solvitaire public? I'd love to take a look!  
> **username_0**: Unfortunately it is not public, I did it as a project to a gaming company that made a commercial version of solitaire.  However it is not too hard to transform Solvitaire into IDDFS, I remember there was one pitfall: Solvitaire store the nodes that were found to be a dead-end in order not to open them again, however in a bounded version of it a node could seems a dead end if it has only X moves left but to be part of a solution if it has X+Y moves left.  So If it got to the dead-end-node with less moves it should try to open it.  
> **username_0**: I will explain it better with an example:   Say you do bounded DFS with a bound of 85 moves.  And say you got to node 'x' after 82 moves, then the DFS found no solution in any of the 3 moves from 'x', so he mark 'x' as a dead-end.  Latter the algorithm gets to 'x' after 70 moves.  But without a update in the code, it will not look if there is a solution from 'x' since 'x' is marked a dead-end.  I added to that check the number of moves it got the node, and if the current visit is lower, is still open up the tree from that node.  

---

