J'espère que mes explications sont claires

Voici des exemples d'échiquiers :

 Cliquez pour afficher

Cet échiquier a un score de 2, comme l'échiquier vide, car il estr toujours possible d'aller d'une case à une autre en deux mouvements


Celui-ci un score de 3 car il faut 3 déplacements pour se déplacer entre les cases f1 et c1


Celui-ci a un score de 4 car il faut 4 déplacements pour aller de a1 à a8

Bonsoir,

 Cliquez pour afficher

j'ai un échiquier ayant un coût de 15 avec 31 pions.

Bonjour, je doute fort d'avoir le max aussi mais je propose quand même.

 Cliquez pour afficher

coût de 23 avec 34 pions pour passer de A1 à H8

Je ne connais pas le max non plus, mais @Vassilia j'ai trouvé le même résultat que toi, hormis que tu as inclus deux pions supplémentaires qui ne sont pas nécessaires pour que l'échiquier ait un score de 23

J'avoue ne pas avoir trop fait attention aux nombres de pions,
je peux en effet supprimer le H5 et le G8

Non pas G8, mais A2

D'accord alors H5, G8 et A2 ce qui nous fait enlever 3 pions
En effet, même sans G8 pour la fin du parcours, si on veut atteindre H7, il faudra 2 déplacements à partir de F8 qui est obligatoire.

D'ailleurs finalement, enlevons aussi B1 car si on part de A2, on a 2 déplacements pour atteindre C1 qui est lui aussi obligatoire.
Donc ça devrait être jouable avec 30 pions. Pas de meilleure idée d'optimisation ce soir et il est l'heure d'aller dormir pour moi.
Bonne nuit.

En effet, j'avais pas vu ça avec B2 et H7 ! bien joué

A2*

Bonjour,

 Cliquez pour afficher

J'en ai un en 24 mouvements.

Bonjour
Tu télécharges ton image comme d'habitude
Puis dans la zone de réponse tu cliques sur l'icône de blank, ton curseur est alors entre les balises
Puis tu cliques sur ton image
Et le code de ton image est alors coincé entre les balises de blank

Super ! Merci
Donc, voici la config :

 Cliquez pour afficher

Bonjour à tous

@Thetapinch27 : il me semble que tu as oublié le raccourci : F2-G3

Imod

Haha le boulet ! Bien vu et merci
Du coup en tentant de réparer mon erreur je trouve qu'on peut faire encore mieux

 Cliquez pour afficher

25 mouvements

Ca semble juste et au passage pourquoi ne pas enlever e4 ?

Imod

Je précise : e5=N ,  e4=B , f5=B .

Imod

En y regardant de plus près , on ne gagne rien en inversant les cases e4-e5 , on reste à 25

Imod

On peut enlever les coins A1, A8, H1 et H8. Non?

Même idée, 6 pions de moins:

 Cliquez pour afficher

Bonsoir,

Juste pour le délire, un code Python pour résoudre le problème. Pas mieux que 25.

Principe :
* On donne une case start et une case stop
* Un algo génétique génère des configurations. Initialement, j'ai choisi une proba de 0.5 pour choisir si une case est bloquée ou autorisée car c'est proche de que donnent les bonnes solutions trouvées par nous tous. De plus, avoir trop de cases libres ferait ramer l'algorithme de Dijkstra pour la recherche du meilleur chemin et on "voit bien" que moins on met de contraintes moins il faut de coups à la dame pour atteindre l'objectif.
** Du coup, le fitness correspond au résultat de Dijkstra lancé sur la config
** Le crossover correspond à récupérer N//2 cases choisies aléatoirement du parent 1 et le reste du parent 2.
** La mutation consiste à changer l'état d'une case

Évidement il y a plein de voies d'amélioration. Je pense que partir d'un échiquier 100% contraint et libérer de proche en proche des cases pourrait donner de bonnes solutions avec beaucoup moins de calculs (plus besoin de Dijkstra)... mais bon j'ai démarré comme ça... alors je laisse.

