Quelle est votre prochaine décision?

18

Ce défi consiste à écrire une fonction minimax dans la langue de votre choix, pour générer le prochain meilleur mouvement dans un jeu NxN de tic-tac-toe étant donné l' état actuel de la carte . L'entrée du tableau peut être acceptée en tant que matrice, collection 2D ou tout autre élément qui a du sens pour vous, mais qui respecte les règles . La sortie étant le prochain meilleur coup pour le tour de celui qui est actuellement , où X est considéré comme ayant commencé .

Contexte rapide de l'algorithme Minimax

L'idée de base de l'algorithme minimax est d'énumérer tous les résultats possibles en tant que DAG, puis de les pondérer par l'avantage que la séquence de mouvements a pour le joueur, déterminé par le premier mouvement effectué. Tous les résultats possibles sont ensuite «regroupés» par le premier coup et sont notés sur la base de la somme de tous les résultats (-1 pour une défaite, 0 pour une égalité et 1 pour une victoire). Dans les implémentations qui nécessitent plusieurs joueurs pour jouer, vous énumérez tous les mouvements possibles du joueur, ainsi que toutes les réponses possibles des adversaires. Par exemple, dans un jeu de tic-tac-toe (après le premier coup), il y a 8 premiers coups possibles que vous pouvez faire, et ils peuvent tous sembler égaux lors de l'analyse du tour suivant uniquement. Mais en parcourant tous les résultats possibles pour chaque ensemble de mouvements possibles qui aboutit à un résultat final et en les résumant tous,

Pour un résumé meilleur, plus approfondi et contextuel de l'algorithme mini-max en termes de tic-tac-toe, lisez plus ici: http://neverstopbuilding.com/minimax

XKCD (solution 3x3 uniquement)

Tous les mouvements possibles pour un jeu de tic-tac-toe 3x3.

Les règles

  • N'importe quel langage peut être utilisé, mais aucune bibliothèque minimax externe n'est autorisée.
  • La sortie peut être une coordonnée (0-n, 0-n) ou un nombre (1-n * n) indiquant le meilleur mouvement suivant.
    • En plus de cela, vous devez être en mesure d'identifier quand le meilleur scénario est une perte ou une égalité au lieu d'une victoire.
    • La façon dont vous indiquez une perte ou une égalité est, encore une fois, à vous de décider.
  • L'entrée doit utiliser les X et O traditionnels, et vous devez supposer que X se déplace en premier; les espaces vides peuvent être représentés par n'importe quoi.
  • Vous pouvez supposer que toutes les entrées entrant dans votre programme ont n O et n + 1 X, en d'autres termes, vous pouvez supposer que vous obtenez une carte bien formée.
  • L'état actuel de la carte doit être la seule entrée de votre programme, si vous utilisez la récursivité, des méthodes d'assistance doivent être mises en place pour faciliter les exigences d'entrée. Voir /codegolf//a/92851/59376 pour des éclaircissements.
  • Toute valeur de 10> = n> = 1 doit être prise en charge; si votre programme "arrive à expiration" pour n> 10, je trouve cela également acceptable, car certaines langues ont une puissance de traitement considérablement inférieure (en particulier en utilisant des consoles Web).

Juger

  • Il s'agit de code-golf, donc le nombre d'octets le plus bas du programme gagne et les failles standard sont universellement interdites.
  • En cas d'égalité, le programme qui prend en charge le plus grand «n» l'emportera.

Exemples d'entrées

2x2

[[X,O]
 [-,-]]

Sortie: 2 ou [0,1] (3 ou [1,1] serait également sans doute correct) (Une forme d'indication de l'emplacement, arbitraire tant que vous pouvez facilement expliquer le format que vous avez utilisé)


3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Sortie: -1 (perte)


Encore une fois, tout format d'entrée que vous voulez est autorisé, mais les X et les O doivent être utilisés, les exemples fournis n'étaient pas destinés à contraindre à ce format, juste pour inspirer.

Urne de poulpe magique
la source
Désolé DJMCMayhem, j'ai essayé de marquer ces choses, mais je n'ai pas pu, car je suis nouveau ici.
Magic Octopus Urn
Le bonus a également été supprimé, n'ajoutant que de l'ennui.
Magic Octopus Urn
Le format de sortie suivant est-il autorisé: un diagramme de la position du plateau avec sur chaque espace initialement vide un caractère unique indiquant si y jouer mène à une victoire / perte / match nul (par exemple W, L et D)
Ton Hospel
1
Dans l'exemple 3x3, O devrait perdre, peu importe ce qu'il joue, mais vous dites que la sortie devrait être [2,1], pourquoi?
Dada
Édité, bonne prise. Je ne sais pas ce que je pensais, c'était l'exemple négatif.
Urne de poulpe magique du

Réponses:

8

Perl, 101 98 octets

Comprend +4pour-0p

Exécuter avec l'entrée sur STDIN

