[Tutorial] Stratégie Minière Assistée par Ordinateur

Contrairement à Fandemagic qui a le bon réflexe d'aller consulter les tutoriaux de référence sur board.ogame.fr, je prendrai le risque de réexposer ici une idée déjà publiée. J'ai pour ma part la flemme de compulser les brevets et droits d'auteurs ! Un éventuel plagiat ne serait imputable qu'au fait que les mêmes hypothèses aboutissent aux mêmes conclusions...

Mon objectif est de vous présenter une stratégie minière assistée par ordinateur. L’ordinateur vous servira de guide pour répondre à la question : quelle mine améliorer ? Par exemple, dois-je améliorer une mine de métal tout de suite, ou bien attendre pour pouvoir améliorer une mine de cristal ? Quelle est la meilleure séquence d’améliorations à appliquer ?

« Meilleure ? » Il s’agit donc d’une stratégie d’optimisation.

Que cherche-t-on à optimiser ? Un minier cherche généralement à maximiser son score au classement général. C’est donc cela que je vais chercher à optimiser également. Ou presque, car j’inclurai dans le score le stock de ressources disponibles. Je chercherai donc à optimiser la somme (Ressources Investies + Ressources en Stock). Inclure les « Ressources en Stock » crée un effet « lissant » qui rendra plus justes les calculs. Ceux qui connaissent l’effet « horizon » dans les logiciels d’échecs me comprendront.

En fonction de quoi cherche-t-on à optimiser le score ? En fonction...

- de conditions initiales : à l’instant t0 = 0, on a un niveau de départ des mines, et un stock disponible de départ ;
- du temps imparti T
- de la séquence d’améliorations choisie, dès lors qu’elle « tient » dans le temps imparti.

Nous nous bornerons à étudier les séquences « maximales » tenant dans le temps imparti (celles auxquelles on ne peut ajouter aucun autre amélioration, sous peine de dépasser le temps imparti).
On arrête les calculs à t1 = t0 + T. On évalue le score de chaque séquence maximale en fonction du niveau d’arrivée des mines et des stocks disponibles.

Y a-t-il des hypothèses simplificatrices ? Oui, elles sont assez nombreuses :

1 ) On ne s’intéresse pas à un démarrage d’univers. On suppose que l’univers commence à « avoir de la bouteille ».
2 ) L’énergie s’acquiert à pas cher, en faisant usage de satellites solaires, de coût négligeable et négligé.
3 ) Seules deux ressources importent vraiment : le métal et le cristal.
4 ) Négligeables sont aussi les investissements en flottes, défenses, technologies et autres bâtiments
5 ) Bref, seuls deux bâtiments importent vraiment dans cette simulation : la mine de métal et la mine de cristal.
6 ) Les temps de construction des bâtiments sont supposés être égaux à 0.
7 ) Au lieu de considérer 9 colonies, on n’en considère qu’une.
8 ) Le joueur qui joue cette stratégie est présent à tous les moments-clé : dès qu’il est possible de lancer l’amélioration de la bonne mine (choix dicté par cette stratégie), le joueur lance cette amélioration sans perdre de temps.
9 ) On ne se fait pas raider

Bref, c'est un stratégie minière pure et dure avec 100% de réinvestissement de la production minière dans la production minière.

L’état, à l’instant t, de mon système, se résume à 4 variables :

- Le niveau Nm de la mine de métal
- le niveau Nc de la mine de cristal
- le stock Sm de métal
- le stock Sc de cristal

A partir des variables précédentes, on peut calculer :

- la productivité Pm et Pc des mines
- les coûts, en métal et en cristal, de l’amélioration de la mine de métal (Kmm, Kcm)
- la même chose pour l'amélioration de la mine de cristal (Kmc, Kcc)
- les durées d'attentes de constitution des fonds nécessaires aux améliorations de mines

Ces calculs sont tantôt dictés par des formules spécifiquement Ogamiennes, tantôt dictées par des formules classiques.

Formules Ogamiennes :

Productivité horaire de la mine de métal en fonction de son niveau Nm.
Pm = 20 + 30 * Nm * 1.1^Nm

Productivité horaire de la mine de cristal en fonction de son niveau Nc.
Pc = 10 + 20 * Nc * 1.1^Nc

Coût en métal de l’amélioration de la mine de métal pour passer du niveau Nm au niveau Nm + 1
Kmm = 60 * 1.5^Nm

Coût en cristal de l’amélioration de la mine de métal pour passer du niveau Nm au niveau Nm + 1
Kcm = 15 * 1.5^Nm

Coût en métal de l’amélioration de la mine de cristal pour passer du niveau Nc au niveau Nc + 1
Kmc = 48 * 1.6^Nc

Coût en cristal de l’amélioration de la mine de cristal pour passer du niveau Nc au niveau Nc + 1
Kcc = 24 * 1.6^Nc

Formules des durées d'attente