Si vous lancez le code ci-dessous, vous en avez pour la nuit (il teste toutes les combinaisons start, stop, chacun parcourant {0,1,2,3}^2 donc 256 algo G à lancer. Pour lancer l'algo qu'une fois, on peut commenter le dernier bloc et décommenter l'avant dernier, ce qui lance le calcul avec start=(0,0) et stop=(7,7)

import heapq
import random

def dijkstra_chessboard(start_pos, end_pos, obstacles):
    size = 8  
    
    distances = [[float('inf')] * size for _ in range(size)]
    distances[start_pos[0]][start_pos[1]] = 0
    
    previous = [[None] * size for _ in range(size)]
    
    pq = [(0, start_pos)]
    
    while pq:
        cost, curr_pos = heapq.heappop(pq)
        if curr_pos == end_pos:
            return construct_path(previous, start_pos, end_pos), cost
        
        for direction in [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]:
            for i in range(1, size):
                new_pos = (curr_pos[0] + i * direction[0], curr_pos[1] + i * direction[1])
                if 0 <= new_pos[0] < size and 0 <= new_pos[1] < size:
                    if new_pos in obstacles:
                        break
                    new_cost = cost + 1  
                    if new_cost < distances[new_pos[0]][new_pos[1]]:
                        distances[new_pos[0]][new_pos[1]] = new_cost
                        previous[new_pos[0]][new_pos[1]] = curr_pos
                        heapq.heappush(pq, (new_cost, new_pos))
    
    return [], 0


def construct_path(previous, start_pos, end_pos):
    path = []
    curr_pos = end_pos
    while curr_pos != start_pos:
        path.append(curr_pos)
        curr_pos = previous[curr_pos[0]][curr_pos[1]]
    path.append(start_pos)
    return path[::-1]


def draw_chessboard(size, obstacles, trajectory):
    for i in range(size):
        for j in range(size):
            if (i, j) in obstacles:
                print("X", end=" ")
            elif (i, j) in trajectory:
                print("*", end=" ")
            else:
                print(".", end=" ")
        print()
    return


def generate_chessboard(size):
    return [[False] * size for _ in range(size)]

    
def generate_individual(size, obstacle_probability, start_pos, end_pos):
    individual = generate_chessboard(size)
    for i in range(size):
        for j in range(size):
            if random.random() < obstacle_probability:
                individual[i][j] = True
    individual[start_pos[0]][start_pos[1]] = False
    individual[end_pos[0]][end_pos[1]] = False
    return individual

def get_obstacles(individual):
    obstacles = []
    for i in range(len(individual)):
        for j in range(len(individual[i])):
            if individual[i][j] == True:
                obstacles.append((i, j))
    return obstacles

def mutate(individual, mutation_probability, start_pos, end_pos):
    size = len(individual)
    mutated_individual = [row[:] for row in individual]
    for i in range(size):
        for j in range(size):
            if random.random() < mutation_probability:
                mutated_individual[i][j] = not mutated_individual[i][j]      
    mutated_individual[start_pos[0]][start_pos[1]] = False
    mutated_individual[end_pos[0]][end_pos[1]] = False
    return mutated_individual

def crossover(parent1, parent2, start_pos, end_pos):
    size = len(parent1)
    half_size = size // 2
    
    child1 = [[None] * size for _ in range(size)]
    child2 = [[None] * size for _ in range(size)]
    
    selected_indices = random.sample(range(size * size), half_size)
    selected_positions = [(i // size, i % size) for i in selected_indices]
    
    for i in range(size):
        for j in range(size):
            if (i, j) in selected_positions:
                child1[i][j] = parent1[i][j]
                child2[i][j] = parent2[i][j]
            else:
                child1[i][j] = parent2[i][j]
                child2[i][j] = parent1[i][j]
    
    child1[start_pos[0]][start_pos[1]] = False
    child1[end_pos[0]][end_pos[1]] = False
    child2[start_pos[0]][start_pos[1]] = False
    child2[end_pos[0]][end_pos[1]] = False
    
    return child1, child2

# Retirer les obstacles inutiles (réduit le nombre de fitness=0)
def cleanup_chessboard(individual, trajectory, obstacles):
    for o in obstacles:
        if not set.intersection(
            {(o[0]-1, o[1]+1), (o[0], o[1]+1), (o[0]+1, o[1]+1),
             (o[0]-1, o[1]), (o[0], o[1]), (o[0]+1, o[1]),
             (o[0]-1, o[1]-1), (o[0], o[1]-1), (o[0]+1, o[1]-1)},
            set(trajectory)):
            individual[o[0]][o[1]] = False
    return
                            
def fitness_function(individual, start_pos, end_pos):
    obstacles = get_obstacles(individual)
    trajectory = dijkstra_chessboard(start_pos, end_pos, obstacles)
    if trajectory[1] > 20: # Sans cette condition, Dijkstra prend trop de temps
        cleanup_chessboard(individual, trajectory[0], obstacles)
    return trajectory[1]

def genetic_algorithm(size, start_pos, end_pos, population_size, obstacle_probability, mutation_probability, num_generations, hint=[]):
    population = hint + [generate_individual(size, obstacle_probability, start_pos, end_pos) for _ in range(population_size - len(hint))]
    
    for generation in range(num_generations):
        #print(f"Generation {generation+1}")
        fitness_scores = [fitness_function(individual, start_pos, end_pos) for individual in population]
        
        best_individual = population[fitness_scores.index(max(fitness_scores))]
        best_fitness = max(fitness_scores)
        #print(f"Best Fitness: {best_fitness}")
        
        new_population = [best_individual]
        
        while len(new_population) < population_size:
            parent1 = random.choices(population, weights=fitness_scores)[0]
            parent2 = random.choices(population, weights=fitness_scores)[0]
            
            child1, child2 = crossover(parent1, parent2, start_pos, end_pos)
            
            mutated_child1 = mutate(child1, mutation_probability, start_pos, end_pos)
            mutated_child2 = mutate(child2, mutation_probability, start_pos, end_pos)
            
            new_population.append(mutated_child1)
            new_population.append(mutated_child2)
        
        population = new_population
    
    best_individual = population[fitness_scores.index(max(fitness_scores))]
    best_fitness = max(fitness_scores)
    #print(f"\nBest Individual: {best_individual}")
    print(f"Best Fitness: {best_fitness}")
    return best_individual

size = 8
start_pos = (0, 0)
end_pos = (7, 7)
population_size = 200
obstacle_probability = 0.5
mutation_probability = 0.01
num_generations = 500
best=[]
hint=[]

# Utilisation basique (start et stop connus). Décommenter
##best = genetic_algorithm(size, start_pos, end_pos, population_size, obstacle_probability, mutation_probability, num_generations, [])
##s,e,o = start_pos, end_pos, get_obstacles(best)
##best_trajectory = dijkstra_chessboard(s,e,o)[0]
##draw_chessboard(size, o, best_trajectory)


# Le code ci-dessous demande beaucoup plus de temps
# Utilisation avec boucles sur start parcourant le quart Nord-Ouest et stop parcourant le quart Sud Est
# Utiliser le best précédent comme élément de la population initiale
for start_pos in ((x,y) for x in range(4) for y in range(4)):
    for end_pos in ((7-x,7-y) for x in range(4) for y in range(4)):
        hint_temp=[]
        for h in hint:
            temp = list(h)
            temp[start_pos[0]][start_pos[1]] = False
            temp[end_pos[0]][end_pos[1]] = False
            hint_temp.append(h)
        current_best = genetic_algorithm(size, start_pos, end_pos, population_size, obstacle_probability, mutation_probability, num_generations, hint_temp)
        best.append(current_best)
        s,e,o = start_pos, end_pos, get_obstacles(current_best)
        best_trajectory = dijkstra_chessboard(s,e,o)[0]
        draw_chessboard(size, o, best_trajectory)
        hint.append(current_best)

Best Fitness: 25
* X X * * X * * 
* . * X . * X . 
X X X X X X X * 
X * * X X * * X 
* X X * * X X X 
X * X X X X X * 
* X X * X * X * 
X * * X * X * . 
Best Fitness: 25
* X * * X X * * 
X * . X * * X . 
X X X X X X X * 
* . * X X * * X 
* X X * * X X X 
X * X X X X * * 
* X X * * X X . 
* . * X X * . * 
Best Fitness: 25
* X X * * X * * 
* . * X X * X . 
X X X X X X X * 
X * * X X X * X 
* X X * * X * X 
X * X X X X X * 
* X X * * X X * 
X * * X X * * X
Best Fitness: 25
X * * X X * * X 
* X X X * X X * 
X * X X * X X * 
* X X * X X * X 
X * X X * X * X 
* . X * X X X * 
* X X * X * X * 
X * * X X X * . 
Best Fitness: 25
X X * X X * * X 
* * X * * X X * 
X X X X X X X * 
* . * X X * * X 
* X X * * X X X 
X * X X X X . * 
* X X * * X X * 
X * * X X * * X 
Best Fitness: 25
X X * X X * * X 
* * X * * X X * 
X X X X X X X * 
* . * X X * * X 
* X X * * X X X 
X * X X X X * . 
* X X * * X X * 
X * * X X * * X 

Juste waouh pour la motivation à écrire ce programme, je vais essayer de le comprendre.

Je n'ai pas écrit beaucoup d'algorithmes (le côté aléatoire sûrement ^^) mais j'ai une idée pour accélérer le calcul de la fitness (Algorithme de Floyd-Marshal à la place de Dijkstra).

Avec ce nouvel algorithme, on calcule directement le diamètre du graphe au lieu de ne regarder qu'un point de départ et d'arrivée.

Mais je me demandais si le fait de définir un point d'arrivée et de départ n'améliorait pas le crossover. En effet, sans départ et arrivée fixe il y a plus de chances que les parents n'aient rien en commun. Autrement dit, moins de chance de générer des enfants aussi bons que leurs parents. thetapinch27, tu en penses quoi?

Est-ce qu'ajouter une méthode de matching entre parents pallierait à ce problème? Est-ce que ça se fait en algorithme génétique?

Il faut lire : "Je n'ai pas écrit beaucoup d'algorithmes génétique"

J'ai écrit beaucoup d'algorithmes mais rarement génétiques

Bonjour,

@LittleFox
Je ne suis pas très étonné, les algo G sont quelquefois "méprisés" (surtout par les mathématiciens ... _{je fais me faire assassiner} ) car ils s'apparentent plus à de la cuisine qu'à de la science (on n'a aucune garantie sur rien). Mais ils ont un intérêt immense dans beaucoup de problèmes concrets car souvent ce qui importe ce n'est pas d'avoir la meilleure solution mais un ensemble de solutions pas trop mauvaises et acceptables.
Pour Dijkstra, je pense que le coût calculatoire est faible dans ce cas particulier car j'utilise l'algo avec en moyenne 1 case sur 2 bloquée. Donc le "branching factor" est toujours faible. Mais en effet, si je réduis la proba de blocage d'une case (30% par exemple), le temps de calcul explose mais les solutions trouvées ne sont pas aussi bonnes qu'avec 0.5.  C'est effectivement une restriction qui limite la capacité d'exploration.
Pour le second point : en fait l'algo tourne déjà à (start, stop) imposé donc tous les parents et tous les enfants ont toujours le même (start, stop). J'ai ensuite une boucle qui lance l'algo G autant de fois qu'il y a de couples (start, stop) - voir le dernier bloc. D'ailleurs pour des raisons de symétrie j'aurais pu me limiter à parcourir le quart NO pour start et la moitié du quart SE pour l'arrivée. Ce qui ferait 160 run au lieu de 256.
La perf globale n'est pas terrible malgré tout. Certains "best" sont améliorables avec un tout petit peu de bon sens. Parfois, lancer l'algo G plusieurs fois avec le même (start, stop) conduit à des fitness différents même s'ils sont toujours pas trop mauvais. Faudrait comparer avec ce que donnerait une méthode brute-force pour dire si le qualificatif "génétique" est utile ici.

Voici ma tentative pour un algorithme génétique
Forte utilisation de numpy
Floyd-Warshall, on est agnostique du départ et de l'arrivée. Et indépendant du nombre de pions sur l'échiquier.
Le plus dur aura été de calculer la matrice d'adjacence tout en utilisant la vectorisation de numpy.
J'ai tenu compte du nombre de pions dans la fitness avec une approche où on en tient peu compte pour les 100 premières générations puis de plus en plus.
J'ai eu des soucis où l'ensemble de la population était composée  de clones du même individu. Maintenant, je supprime tous les clones avant de calculer la fitness. Ça à l'air de marcher
La fitness est normalisée de façon à ce que le meilleur ait deux fois plus de chance que le plus mauvais.
Je garde les 10 meilleurs individus pour empêcher ma population de régresser.
On pourrait augmenter la probabilité de mutation quand la population stagne. Je ne l'ai pas fait.

Le code est disponible sur github:

 Cliquez pour afficher

import multiprocessing
import random
from itertools import count

import numpy

# See https://www.ilemaths.net/sujet-deplacements-sur-un-echiquier-888158.html


# Chess grids are represented by a numpy array of 8x8 int
# where 0 is a pawn (X), 1 is open (.) and 2 is open but part of the longest path(*).
# We are trying to find a grid where a queen has the longest shortest path between any square of the grid.

RNG = numpy.random.default_rng()


def print_grid(grid):
    print('\n'.join(' '.join({0: 'X', 1: '.', 2: '*'}[cell] for cell in row) for row in grid))


def get_adjacency(grid: numpy.ndarray):
    """Get the adjacency matrix of the grid for a queen.

    get_adjacency(grid)[i, j] is True if and only if there is a queen move from cell i to j.
    Cells are numbered in numpy.ravel default order.
    """
    open_cells: numpy.ndarray = grid > 0
    adjacency = numpy.diag(open_cells.ravel())

    grid_right = open_cells.copy()
    for k in range(1, 8):
        grid_right[:, :-1] &= grid_right[:, 1:]
        grid_right[:, -1] = False
        adjacency |= numpy.diag(grid_right.ravel()[:-k], k=k)

    grid_down = open_cells.copy()
    for k in range(1, 8):
        grid_down[:-1, :] &= grid_down[1:, :]
        grid_down[-1, :] = False
        adjacency |= numpy.diag(grid_down.ravel()[:-8 * k], k=8 * k)

    grid_descending = open_cells.copy()
    for k in range(1, 8):
        grid_descending[:-1, :-1] &= grid_descending[1:, 1:]
        grid_descending[-1, :] = False
        grid_descending[:, -1] = False
        adjacency |= numpy.diag(grid_descending.ravel()[:-9 * k], k=9 * k)

    grid_ascending = open_cells.copy()
    for k in range(1, 8):
        grid_ascending[1:, :-1] &= grid_ascending[:-1, 1:]
        grid_ascending[0, :] = False
        grid_ascending[:, -1] = False
        adjacency |= numpy.diag(grid_ascending.ravel()[7 * k:], k=-7 * k)

    adjacency |= adjacency.transpose()

    return adjacency


def get_distances(grid):
    """Get the distance between each pair of open cell in the grid.

    Only open cells are returned. They are numbered in numpy.ravel default order.
    A distance of 127 is "infinite", there is no path between the cells.
    """
    adjacency = get_adjacency(grid)
    open_cells: numpy.ndarray = (grid > 0).ravel()

    distances = adjacency.astype(numpy.uint8)
    distances = distances[open_cells, :]
    distances = distances[:, open_cells]
    distances[distances == 0] = 127
    numpy.fill_diagonal(distances, 0)

    for k in range(distances.shape[0]):
        numpy.minimum(distances, distances[:, k:k + 1] + distances[k:k + 1, :], out=distances)

    return distances


def get_diameter(grid):
    """Get the diameter of the grid.

    The diameter of a grid is the longest of the shortest paths for a queen for all pair of cells in the grid.
    """
    distances = get_distances(grid)
    distances[distances == 127] = 0

    return distances.max()


def get_longest_path(grid):
    """Set cells of the grid on the longest path to 2."""
    distances = get_distances(grid)
    distances[distances == 127] = 0

    start, end = divmod(distances.argmax(), distances.shape[0])

    path = []
    current = start
    while current != end:
        path.append(current)
        current = numpy.argmax((distances[current, :] == 1) & (distances[:, end] == distances[current, end] - 1))

    path.append(end)

    grid = grid.astype(numpy.uint8)
    grid[numpy.where(grid > 0)[0][path], numpy.where(grid > 0)[1][path]] = 2

    return grid


def crossover(population, fitness, nb_children):
    """Create a new population from the current population.

     The parents are selected proportionally to their fitness.
     """
    new_population = numpy.full((nb_children, 8, 8), False)
    noise = RNG.random(new_population.shape) < .5

    for child in range(nb_children):
        parents = random.choices(range(population.shape[0]), weights=fitness, k=2)
        new_population[child] = numpy.where(noise[child], population[parents[0]], population[parents[1]])

    return new_population


def mutate(population, p):
    """Mutate each gene in a whole population with a probability p."""
    noise = RNG.random(population.shape) < p
    population ^= noise


def get_score(grid):
    return get_diameter(grid), (grid == 0).sum()


def get_fitness(population, generation, worker_pool):
    scores = numpy.array(worker_pool.map(get_score, population), dtype=float)
    fitness = 64 * scores[:, 0] - (1 - 1 / (1 + generation / 100)) * scores[:, 1]
    return 2 ** ((fitness - fitness.min()) / (fitness.max() - fitness.min()))


def main(population_size=200, pawn_probability=0.5, survivors=10):
    population = RNG.random((population_size, 8, 8)) < pawn_probability

    best_score = (0, 0)
    with multiprocessing.Pool(1) as worker_pool:
        for generation in count():
            population = numpy.unique(population, axis=0)
            fitness = get_fitness(population, generation, worker_pool)
            order = fitness.argsort()

            best_grid = population[order[-1]]
            score = get_score(best_grid)
            if score > best_score:
                best_score = score
                print(f"Generation: {generation}")
                grid = get_longest_path(best_grid)
                print_grid(grid)
                print(score)
                print()

            children = crossover(population[order[survivors:]], fitness[order[survivors:]],
                                 nb_children=population_size - survivors)
            mutate(children, 1 / 64)
            population = numpy.concatenate((population[order[-survivors:]], children))


def validate(grid: str | numpy.ndarray):
    if isinstance(grid, str):
        grid = numpy.array(grid.split()).reshape(8, 8) != 'X'
    print_grid(get_longest_path(grid))
    print(get_score(grid))


if __name__ == "__main__":
    main()

* * X * * X * *
. X * . X * X .
* X X X X X X *
X * X * . X * X
* X X X * X * X
* . X * X X X *
X * X * X * X *
* . X . * X * .

Generation: 1831
* * X * * X * *
. . X . X * X .
X * X * X X X *
* X X X * X * X
* . X * . X X *
X * X X X X * X
* X X * * X X *
* . * X X * * .
(25, 30)