Archives pour la catégorie Problèmes d’échecs

Tout ce qui concerne les problèmes d’échecs

Popeye et les kangourous

Comme l'indique le diagramme ci-contre, le sujet d'aujourd'hui est un problème d'échecs.

Depuis le 13 novembre est lancé sur le site caissa-france.net le concours du pat aidé de série le plus long aboutissant au diagramme ci-contre.

La pièce inhabituelle en ç5 et é5 est un kangourou. Cette pièce saute au-dessus de 2 autres pièces et atterrit juste après la 2e. Les détails sont accessibles depuis la page donnant le règlement du concours.

Popeye est un logiciel gratuit qui résout toutes sortes de problèmes d'échecs, notamment les pat aidés de série avec des kangourous au diagramme.

Pour m'aider dans ma recherche, j'ai écrit un programme, en shell, qui soumet à Popeye toutes les positions possibles pour le roi et les kangourous noirs, en imposant un dernier coup blanc. Ci-dessous se trouve le listing de ce programme. Dans cet exemple, le coup blanc qui fait pat est Ré2-d2.

Il est évident qu'une telle recherche est très longue. Je n'ai pas eu le temps de faire des recherches pour 6 pièces avec tous les derniers coups blancs possibles. La recherche avec 7 pièces au diagramme, en ajoutant par exemple un kangourou noir, est encore énormément plus longue.

L'intérêt de ce programme est de voir les positions intermédiaires trouvées, et d'en tirer un sentiment sur les idées qui marchent et celles qui ne marchent pas. Pour atteindre le record, il faut encore un gros travail sur l'échiquier.

#!/bin/sh

casesRoi="a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8 c1 c2 c3 c5 c6 c7 c8 d4 d6 d7 d8 e5 e6 e7 e8 f4 f6 f7 f8 g1 g2 g3 g4 g5 g6 g7 g8 h1 h2 h3 h4 h5 h6 h7 h8"

casesKangourou="a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8 c1 c2 c3 c4 c5 c6 c7 c8 d1 d2 d4 d5 d6 d7 d8 e1 e3 e5 e6 e7 e8 f1 f2 f3 f4 f5 f6 f7 f8 g1 g2 g3 g4 g5 g6 g7 g8 h1 h2 h3 h4 h5 h6 h7 h8"

FOUND=0
COOKED=1
NO_SOL=2

choixRoi()
{
    ka1=$1
    ka2=$2

    for roi in $casesRoi
    do
	if test $roi = $ka1 -o $roi = $ka2
	then
	    :
	else
	    dichotomie $roi $ka1 $ka2
	fi
    done
}

dichotomie()
{
    roi=$1
    ka1=$2
    ka2=$3

    min=2
    max=100

    resoudre $roi $ka1 $ka2 $min
    resMin=$?
    if test $resMin -ne $NO_SOL
    then
	return
    fi

    resoudre $roi $ka1 $ka2 $max
    resMax=$?
    if test $resMax -eq $NO_SOL
    then
	echo $ka1$ka2${roi}n0 >> noSolution
	return
    elif test $resMax -eq $FOUND
    then
	return
    fi

    (( delta= $max - $min ))
    while test $delta -gt 1
    do
	(( milieu=($max + $min) / 2 ))
	resoudre $roi $ka1 $ka2 $milieu
	res=$?
	case $res in
	    0)
		return
		;;
	    1)
		max=$milieu
		resMax=$res
		;;
	    2)
		min=$milieu
		;;
	esac
	(( delta= $max - $min ))
    done
}

resoudre()
{
    roi=$1
    ka1=$2
    ka2=$3
    n=$4

    file=$roi.txt
    cat >$file < result.txt 2>/dev/null
    ok=`grep -c "e2-d2" result.txt`
    set `wc -l result.txt`
    nbLignes=$1
    if test ${nbLignes} -ge 30
    then
	result=$COOKED
    elif test ${nbLignes} -eq 28
    then
	result=$NO_SOL
    elif test ${nbLignes} -eq 29
    then
	if test $ok -eq 1
	then
	    echo -n "+"
	    dir=n${n}
	    if test ! -d $dir
	    then
		mkdir $dir
	    fi
	    res=$dir/$ka1$ka2${roi}n${n}.txt
	    cp $file $res
	    cat result.txt >> $res
	fi
	result=$FOUND
    else
	res=etrange$ka1$ka2${roi}n0.txt
	cp $file $res
	cat result.txt >> $res
	result=$NO_SOL
    fi
    rm $file
    rm result.txt
    return $result
}

for ka1 in $casesKangourou
do
    echo ""
    echo -n "Position $ka1 :"
    for ka2 in $casesKangourou
    do
	if [[ $ka2 > $ka1 ]]
	then
	    echo -n " $ka2"
	    choixRoi $ka1 $ka2
	fi
    done
done