Morpion
Solitaire MS1 par C.Klipfel HOME-PAGE
1. Quelques
définitions.
1.1 Nombres de
points sur la feuille:
Soit N0 les points de départ , N0 = 36
N le nombre de points
ajoutés. (C'est celui qu'on veut maxi à la fin !)
K le nombre total
de points sur la feuille.
1.2 Instant du jeu
t
On prendra les
conditions initiales pour t=0 les points de départ N0
Avec N(0)=0 et
K(0)= N0
1.3 Variable
connexe ki
C'est le nombre de
points du jeu qui ont i connections.
Exemple:
si k5 = 3 ça veut dire qu'il y a 3 points avec 5
connections
Si k0 =
12 il y a 12 points avec 0 connections.
Dans le jeu
0<i<8
1.4 Potentialité
p(M)
C'est le nombre de directions
ou peut se connecter un points Mi du jeu.
Avec 0<p(M)<8
Exemple: Un point
donné Mi qui peut se connecter à 5 directions p(Mi)=5
On appelle P la
potentialité totale du jeu . P0 la
potentialité de départ
2 Relations
On voit que 
(1)
K(t) = N0+N(t)
P0 = 8 N0
La connexité et la
potentialité sont complémentaires de 8.
S'il y a déjà 2
directions de prise il ne lui reste plus que (8-2) potentialités.
Soit par exemple
l'ensemble des points M(i),M(i+1) et M(i+2) de même connexité 2
On aura par
ailleurs k2 = 3
La somme des
potentialités pour ces trois points P(M(i))+P(M(i+1))+P(M(i+2))
sera de (8-2)X3
Soit, si la
connexité de ces 3 points était de i, une potentialité de (8-i)ki.
On peut généraliser
cela à l'ensemble des points du jeu soit finalement.
(2)
ou
encore en développant
soit finalement la
relation fondamentale:
(3)
3 Evolution du jeux.
Lorsqu'on rajoute un point sur la grille on rajoute
8 potentialités, mais en joignant les 5 points on fait perdre également 8
potentialités. 2 pour les points extrêmes et 6 pour les 3 autres points du
segment. On a donc une évolution à potentialité constante.
(Sauf si on joint 5 croix sans rajouter de
point.)
La potentialité P(t) est constante et égale à
celle du début de jeu soit P0.
La formule (2) peut donc s'écrire 
soit finalement:
Cette formule peut être vérifiée dans un des
logiciels. Ms13-13.exe
En résumé, on a 2 équations d'état qui régissent
le jeu à un instant t:
Résultante connexe:
(1) ou 
Moment connexe:
(4)ou 
(5)
4)
Formulation différentielle
En réalité les ki
sont fonction de t ki=ki(t)
En utilisant les équations (1) et (4) écrites
aux instants t et t+1 on obtient:
K(t+1)-K(t)=1 ou N(t+1)-N(t+1)-N(t)=1 (même
si on ne met pas de nouveau point).
On note ki(t+1)-ki(t)=Dki
D'ou
les relations 
Dki = 1 (6)
8(N(t+1)-N(t))=i(ki(t+1)-ki(t)) = 8
iDki = 8 (7)
On constate dans (7) que Dk0
n'est pas concerné
Chaque Dki
est majoré
"i
Dki 
La variation de la résultante et du moment
connexe sont donc constants.
5) Critères
de fin de jeux:
On constate que vers la fin du jeu k0
= 0
K1 est au minimum égal à 1 si on
rajoute le dernier point .
Pour un jeu intéressant, probablement k8
est le plus important
L'équation (2) nous dit que 
Soit
Une distribution des ki
indépendants de K. Il suffirait donc de trouver une distribution qui marche et
avec l'équation (1) de calculer le K(t) qui lui correspond. Malheureusement k8,
qui est le plus important en fin de jeu n'intervient pas!.
L'équation (5) est plus intéressante, K0 n'intervient pas et le poids des indices
forts est prépondérant en particulier k8. La somme doit être
multiple de 8. On sait qu'on aura toujours pour le premier coup k1=2
et k2=3 pour vérifier K(1)=1=(1/8)(k1+2k2).
La question est : une distribution des ki qui respecte les équations(1)(5)(6)
et (7) est-elle nécessairement un jeu de morpion ?
Si c'est le cas on pourra trouver N maxi
……Malheureusement vous pouvez le constater vous même, c'est pas le cas ! Euristic1.exe
En effet au 3° coup il nous place un k7 tombé
du ciel ! La seule contrainte imposée était Dk0 <=0. Sans doute un
bug !
Il faut imposer également que K1>=1 et que
Dk8>=0
ainsi que d'autres contraintes que l'on va découvrir avec le logiciel Ms1-13-1
qui permet de voir varier les Dki dans un vrais jeu..
6)
Détermination d'une borne de jeux maxi
Le jeu s'arrête quand les potentialités sont situées tel qu'il n'existe plus de directions comme associés. C'est à dire des points isolés où que ces potentialités soient rejetées sur les pts frontière du graphe obtenu.
Soit Kf nombre de points de la frontière
Kint nombre de points à l'intérieur non associables
Cherchons une relation entre la valeur des potentialités extérieures à une courbe fermée simplement connexe en fonction du nombre de ces points
6.1 Potentialité d’un point Mk
Soit un point de la frontière Mk,
on défini le vecteur 
et
unitaires tel que 
( Mk,
M k+1) et 
= ( Mk, M
k-1)
Puis les angles en radian Өki =
(
, ) et Өkj = ( ,
)
Dans ces conditions la potentialité du point Mk
, P Mk
s’écrit :
P Mk = 
,)
4/π – 1 = [(,
)+(,
)]
4/π – 1 = (Өkj+ Өki)4/π – 1
Soit finalement
P Mk = (Өkj- Өki)4/π – 1
6.2 Potentialité totale
Pour tous les points de la frontière la
potentialité totale PKf sera
Pour plus de clarté on notera les doubles
indices Өkj par Өk,j
Or, pour les points d’une frontière il existe une relation entre les Өk+1,j et Өk,i
Өk,i = Ө k,k+1 et
Өk,j = Өk,k-1
D’où 
-Өk+1,k)4/π-1]
Or on a Өk+1,k – Өk,k+1 = π
D’où 
=3Kf + 
Pour une courbe fermée on vérifie que
D’où la formule recherchée :
Pkf = 3 Kf + 8
Donc une fonction linéaire de Kf
C’est facilement vérifiable sur des figures
simples fermées. On peut vérifier le résultat en
Supposant que Pkf =
a Kf + b et ensuite avec 2 figures simples déterminer a et b
On obtient bien sur le même résultat..
6.3 Nombre de points maxi sur la frontière
On a vu que le jeu évolue à potentialité
constante Po = 8 * 36 = 288
Il est évident que la potentialité intérieure
Pint n’est pas nulle.
Son minimum est de telle que Kf est
entier Pint
mini = 1
D’où Kf max = 93
Reste à trouver une figure qui englobe le
maximum de points avec une frontière de 93 points
Il est évident dans notre cas que ce sera un
polygone
Dans le cas d’un système continu c’est un
cercle de rayon R
On a 2πR = 93 Kint = Kf2/4π
= 688
Ce qui ferait un total
K = Kint + Kf = 781
K < 781
Ce qui est certain ,
c’est que le jeux maxi est inférieur à cette limite reste à trouver une forme
finale optimale
7) A suivre
…..