Calculons d'abord les durées d’attente unitaires. Combien de temps faut-il attendre, par exemple, pour réunir la composante métal (M) du coût d'amélioration d'une mine de cristal (C) ?

Si Sm >= Kmc,
Alors Dmc = 0
Sinon Dmc = (Kmc – Sm) / Pm

Ce que je noterai en abrégé :
Dmc = (Sm >= Kmc) ? 0 : (Kmc – Sm) / Pm

Cette formule, expliquée ici pour le cas MC (composante M de la mine de C) existe en fait en 4 variantes (MM/CM/MC/CC). Les voici :


Dmm = (Sm >= Kmm) ? 0 : (Kmm – Sm) / Pm
Dcm = (Sc >= Kcm) ? 0 : (Kcm – Sc) / Pc
Dmc = (Sm >= Kmc) ? 0 : (Kmc – Sm) / Pm
Dcc = (Sc >= Kcc) ? 0 : (Kcc – Sc) / Pc


Quand il s’agit d’attendre que les fonds soient réunis pour un bâtiment, il y a une ressource métal ou cristal « facteur limitant » qu’il faut attendre plus que l’autre. La durée d’attente du bâtiment est donc le « max » des durées d’attente de ses composantes métal et cristal.

Durée d'attente pour améliorer la mine de métal
Dm = max(Dmm, Dcm)

Durée d'attente pour améliorer la mine de cristal
Dc = max(Dmc, Dcc)

Première durée d'attente (pour améliorer le bâtiment qui sera disponible le premier)
Dmin = min(Dm, Dc)

Seconde durée d'attente (pour améliorer le bâtiment qui sera disponible en second)
Dmax = max(Dm, Dc)

Commençons par chercher l’algorithme « à la main ». Démarrons par exemple avec des stocks nuls et des mines de niveau 0. (Si ça vous choque, notamment par considération de l’hypothèse simplificatrice n°1, imaginez que ce sont des mines de niveau 30/27).

Notre stock initial est nul. On ne peut rien construire. Attendons d’avoir le stock disponible pour construire quelque chose. Pendant ce temps, notre score augmente de (20+10) par heure.
A un certain instant t1, il nous est possible de construire une mine. Le calcul montre que cette mine est une mine de cristal (et que t1 = 2.4h). Deux possibilités : soit on upgrade tout de suite dans la mine de cristal, soit on attend jusqu’à un instant ultérieur t2 (t2 = 3.0h) pour upgrader la mine de métal.

Supposons qu’on investisse à t1 dans la mine de cristal. Notre score ne change pas, il reste de 72. En effet, la somme « Ressources Investies + Stock Disponible » reste inchangée. Le score ne fait que changer de nature, depuis Stock Disponible vers Ressources Investies. Ce qui change, en revanche, c'est notre productivité qui passe à (20+32)
Mais là, aïe aïe aïe ! Que l’attente est longue avant de pouvoir construire une nouvelle mine...

Supposons au contraire, qu'à l'instant t1, on n’ait pas investi tout de suite mais attendu un tout petit peu (0.6 h), jusqu’à t2 pour investir en métal. On aurait bien vite eu de nouveau de quoi investir dans une cristal 1 voire dans une métal 2...



Sur l’illustration, je n’ai développé que les 2 ou 3 premières ramifications de l’arbre des choix. En faisant un bilan à l’instant t = 6.15h par exemple, on a l'impression (sans doute très juste) que la séquence « C1 » en vue de construire C2 (qu’elle n’a pas le temps de construire d’ailleurs) est lamentable comparée à la séquence « M1 M2 C1 ».

Il est possible d'écrire un programme "force brute" qui effectue tous ces calculs automatiquement et qui en déduise la meilleure stratégie sur la profondeur choisie.

J'ai développé un tel programme et le livre à la communauté dans sa version PC/Windows :
http://xenomorphext.ifrance.com/download/ogtimise.bmp
- faites un clic droit / enregistrer la cible du lien sous... pour télécharger ce programme
- renommez le en "ogtimise.exe"
- contrôlez qu'il est sain avec votre antivirus préféré, sait-on jamais

Ce programme ne s'utilise qu'en mode "Commandes MS-DOS". Il auto-décrit sa syntaxe d'utilisation si vous le lancez sans paramètres :

Code:

ogtimise

Code:

Usage : ogtimise <mode> <Nm> <Nc> <Sm> <Sc> <dt>
  (ou : ogtimise -h)
  avec :
  <mode> =
          0 ... mode interactif
          1 ... mode batch silencieux
          2 ... mode batch verbeux (evaluations finales)
          3 ... mode batch verbeux (equations de droites)
  <Nm>  = niveau initial de la mine de metal
  <Nc>  = niveau initial de la mine de cristal
  <Sm>  = stock initial de metal
  <Sc>  = stock initial de cristal
  <dt>  = profondeur de calcul = duree de jeu simulee (h)

