Déterminer le gagnant de Connect 4

19

Vous obtenez une grille Connect 4 partiellement remplie (7x6).

O X             
O X          
X O X O     O
X O X O   X X
O X X X O O X
O O O X X O X

(L'entrée peut être donnée sous forme de tableau 1D ou 2D et sous forme de lettres ou de chiffres, etc.)

Suppose que

  • X a commencé le jeu.
  • Personne n'a encore gagné.
  • Les joueurs n'ont peut-être pas bien joué jusqu'à présent, mais à partir de maintenant, ils utiliseront tous deux des stratégies optimales.
  • La grille d'entrée n'est pas défectueuse.

Vous devez sortir une seule valeur qui indique quel joueur gagne (ou un match nul)

Code défi de golf; donc le code le plus court gagne. Votre programme n'a pas à calculer réellement la sortie dans un laps de temps raisonnable, mais vous devriez être en mesure de prouver que la sortie sera obtenue correctement dans un laps de temps fini.

code-golf game grid board-game ghosts_in_the_code
la source
En relation.
Martin Ender
@ MartinBüttner Cela signifie-t-il que je vais être rétrogradé, ou est-ce que je peux laisser ma question ici?
ghosts_in_the_code
4
Cela signifie simplement que les questions sont liées, rien de plus, rien de moins. Le but de la publication du lien est que les défis apparaissent dans la barre latérale "Linked" de l'autre, afin que les gens puissent trouver plus facilement les défis liés. Si j'avais considéré votre question comme un doublon, je l'aurais dit (ou je l'ai simplement fermée), alors ne vous inquiétez pas. :)
Martin Ender
2
Le "jeu optimal" est-il bien défini? Si oui, pouvez-vous fournir un lien décrivant l'algorithme pour un jeu optimal?
Rainbolt
2
@Rainbolt Il a été résolu et il existe également des algorithmes parfaits . Lisez Wikipedia pour en savoir plus.
ghosts_in_the_code

Réponses:

16

Perl, 119 118 117 117 octets

Comprend +4 pour -0p

Donnez une planche pivotée rembourrée avec des espaces sur STDIN (la gravité tire les pierres vers la droite)

connect4.pl
  OXXX
   XOO
    OX
  OOXX
  XXXO
XXOOXO
OOXXOO
^D

connect4.pl:

#!/usr/bin/perl -p0
y/XO/OX/if$^S|y/X//>y/O//;$_=$$_||=/Z@{[map"|O".".{$_}O"x3,0,5..7]}/sx||s% (?! )%$_="$`X$'";do$0%eg?/1/?3:1+/2/:2

Imprime 3si le joueur à déplacer gagne, 1si le joueur à déplacer perd et 2pour un match nul.

Sur les anciennes perles, vous pouvez utiliser un littéral ^Spour gagner un octet. Si cela ne vous dérange pas extrême inefficacité vous pouvez laisser le $$_||=(tableau de transposition) et gain de 6 plus d' octets. Si vous omettez le, $_=il vous montrera où jouer au lieu du résultat (jouez 1et gagnez s'il y en a un, jouez 2et tirez s'il y en a un ou jouez sur n'importe lequel 3et perdez)

Construit et évalue un arbre minimax complet. Vous manquerez de mémoire et de temps à moins que le tableau ne soit déjà raisonnablement bien rempli.

Ton Hospel
la source
2
Pourquoi diable quelqu'un at-il voté contre? Le golf est vraiment incroyable (je joue avec Perl et obtenir une telle solution est extrêmement difficile - je ne suis pas sûr qu'un autre golfeur de Perl que je connaisse aurait pu trouver ce code). Et le code a le comportement requis.
Dada
Cela me fait mal au cerveau. +1!
levelonehuman
@Dada comment savez-vous que cette réponse est rejetée? Je vois 3 comme vote ...
RosLuP
@RosLuP quand j'ai vu ce post pour la première fois, il y avait 1 downvote. De plus, lorsque vous avez suffisamment de représentants, vous pouvez voir combien de votes de haut en bas un post a: dans ce cas, il a maintenant 4 up et 1 down.
Dada