Compter les disques stables à Othello

Question

Je codage un moteur Othello (Reversi), en tant que formation pour mettre en œuvre un moteur d'échecs plus tard. Je veux compter le nombre de pièces stables, mais je ne sais pas quelle est la meilleure façon de le faire.

Je peux facilement compter les pièces «Edge Stable», mais je ne sais pas comment tenir compte des autres. J'utilise un tableau 1-D pour représenter le tableau.

Appréciez tous les conseils à ce sujet!

Answer 1

de http://en.wikipedia.org/wiki/reversi

"Généralement, une pièce est stable lorsque, le long des quatre axes (horizontaux, verticaux et chaque diagonale), il est sur une frontière, dans une rangée remplie, ou à côté d'un morceau stable de la même couleur."

Vous avez déjà mentionné les limites - les lignes remplies peuvent être vérifiées en comptant simplement les pièces, bien qu'il y ait probablement de nombreuses optimisations ici, par exemple, trouvez les lignes remplies d'abord, puis marquez chaque position sur la ligne complète comme potentiellement stable, plutôt que d'itréter sur Chaque position, puis vérifiant toutes les directions pertinentes, ce qui entraînera des efforts gaspillés.

Cette page A plus de détails sur le calcul de la stabilité.

Si vous êtes intéressé par l'ordinateur Othello, assurez-vous de rechercher le publications sur Logistello, qui était (il y a au moins quelques années) le champion du monde. L'auteur, Michael Buro, a écrit sa thèse de doctorat sur ce sujet. Le code source est désormais disponible, vous pouvez donc inspecter les structures de données utilisées. De la mémoire, je pense qu'il a utilisé des nombres ternaires (c'est-à-dire des valeurs noires, blancs, vides) pour permettre des recherches rapides - et a également maintenu l'état de divers motifs (lignes, colonnes, diagonales, coins et autres) pour accélérer la fonction d'évaluation.

Answer 2

HM, il appartient à votre datastructure, je pense. Pour vérifier si une pièce est stable, vous devez vérifier si tous les champs à côté (horizontaux, verticaux, diagonaux) suivent l'une de ces règles:

• C'est une frontière
• C'est un morceau stable de la même couleur
• C'est dans une rangée remplie

La façon dont vous vérifiez cela dépend de votre datastructure. Vous pouvez peut-être choisir un tableau en 2 dimensions, vous avez donc une «image» plus proche du vrai tableau de jeu, une matrice 8x8.