Le calcul de machine à sous de paiement

Chaque paiement en plus de lignes de paiement qui semble trivial. Pour les trois lucky 7s, juste itérer sur le visible carrés et compte le 7s. De même pour la vérification d'un diamant. Si nous laissons h être le nombre de lignes et de w être le nombre de colonnes, cette opération est O(hw*), qui pour pratiquement de la taille des machines à sous est assez faible.

Les lignes de paiement, cependant, sont plus intéressants. Théoriquement, le nombre de lignes de paiement (m à partir de maintenant) est beaucoup, beaucoup plus grand que *h * w*; avant de les jeter de manière illégale lignes de paiement qui sauter m = h^w qui est beaucoup plus grand que *h ** w. Plus important encore, ils semblent partager beaucoup de similitude. Par exemple, la ligne 2 et la ligne 6 dans votre exemple, les deux nécessitent correspondant en haut à gauche et en haut au centre-gauche carrés. Si ces deux ne correspondent pas, alors vous ne pouvez pas gagner sur la ligne 2 ou la ligne 6.

Pour représenter les lignes, je vais utiliser la longueur w les tableaux d'entiers dans l'intervalle [1, h], tels que la ligne[i] = l'index dans la colonne (1 indexé) de rang i dans la solution. Par exemple, la ligne 1 est [1, 1, 1, 1, 1], et de ligne 17 est [3, 3, 2, 1, 2].

À cette fin, un le suffixe de l'arbre semble comme une structure de données qui peut améliorer considérablement votre temps de course de la vérification de toutes les lignes de paiement à l'encontre d'un conseil d'état. Considérons l'algorithme suivant pour la construction d'un suffixe arbre qui encapsule toutes les lignes de paiement.

Initialize: 
    Create a root node at column 0 (off-screen, non-column part of all solutions)
    root node.length = 0
    root node.terminal = false
    Add all paylines (in the form of length w arrays of integers ranging from 1 to h) to the root nodes' "toDistribute set"
    Create a toWork queue, add the root node to it

Iterate: while toWork not empty:
    let node n = toWork.pop()
    if n.length < w
        create children of n with length n.length + 1 and terminal = (n.length + 1 == w).
    for payline p in n.toDistribute
        remove p from n.toDistribute
        if(p.length > 1)
            add p.subArray(1, end) to child of n as applicable.
    add children of n to toWork

L'exécution de cette construction de l'algorithme sur l'exemple pour les lignes 1-11 donne un arbre qui ressemble à ceci:

Le calcul de cet arbre est assez intense; il implique la création de sum i = 1 to w of h ^ i nœuds. La taille de l'arbre dépend uniquement de la taille du conseil d'administration (hauteur et largeur), et non pas le nombre de lignes de paiement, qui est le principal avantage de cette approche. Un autre avantage est qu'il est tout de pré-traitement, vous pouvez avoir cet arbre construit bien avant qu'un joueur s'assoit tirer le levier.

Une fois que l'arbre est construit, vous pouvez donner à chaque nœud d'un champ pour chaque match de critères (même symbole, de la même couleur, etc). Ensuite, lors de l'évaluation d'un conseil d'état, vous pouvez dfs de l'arbre, et à chaque nouveau nœud, demander (pour chaque critère) si elle correspond à son nœud parent. Si oui, marque que des critères comme vrai et de continuer. Autre, marque comme faux et ne recherche pas les enfants pour que les critères. Par exemple, si vous êtes à la recherche spécifiquement pour les identique de jetons sur le sous-tableau [1, 1, ...] et de trouver que la colonne 1 de la ligne 1 et la colonne 2 de la ligne 1 ne correspondent pas, alors n'importe quelle ligne de paiement qui comprend [1, 1, ...] (2, 6, 16, 20) tout ne peut pas être gagné, et vous n'avez pas à dfs cette partie de l'arbre.

Il est difficile d'avoir une bonne algorithmique analyse de la façon dont beaucoup plus efficace cette dfs approche est qu'individuellement vérifier chaque ligne de paiement, car une telle analyse aurait besoin de savoir combien de gauche qui se chevauchent (en moyenne) il y a entre les lignes de paiement. C'est certainement pas pire, et au moins pour ton exemple est beaucoup mieux. En outre, plus de lignes de paiement que vous ajoutez à un conseil, plus le chevauchement, et la plus grande de l'économie de temps pour la vérification de toutes les lignes en utilisant cette méthode.

OriginalL'auteur Mshnik