D'un point de vue humain, je suppose que l'interprétation de la difficulté est assez subjective : ce qu'une personne peut trouver difficile, une autre peut le trouver facile. Si, pour nos besoins, nous utilisons une définition approximative du type "combien de temps le joueur moyen passe sur une disposition", alors il y a quelques choses intéressantes que nous pouvons dire sur la relation entre la difficulté d'une disposition et ses caractéristiques générales.
Comme le suggère votre premier point, la solvabilité du plan (c'est-à-dire l'existence d'une séquence de coups légaux permettant de gagner) est évidemment essentielle. Considérons d'abord ce cas :
Mises en page insolubles
Si une disposition n'est pas soluble, alors, dans un sens, elle est infiniment difficile. Cependant, même pour les dispositions non solubles, la profondeur de la arbre de recherche peut refléter une sorte de difficulté.
Dans le cas extrême, si au départ il n'y a aucun coup légal disponible dans le tableau (cartes principales) ou dans le stock, alors bien que la disposition ne soit pas soluble, dans un sens elle est facile parce que vous pouvez immédiatement abandonner. Par ailleurs, une disposition peut présenter un grand nombre de coups prometteurs, pour s'avérer finalement insoluble.
En utilisant un outil comme Solvitaire (divulgation complète : je suis l'un des auteurs de Solvitaire) peut identifier les dispositions insolubles et enregistrer le nombre d'états uniques qui ont dû être recherchés pour prouver qu'il n'y a pas de solution (souvent un très grand nombre d'états !). Un autre bon solveur est Klondike-Solver mais je ne connais pas les mesures qu'il rapporte.
Ce n'est pas une mesure parfaite, loin de là. Les humains ne sont pas des ordinateurs, et nos cerveaux n'utilisent probablement pas la recherche en profondeur comme le ferait un solveur. Sans regarder les données de jeu humain, c'est probablement la meilleure heuristique de difficulté pour les dispositions insolubles.
Mises en page résolubles
Comme c'était le cas pour les dispositions insolubles, si l'on a accès à des données de jeu humain, il est presque certain que ce sera la meilleure source pour comprendre la difficulté que les humains trouveront à une disposition.
Supposons toutefois que nous ne disposions pas de ces données, mais que nous ayons un solveur informatisé. Le simple fait de regarder les cartes statiques dans la disposition de départ ne nous apprend pas grand-chose, mais en utilisant le solveur, nous pouvons en déduire davantage sur la difficulté d'une donne (pour un humain).
Voici quelques heuristiques que l'on pourrait utiliser à la place :
Taille de l'arbre de recherche
Pour un ordinateur, c'est important, mais dans le cas d'une solution, cela peut ne pas nous renseigner sur le jeu humain. Par exemple, l'arbre de recherche d'une disposition peut être énorme, mais avoir une solution qui est très évidente pour un humain. Nous ne voudrions pas classer une telle disposition comme difficile juste parce qu'elle a un grand arbre de recherche.
Profondeur de la solution la moins profonde / meilleure
Selon la logique ci-dessus, la profondeur de la solution la moins profonde (c'est-à-dire la "meilleure") dans l'arbre de recherche est peut-être une meilleure mesure. Cependant, cette mesure n'est peut-être pas encore idéale. Nous pourrions qualifier une disposition de facile parce qu'elle a une solution peu profonde, mais si cette solution est extrêmement difficile à repérer pour un humain, notre heuristique sera trompeuse.
Nombre de solutions différentes
Cette heuristique pourrait être assez précise, bien qu'il soit difficile de l'affirmer. Le fait d'avoir beaucoup de solutions différentes dans l'arbre de recherche suggère qu'un joueur humain est susceptible de trouver une solution plus tôt, mais il n'y a aucune garantie. Il s'agit certainement d'un sujet qui mérite d'être exploré plus avant.
Nombre d'états recherchés jusqu'à la première solution
Il s'agit probablement de l'heuristique la plus évidente : combien d'états ont été nécessaires avant que le solveur ne trouve la première solution ? Cependant, cette mesure peut être très imparfaite. Il n'y a aucune garantie que les résolveurs informatiques cherchent dans un ordre qui ressemble à celui dans lequel un humain chercherait (ce n'est certainement pas le cas du Solvitaire).
Disons que le coup "A" mène manifestement à une solution en quelques coups, alors que le coup "B" mène dans une direction très différente. Il n'y a aucune garantie que le solveur choisisse d'abord "A" ; il pourrait choisir "B" et essayer des milliers, voire des millions d'autres coups avant de revenir au point où il pense essayer "A".
Pour que ce type de méthode fonctionne, il faut définir une politique concernant les mouvements à essayer. Pour le Solvitaire, qui veut simplement explorer tout ce qui est possible pour les déplacements, cela n'a pas d'importance, mais pour déterminer la difficulté, c'est très important ! Si l'on pouvait trouver une politique qui reflète étroitement la façon dont un humain moyen jouerait, alors le nombre d'états recherchés jusqu'à la première solution serait une excellente mesure. Mais la mise au point d'une telle mesure est un travail difficile et complexe.
What Is A Move : Dominances and K+
Dans toutes ces discussions, nous avons parlé de déménagements et d'états. Mais la façon dont nous définissons un mouvement dans Klondike n'est en fait pas triviale.
Tout d'abord, considérons le stock. Les règles standard exigent que nous retournions 3 cartes en une seule fois. Une conséquence de cela est qu'à différents moments, il y a différents groupes de cartes qui sont effectivement "disponibles" pour nous.
Bjarnason et al. utilisent un solveur qui peut déplacer n'importe laquelle des cartes de stock disponibles dans le tableau en un seul mouvement (ils appellent cela le La représentation de K+ ). Pour un humain, cela revient à dire "Je me souviens qu'il y a un 5H là-dedans, alors je vais faire une boucle pour le récupérer". Du point de vue de la difficulté, on peut considérer ce genre de chose comme un seul mouvement, plutôt que plusieurs mouvements séparés.
Enfin, en notre document sur le Solvitaire nous considérons une chose appelée dominations . Ce sont des cas dans lesquels on peut prouver que l'un des coups disponibles est garanti pour être un bon coup. Par exemple, il peut parfois être clairement démontré que "mettre en jeu", disons un as, est toujours la bonne chose à faire. C'est souvent évident pour un joueur humain et l'on pourrait ne pas vouloir compter cela comme un coup (le Solvitaire ne compte pas cela comme un coup supplémentaire).
En résumé :
- Il faut d'abord considérer la solvabilité
- Ensuite, si une disposition est soluble, on peut commencer par des méthodes plus faciles, mais probablement moins précises, comme le nombre de solutions possibles ou la profondeur de la meilleure solution.
- Enfin, et uniquement si l'on peut élaborer une bonne politique (de type humain) pour les mouvements à essayer à chaque étape de la recherche, une meilleure approche peut consister à mesurer le nombre d'états que le solveur recherche jusqu'à la première solution.
