Parcours en largeur 0-1
Combien de pierres faut-il encore à ce joueur pour finir une connexion ?
Une recherche de plus court chemin pour les graphes dont les pas coûtent 0 ou 1, avec une liste par coût au lieu d’un tas. HEX l’utilise pour compter les pierres qu’il reste à poser à un joueur.
Quand chaque pas coûte 0 ou 1, le tas de Dijkstra est excessif. Une file à double extrémité suffit : un pas de coût 0 va en tête, car il est aussi peu cher que la case quittée, et un pas de coût 1 va en queue. La file reste ordonnée par coût, donc les cases sortent dans le bon ordre en un temps proportionnel au plateau. La version de la démo est la même idée avec une liste par valeur de coût.
À HEX, traverser une pierre du joueur coûte 0, une case vide coûte 1 (une pierre à poser) et les pierres adverses sont des murs. Le chemin le moins cher entre deux bords du joueur est le nombre de pierres qu’il lui faut encore.
Ce nombre est la fonction d’évaluation de la recherche alpha-bêta : l’IA préfère les positions où sa propre distance est courte et la vôtre longue.
- 01Partir de chaque case du premier bord du joueur : coût 0 si elle porte une pierre du joueur, coût 1 si elle est vide, ignorée si elle porte une pierre adverse.
- 02Prendre la case la moins chère de la file.
- 03Si elle est sur le bord opposé du joueur, son coût est la réponse.
- 04Pour chaque voisine qui n’est pas une pierre adverse, le pas coûte 0 si c’est une pierre du joueur et 1 si elle est vide. Si cela abaisse son coût enregistré, l’enregistrer et la mettre à l’extrémité correspondante.
- 05Si la file se vide, le joueur ne peut plus se connecter.
function zero_one_bfs(starts, is_target):
dist = {}
deque = []
for s in starts:
dist[s] = step_cost(s) # 0 for my stone, 1 for an empty cell
deque.push_back(s)
while deque is not empty:
cell = deque.pop_front()
if is_target(cell): return dist[cell]
for n in neighbours(cell):
if is_opponent(n): continue
w = step_cost(n) # 0 or 1
if dist[cell] + w < dist.get(n, infinity):
dist[n] = dist[cell] + w
if w == 0: deque.push_front(n)
else: deque.push_back(n)
return infinityLinéaire en fonction de la taille du plateau, ce qui compte car l’évaluation tourne sur chaque position visitée par la recherche.
- Temps linéaire, sans tas.
- Donne une évaluation qui a un sens : les pierres encore à poser.
- Marche pour tout graphe à coûts 0 et 1.
- Seulement pour des coûts 0 et 1.
- Compte des pierres, pas des menaces, donc il ne voit pas que deux chemins peuvent se protéger.
- Lancé une fois par position, donc il doit être rapide.
- 01HEXMesure, pour chaque camp, les pierres encore nécessaires pour joindre ses deux bords. Le coup de l’IA est celui qui laisse votre distance longue et la sienne courte.