tictactoe.pl
OXO
---
--X
^D

La sortie est le même diagramme, mais à chaque mouvement mis à jour avec son statut, 1représente une victoire, 2représente un match nul et 3représente une perte. Pour ce cas, ce serait

OXO
223
21X

donc 3 coups tirent, 1 gagne et 1 perd (je mettrai à jour la solution si ce format de sortie est inacceptable, mais le code de base restera le même)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

C'est déjà douloureusement lent et utilise beaucoup de mémoire pour la carte 3 * 3 vide (pourquoi en fait, la récursivité ne va pas aussi loin. Doit être une fuite de mémoire). L'ajout de la mémorisation coûte 6 octets mais est beaucoup plus sain:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
Ton Hospel
la source
Wow, en oubliant que c'est pl et probablement ne fonctionnerait absolument pas pour n = 10 avec beaucoup de vides ... Vous avez fait les deux choses que j'espérais voir quelqu'un faire. Une entrée de chaîne et un mappage du résultat pour tous les mouvements, pas seulement le meilleur. Bravo.
Magic Octopus Urn
Si une fonction récursive «fuite», comment ça va? Un langage trop élevé ne fait pas voir le registre 32 bits dans le CPU (ou quelque chose comme ça l'instruction simple)
RosLuP
@RosLup Leak dans ce contexte ne signifie pas nécessairement une mémoire perdue inaccessible. Perl est plutôt particulier lorsqu'il libère de la mémoire, le faisant souvent plus tard que prévu et donc utilisant beaucoup plus de mémoire que prévu. Il a également tendance à allouer plus que ce qui est directement nécessaire dans l'espoir de développer vos infrastructures de données. Dans ce cas, l'utilisation d'une récursion "normale" avec une fonction au lieu de l'abus do$0utiliserait 10 fois moins de mémoire. Attention, ce cas est si extrême qu'il pourrait en fait s'agir d'une véritable fuite de mémoire.
Ton Hospel
Non seulement on ne voit pas les registres ou les instructions de base (à partir des instructions hlls) mais on perd le contrôle de l'utilisation de la mémoire ... Pour moi ils ne redimensionnent pas ...
RosLuP
Ça fait assez longtemps, vous gagnez mon homme, triste cependant, nous n'avons pas eu plus de tentatives.
Magic Octopus Urn
2

Javascript (ES6), 320 294 octets

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

Contribution

1) Un tableau de tableau de caractères décrivant la carte actuelle, comme:

[['X', '-'], ['-', 'O']]

2) Un entier décrivant le tour en cours: 1 = X , -1 =O

Production

Un tableau composé de:

  • un tableau décrivant le meilleur mouvement [x, y] format
  • le résultat du jeu sous forme d'entier: 1 = victoire, -1 = perte, 0 = égalité

Exemple

Dans l'exemple suivant, il Xest garanti de gagner en jouant [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

UN JEU ÉTRANGE. LE SEUL MOUVEMENT GAGNANT N'EST PAS JOUÉ.
QU'EN EST-IL D'UN BON JEU D'ECHECS?

Arnauld
la source
Bravo, bonne première entrée. Seules les remarques que j'ai sont le potentiel d'économiser des octets avec les informations données «X se déplacera toujours en premier». Et avez-vous essayé avec une carte non 3x3;)?
Urne de poulpe magique
@carusocomputing - Pas sûr de comprendre ce que vous avez en tête avec 'X bougera toujours en premier'. Il pourrait être utilisé pour déduire quel côté est en mouvement étant donné la carte seule, mais le calcul coûterait en fait plus d'octets; donc je suppose que vous parlez d'autre chose. Et oui, j'ai fait quelques tests avec des planches légèrement plus grandes. Cela devrait fonctionner comme prévu tant que ... euh ... il n'y a pas trop de positions vides. :-)
Arnauld
Le défi dit The current state of the board must be the only input to your program. Votre code a besoin de deux entrées, ce qui enfreint cette règle.
Dada
1
@Dada - Je me demandais à ce sujet, mais je supposais la couleur active est une partie de l'état de la carte (comme une position d'échecs est toujours avec couleur active + en passant carré + roque disponibilité). Je suppose donc que le PO devrait clarifier ce point. (Et si vous avez raison, cela ressemble à une difficulté supplémentaire inutile, à mon humble avis.)
Arnauld
1
Mmm .. j'aime vraiment l'explication de l'état de la carte dans sa réponse. En y réfléchissant, certaines langues peuvent n'utiliser que des chaînes en entrée, il serait difficile de déchiffrer une carte comme XXOOXO-OO avec un nombre d'octets bas sans informations supplémentaires telles que les dimensions de la carte. Je n'autoriserai aucune entrée supplémentaire qui contribue à l'état de la carte, bien que je pense toujours que les informations «supposons que X bouge en premier» sont différentes de «étant donné qui tourne» Certaines langues en profiteront comme hypothèse;).
Urne de poulpe magique