Voici une trace d'exécution possible dans le cadre d'une utilisation normale :

Code:

ogtimise 2 0 0 0 0 6.15

Code:

Situation initiale :
Instant :    -0.00h
Niveaux : M0 C0
Stocks  :    0.00M    0.00C
Score  :    0.00
Prod.  :    20.00M/h    10.00C/h
Couts  : Mine de M :    60.00M    15.00C Mine de C :    48.00M    24.00C
Duree de jeu simulee :    6.15h
#1: 'M1 M2 ' (345.94)
#2: 'M1 M2 C1 ' (345.94)
#3: 'M1 M2 C1 ' (345.94)
#4: 'M1 C1 M2 ' (359.46)
#5: 'M1 C1 M2 ' (359.46)
#6: 'M1 C1 C2 ' (358.82)
#7: 'M1 C1 C2 ' (358.82)
#8: 'C1 M1 ' (291.75)
#9: 'C1 M1 ' (291.75)
#10: 'C1 ' (267.00)
Meilleure sequence trouvee : M1 C1 M2
Score final :  359.46

On peut faire en sorte que ce programme dresse la liste des segments de droites "score en fonction du temps".

Code:

ogtimise 3 0 0 0 0 6.15

Code:

Situation initiale :
Instant :    -0.00h
Niveaux : M0 C0
Stocks  :    0.00M    0.00C
Score  :    0.00
Prod.  :    20.00M/h    10.00C/h
Couts  : Mine de M :    60.00M    15.00C Mine de C :    48.00M    24.00C
Duree de jeu simulee :    6.15h
#1: M0C0 | [-0.00;3.00] | M++ | 0.00 + 30.00 * t
#2: M1C0 | [3.00;4.70] | M++ | -99.00 + 63.00 * t
#3: M2C0 | [4.70;6.15] | M== | -285.05 + 102.60 * t
#4: M2C0 | [4.70;6.15] | C++ | -285.05 + 102.60 * t
#5: M2C1 | [6.15;6.15] | M== | -420.35 + 124.60 * t
#6: M2C1 | [6.15;6.15] | C== | -420.35 + 124.60 * t
#7: M1C0 | [3.00;3.91] | C++ | -99.00 + 63.00 * t
#8: M1C1 | [3.91;5.60] | M++ | -184.92 + 85.00 * t
#9: M2C1 | [5.60;6.15] | M== | -406.83 + 124.60 * t
#10: M2C1 | [5.60;6.15] | C== | -406.83 + 124.60 * t
#11: M1C1 | [3.91;5.35] | C++ | -184.92 + 85.00 * t
#12: M1C2 | [5.35;6.15] | M== | -326.29 + 111.40 * t
#13: M1C2 | [5.35;6.15] | C== | -326.29 + 111.40 * t
#14: M0C0 | [-0.00;2.40] | C++ | 0.00 + 30.00 * t
#15: M0C1 | [2.40;5.40] | M++ | -52.80 + 52.00 * t
#16: M1C1 | [5.40;6.15] | M== | -231.00 + 85.00 * t
#17: M1C1 | [5.40;6.15] | C== | -231.00 + 85.00 * t
#18: M0C1 | [2.40;6.15] | C== | -52.80 + 52.00 * t
Meilleure sequence trouvee : M1 C1 M2
Score final :  359.46

L'intérêt de ces traces est de les injecter dans un grapheur de maths. Voilà ce que ça peut donner :

Score en fonction du temps et de la séquence d'améliorations.
(t0=0: Nm=0, Nc=0, Sm=0, Sc=0 ; t1=6.15)


Score en fonction du temps et de la séquence d'améliorations.
(t0=0: Nm=0, Nc=0, Sm=0, Sc=0 ; t1=21)


Sur ce dernier graphique, j'ai représenté en blanc les séquences issues du choix initial M1, en gris celles issues du choix initial C1. Sans que cela constitue une preuve, on voit qu'il y a un écart de points irréversible entre les "enveloppes" des 2 familles de courbes. D'où l'importance de faire le bon choix à chaque fois...

Voilà, j'arrête là cette présentation pour le moment, même si je continue de réfléchir sur ce sujet.

il y en a qui se complique vraiment la vie :p

oui de plus si c'est un programme ou qui fais des choses a ta place .

Ben c'est interdit et il n'y aucun plaisir de jeux!!!!!

Le programme ne fais que calculer la meilleure option à prendre. Il ne joue pas.

Tres impressionant quand meme!

Chapeau pour tout ce que tu as mis, j'ai lu les grandes lignes, mais je crois qu'il me faudrait facilement 1 ou 2 heures pour aller au bout de tout ce que tu as mis!
Je plancherai dessus ce week-end, mais ca montre a quel point meme pour les "simples" miniers Ogame peut se reveler tres compliqué si on s'y penche un peu!

Pas eu le tmeps de tout lire encore, mais j'adore.

Et vivement els algorithmes d'optimisation