Test Driven Development : le gain facile
Publié le
Le but des LucidPlayers de l'épisode précédent était de choisir un mouvement qui fait gagner immédiatement si possible. Autrement dit, de ne pas passer à côté d'une victoire évidente. C'est en ça qu'ils étaient lucides... en quelque sorte.
Je continue donc l'implémentation de cette stratégie en implémentant la recherche du coup gagnant et son choix. J'ai tout ce qu'il faut pour ça :
def is_last_line(line, role):
if role == P1:
return line == BOARD_MAXIMAL_Y
return line == 0
class LucidPlayer(Player):
def ask_move(self, effector):
allowed_movements = []
allowed_movements.extend(self._get_all_valid_movements())
allowed_movements.extend(get_valid_drops(self.board, self.tray, self._role))
if len(allowed_movements) > 0:
winning_capture = [(piece, source, destination)
for (piece, source, destination)
in allowed_movements
if source is not None
and self.board.get_piece_at(destination).is_a_lion()]
if len(winning_capture) > 0:
piece, source, destination = winning_capture[0]
effector.capture(source, destination)
return
winning_move = [(p, s, d)
for (p, s, d)
in allowed_movements
if s is not None
and p.is_a_lion()
and is_last_line(d[1], self._role)]
if len(winning_move) > 0:
piece, source, destination = winning_move[0]
if self.board.get_piece_at(destination).get_controller() == 0:
effector.move(source, destination)
else:
effector.capture(source, destination)
return
piece, source, destination = random.sample(allowed_movements, 1)[0]
if source is not None:
if self.board.get_piece_at(destination).get_controller() == 0:
effector.move(source, destination)
else:
effector.capture(source, destination)
else:
effector.drop(piece, destination)
Tout d'abord, je collecte la liste de tous les mouvements possibles. puis, s'il en existe, je construits la liste des mouvements de capture d'un Lion. Si cette liste contient un mouvement, il est choisi.
Sinon, je construis la liste de tous les mouvements qui amènent un Lion sur la dernière ligne (pour cela, j'introduis une fonction d'aide is_last_line). Encore une fois, s'il existe un tel mouvement, il est choisi.
Et dans la cas où il n'y a pas de mouvement gagnant, alors un mouvement aléatoire est choisi, comme précédemment.
Ça marche. Et j'ai donc ma première réponse à la question que je me posais il y a bien longtemps lorsque j'ai commencé cette série d'articles.
Globalement, une partie de Dôbutsu Shôgi entre deux joueurs débutants, qui ont compris les règles, dure 4 tours. Au bout de 25 tours, les parties sont terminées. 53% des parties sont gagnées par le premier joueur, ce qui est plutôt équilibré.
J'ai ma réponse, quoi d'autre ?
Les joueurs lucides ne sont tout de même pas très futés. Par exemple, ils ne réfléchissent même pas un coup à l'avance, et n'évitent pas une victoire évidente de l'adversaire.
J'aimerais donc continuer un peu avec une IA qui réfléchisse un peu plus. Mais avant cela, puisque je continue, je voudrais simplifier un peu le programme des joueurs lucides.
En effet, il y a de la duplication inutile. Si mon atelier était terminé ici, cela serait correct. Mais si je choisi de continuer, cette complexité risque de se faufiler dans le futur et rendre mes explorations plus complexes.
Mouvement générique
La principale cause de duplication est le décodage du mouvement pour choisir entre move et capture. Et il y a beaucoup de chance que ce motif réapparaisse dans d'autres IAs. Il me faut donc simplifier ceci.
Un premier pas de simplification est de tout simplement factoriser ces lignes.
def commit_move(self, effector, piece, source, destination):
if source is not None:
if self.board.get_piece_at(destination).get_controller() == 0:
effector.move(source, destination)
else:
effector.capture(source, destination)
else:
effector.drop(piece, destination)
Autant de paramètres est toujours louche. Je fais une autre simplification en deux mouvements, d'abord par l'introduction d'une fonction qui s'intercale :
def commit_move(self, effector, move):
piece, source, destination = move
self.commit_move_tuple(effector, piece, source, destination)
def commit_move_tuple(self, effector, piece, source, destination):
if source is not None:
if self.board.get_piece_at(destination).get_controller() == 0:
effector.move(source, destination)
else:
effector.capture(source, destination)
else:
effector.drop(piece, destination)
En branchant les appels vers commit_move, puis en mélangeant ces deux fonctions :
def commit_move(self, effector, move):
piece, source, destination = move
if source is not None:
if self.board.get_piece_at(destination).get_controller() == 0:
effector.move(source, destination)
else:
effector.capture(source, destination)
else:
effector.drop(piece, destination)
def ask_move(self, effector):
allowed_movements = []
allowed_movements.extend(self._get_all_valid_movements())
allowed_movements.extend(get_valid_drops(self.board, self.tray, self._role))
if len(allowed_movements) > 0:
winning_capture = [(piece, source, destination)
for (piece, source, destination)
in allowed_movements
if source is not None
and self.board.get_piece_at(destination).is_a_lion()]
if len(winning_capture) > 0:
self.commit_move(effector, winning_capture[0])
return
winning_move = [(p, s, d)
for (p, s, d)
in allowed_movements
if s is not None
and p.is_a_lion()
and is_last_line(d[1], self._role)]
if len(winning_move) > 0:
self.commit_move(effector, winning_move[0])
return
move = random.sample(allowed_movements, 1)[0]
self.commit_move(effector, move)
Comme je ne travaille pas sous test ici, il convient d'être ultra prudent et de ne faire que des opérations très simples, que je teste brièvement en lançant le programme tout de même à chaque changement.
En modifiant légèrement les deux dernières lignes en :
winning_move = random.sample(allowed_movements, 1)
if len(winning_move) > 0:
self.commit_move(effector, winning_move[0])
return
Je révèle une duplication supplémentaire. Que je peux sortir dans une fonction :
def commit_potential_move(self, effector, move_list):
if len(move_list) > 0:
self.commit_move(effector, move_list[0])
return True
return False
Et je m'arrête là.
Conclusion
Il y a encore pas mal de choses qui pourraient être faites dans cette étude. Une IA plus intelligente, avec mémoire,...
Cependant, je vais arrêter là cette série d'articles. J'espère que cette aventure au pays du TDD vous a plus.
J'espère aussi vous avoir convaincu de l'intérêt de la méthode, et je suis disponible pour en discuter.