algoritmo de calculo de manos

[Warchief]

Si te tocan mas de dos, te los comes con patatas entonces?

http://es.wikipedia.org/wiki/Chinch%C3%B3n_%28juego_de_naipes%29
Las combinaciones de cartas que pueden formarse son:
    Escalera: tres o más cartas del mismo palo consecutivas, con un solo comodín.
    Pie o trío: tres o cuatro cartas del mismo número, con un solo comodín.
    Chinchón: siete cartas consecutivas, del mismo palo.

[blau]

Siempre te puedes descartar una carta en tu turno... :)

[Warchief]

Me refiero a qué pasa cuando te quedas con 3 comodines en tu mano y cierran.
Creo que ya tengo la versión sin comodines funcionando; añadir comodines me parece que será sencillo con los casos interesantes.

[Warchief]

Me voy a dormir que ya ni veo si los resultados son buenos. Mañana comodines y limpiar código.
Uhm, debido a una optimización, falla si hay repetidos en escalera. Mañana quito la optimización.

[Warchief]

Perfecto, he modificado la representacion de datos para no tener que quitar la optimizacion y voila.
Para meter multiples comodines se me ocurren varias formas en la implementacion que tengo, pero creo que volver a la idea de Vicente de las permutaciones es mas sencillo. No creo que siga ya implementando porque consume bastante tiempo, pero ha sido divertido.

Código [Seleccionar] Expand


*******************************************************
MANO     {102, 103, 104, 105, 205, 305, 402}
Ordenada {102, 103, 104, 105, 205, 305, 402}
Mejor Jugada:
  | - Escalera = {102, 103, 104}
  | - Match x3 = {105, 205, 305}
  | - Libres   = {402}
  | + Score = 2

*******************************************************
MANO     {102, 202, 302, 105, 205, 305, 405}
Ordenada {102, 105, 202, 205, 302, 305, 405}
Mejor Jugada:
  | - Match x3 = {102, 202, 302}
  | - Match x4 = {105, 205, 305, 405}
  | + Score = 0

*******************************************************
MANO     {102, 103, 104, 105, 103, 102, 202}
Ordenada {102, 102, 103, 103, 104, 105, 202}
Mejor Jugada:
  | - Escalera = {103, 104, 105}
  | - Match x3 = {102, 202, 102}
  | - Libres   = {103}
  | + Score = 3

*******************************************************
MANO     {306, 402, 305, 403, 307, 404, 401}
Ordenada {305, 306, 307, 401, 402, 403, 404}
Mejor Jugada:
  | - Escalera = {305, 306, 307}
  | - Escalera = {401, 402, 403, 404}
  | + Score = 0


[Warchief]

Por cierto, el algoritmo ha quedado bastante sencillo, aunque se puede reordenar un poco para simplificar BuscarEscalera (hace el mismo check en dos path distintos).

Código [Seleccionar] Expand


  // Find
  //   Ordenar
  //   BuscarEscalera( 0 )

  // BuscarEscalera( IDX )
  //   FOR n = 3 a CartasRestantes( IDX )
  //     SI HayEscalera( IDX, n )    -- hay escalera en el indice IDX con longitud n
  //       UsarCartas( IDX, n )      -- marcar las cartas como usadas en la escalera que empieza en IDX y con longitud n
  //       SI QuedanCartas           -- quedan cartas tras UsarCartas
  //         BuscarEscalera()        -- buscar escaleras en las cartas restantes
  //       SI NO
  //         BuscarPies()            -- buscar entre las cartas que nos dejamos atras sin meter en escaleras
  //   SI HayCartasPorMirar          -- quedan cartas que no hemos explorado (donde empezar escaleras)
  //     BuscarEscalera( IDX + 1 )   -- avanzar a la siguiente
  //   SI NO
  //     BuscarPies()                -- no hay mas escaleras, buscar pies entre las cartas que hemos dejado atras

  // BuscarPies( IDX )
  //   SI HayRepeticion( IDX )       -- se puede hacer un pie con la carta en IDX
  //     UsarCartas( IDX )           -- marcar como usadas las cartas con el mismo valor
  //     BuscarPies()                -- buscar mas pies entre las restantes
  //   SI NO
  //     SI HayCartasPorMirar        -- quedan cartas que no hemos explorado (valores que aun puede formar pies)
  //       BuscarPies( IDX + 1 )     -- avanzar a la siguiente
  //     SI NO
  //       CalcularPuntuacion        -- devolver el valor las cartas que han quedado libres


[Warchief]

Hace unos días un estudiante me pidió el código de mi algoritmo, así que lo pondre aquí. No creo que en 2013 puedas engañar a un profesor con código bajado de Internet, así que puede servir como referencia pero no creo que para presentar.

Obviamente el código no está comentado, ni refactorizado, pero ahí va.
http://pastebin.com/gbDcatwn

Lo que puedes obtener: dada una mano definida por cartas XYY, siendo X el palo (eg: 1 = Espadas, 2 = Oros..), y siendo YY el valor de la carta (eg: 01 = As, 02 = 2, ... 12 = Rey)

Código [Seleccionar] Expand


        Mano m;
        m.AddCard( 102 );
        m.AddCard( 103 );
        m.AddCard( 104 );
        m.AddCard( 105 );
        m.AddCard( 205 );
        m.AddCard( 305 );
        m.AddCard( 402 );


Encuentra la mejor jugada (para cerrar o para contar puntos):

Código [Seleccionar] Expand


*******************************************************
MANO     {102, 103, 104, 105, 205, 305, 402}
Ordenada {102, 103, 104, 105, 205, 305, 402}
Mejor Jugada:
  | - Escalera = {102, 103, 104}
  | - Match x3 = {105, 205, 305}
  | - Libres   = {402}
  | + Score = 2


Al final no añadí comodines porque me cansé, pero no sería muy difícil hacer una version no optimizada seleccionando valores para los comodines que puedan cambiar la puntuación (adyacentes a otras cartas o de mismo valor que las presentes) :)

Por si PasteBin no funciona:

Código [Seleccionar] Expand


// Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <cmath>
#include <vector>
#include <list>
#include <cassert>
#include <cstdarg>
#include <algorithm>

#define VERBOSE 0

typedef int INT;
typedef unsigned int  UINT;
typedef unsigned long ULONG;

//  todo quitar push invertido (no es necesario)

struct _Log
{
    void Print( const char* format, ... )
    {
#if VERBOSE
        for( INT i=0; i<NUMTABS; ++i ) { printf("  "); }
#endif
        va_list args;
        va_start( args, format );
        vprintf( format, args );
        va_end( args );
    }
    void Push()
    {
        ++NUMTABS;
    }
    void Pop() {
        --NUMTABS;
        assert( NUMTABS >= 0 );
    }
private:
    INT NUMTABS;
} Log;

struct ScoreTrack
{
    ScoreTrack() { Reset(); }

    enum
    {
        TOKEN_START = 0
        , ESCALERA
        , MATCH3 = 3
        , MATCH4
        , MATCH5
        , MATCH6
        , MATCH7
        , FREE
        , TOKEN_END
    };

    void PushEscalera()
    {
        Combinacion.push_back( ESCALERA );
    }
    void PushMatch( UINT Reps )
    {
        assert( Reps >= MATCH3 && Reps <= MATCH7 );
        Combinacion.push_back( Reps );
    }
    void PushFree()
    {
        Combinacion.push_back( FREE );
    }
    void PushVal( UINT v )
    {
while ( v > 500 ) { v -= 400; }
        Combinacion.push_back( v );   
    }
    bool IsBackToken() const
    {
        UINT Val = Combinacion.back();
        return ( Val > TOKEN_START && Val < TOKEN_END );
    }
    void Pop()
    {
        assert( Combinacion.size() > 0 && !IsBackToken() );
        do
        {
            Combinacion.pop_back();
        } while( !IsBackToken() );
        Combinacion.pop_back();
    }
    ULONG GetScore() const
    {
        return Score;
    }
    bool IsEmpty()
    {
        return Combinacion.empty();
    }
    void Reset()
    {
        Score = 666;
        Combinacion.clear();
    }
    void Print()
    {
        Log.Print( " Mejor Jugada:\n" );
        for( UINT i=0; i<Combinacion.size(); ++i )
        {
            if ( Combinacion[i] == ESCALERA )
            {
                printf( "  | - Escalera = {" );
            }
            else if ( Combinacion[i] >= MATCH3 && Combinacion[i] <= MATCH7 )
            {
                printf( "  | - Match x%d = {", Combinacion[i] );

                // Porque hago push invertido
                for ( UINT j = i + Combinacion[i]; j > i ; --j )
                {                   
                    if ( j == i+1 )
                    {
                        printf( "%d}\n", Combinacion[j] );
                    }
                    else
                    {
                        printf( "%d, ", Combinacion[j] );
                    }                   
                }
                i = i + Combinacion[i];
            }
            else if ( Combinacion[i] == FREE )
            {
                printf( "  | - Libres   = {" );
            }
            else
            {
                UINT Next = i+1;
                if ( Next >= Combinacion.size() || ( Combinacion[Next] < TOKEN_END ) )
                {
                    printf( "%d}\n", Combinacion[i] );
                }
                else
                {
                    printf( "%d, ", Combinacion[i] );
                }
            }
        }
        printf( "  | + Score = %lu\n", Score );       
        //Log.Print( "- - - - - - - - - \n\n" );

    }

    ULONG Score;
private:
    std::vector<UINT> Combinacion;
};
ScoreTrack CurrentScore;
ScoreTrack BestScore;

class Mano
{
private:
    typedef std::vector<UINT> Container;   
    Container Cards;
    Container UsedCards;

public:
    void AddCard( UINT c )
    {
        Cards.push_back( c );
        assert( Cards.size() <= 7 );
    }   
    void Use( UINT first, UINT count )
    {
        assert( count <= ( Cards.size() - first ) );       
        for( UINT i = first ; i < (first+count); ++i )
        {
            UsedCards.push_back( Cards[i] );
            CurrentScore.PushVal( Cards[i] );
        }
        Cards.erase( Cards.begin() + first, Cards.begin() + first + count );
    }
    void Restore( UINT count )
    {
        assert( count <= UsedCards.size() );
        for( UINT i = 0; i < count; ++i )
        {
            AddCard( UsedCards[UsedCards.size() - i - 1] );
        }
        CurrentScore.Pop();
        UsedCards.erase( UsedCards.end() - count, UsedCards.end() );
        std::sort( Cards.begin(), Cards.end() ); // podria optimizarse
    }
    void RemoveCardByVal( UINT c )
    {
        Container::iterator match = std::find( Cards.begin(), Cards.end(), c );
        assert( match != Cards.end() );
        Cards.erase( match );
    }
    void RemoveCardByIndex( UINT i )
    {
        assert( i < Cards.size() );
        Cards.erase( Cards.begin() + i );
    }

    bool HayEscalera( UINT index, UINT n ) const
    {
        assert( n > 2 && n <= Cards.size() );
        return ( Cards[index+n-1] - Cards[index] == (n-1) );
    }

    UINT CardsLeft( UINT curIdx ) const
    {
        assert( curIdx <= Cards.size() );
        return Cards.size() - curIdx;
    }
    bool HayNext( UINT curIdx ) const
    {
        return (curIdx+1) < Cards.size();
    }
    UINT Valor( UINT curIdx ) const
    {
        assert( curIdx < Cards.size() );
        return UINT( Cards[curIdx] % 100 );
    }

    void Print() const
    {
        PrintFrom( 0, Cards.size() );
    }
    void PrintFrom( UINT first, UINT count ) const
    {
        assert( first >= 0 && count <= ( Cards.size() - first ) );
        printf("{");
        for( UINT i = first ; i < (first+count); ++i )
        {
            if ( i != first )
            {
                printf(", ");
            }
            printf( "%u", Cards[i] );
        }
        printf("}\n");
    }

void CleanDups()
{
for ( UINT i=0; i < Cards.size(); ++i )
{
for ( UINT j=i+1; j < Cards.size(); ++j )
{
if ( Cards[i] == Cards[j] )
{
Cards[j] += 400;
}
}
}
}

void RestoreDups()
{
for ( UINT i=0; i < Cards.size(); ++i )
{
while ( Cards[i] > 500 )
{
Cards[i] -= 400;
}
}
}

    void FindBestScore();

private:
    void Buscar( UINT curIdx );
    void Match( UINT curIdx );
    ULONG CloseVal() const;

};


ULONG Mano::CloseVal() const
{
    ULONG Val = 0;
    for ( UINT i = 0; i < Cards.size(); ++i )
    {
        Val += Valor( i );
    }
    return Val;
}

void Mano::Match( UINT curIdx )
{
#if VERBOSE
    Log.Print("Match: ");
    PrintFrom( curIdx, CardsLeft( curIdx ) );
#endif

    if ( CardsLeft( curIdx ) >= 3 )
    {
        UINT CardsLeftTotal = CardsLeft( curIdx );
        UINT Val = Valor( curIdx );
        UINT Reps = 1;
        for ( UINT i = curIdx + 1; i < curIdx + CardsLeftTotal; ++i )
        {
            if ( Valor( i ) == Val )
            {
                ++Reps;
            }
        }

        if ( Reps >= 3 )
        {

#if VERBOSE
            Log.Print( "Match x%d = {", Reps );
            UINT NumRep = 1;
            for ( UINT i = curIdx; i < curIdx + CardsLeftTotal; ++i )
            {
                if ( Valor( i ) == Val )
                {
                    if ( NumRep == Reps )
                    {
                        printf( "%d}\n", Cards[i] );
                        break;
                    }
                    else
                    {
                        printf( "%d, ", Cards[i] );
                    }
                    ++NumRep;
                }
            }
#endif

            CurrentScore.PushMatch( Reps );

            Log.Push();
            for ( INT i = curIdx+CardsLeftTotal-1; i >= (INT)curIdx; --i )
            {
                if ( Valor( (UINT)i ) == Val )
                {
                    Use( i, 1 );
                }
            }

            Match( curIdx );

            Log.Pop();
            Restore( Reps );
        }
        else if ( HayNext( curIdx ) )
        {
            Match ( curIdx + 1 );
        }
    }
    else
    {
        CurrentScore.Score = CloseVal();
        if ( CurrentScore.Score < BestScore.Score )
        {
            BestScore = CurrentScore;

            // Add libres
            if ( UINT FreeCount = CardsLeft(0) )
            {
                BestScore.PushFree();
                for( UINT i=0; i<FreeCount; ++i )
                {
                    BestScore.PushVal( Cards[i] );
                }
            }
        }

#if VERBOSE
        Log.Print( "Libres   = " );
        Print();
        Log.Print( " + New Score = %lu\n",  CloseVal() );
        Log.Print( "- - - - - - - - - \n\n" );
#endif

    }

}

void Mano::Buscar( UINT curIdx )
{
    assert( curIdx < Cards.size() );

#if VERBOSE
    Log.Print("Buscar: ");
    PrintFrom( curIdx, CardsLeft( curIdx ) );
#endif

    // Buscar escaleras de todos los tamanyos
    for ( UINT n = CardsLeft( curIdx ); n >= 3; --n )
    {
        if ( HayEscalera( curIdx, n ) )
        {
#if VERBOSE
            Log.Print( "Escalera = " );
            PrintFrom( curIdx, n );
#endif
            CurrentScore.PushEscalera();

            // Considerar dicha escalera
            Log.Push();
            Use( curIdx, n );
   
            if ( CardsLeft( curIdx ) > 0 )
            {
                Buscar( curIdx );
            }
            else
            {
                Match( 0 );
            }
                       
            Restore( n );
            Log.Pop();
        }
    }

    // Si quedan cartas que no se han probado
    if ( HayNext( curIdx ) )
    {
        Buscar( curIdx+1 );
    }
    else
    {
        // Si no, es hora de matchear repes
        Match( 0 );
    }
}

void Mano::FindBestScore()
{
    std::sort( Cards.begin(), Cards.end() );
    printf( " Ordenada " );
    Print();

CleanDups();
std::sort( Cards.begin(), Cards.end() );
//printf( " Hacked   " );
//Print();

    CurrentScore.Reset();
    BestScore.Reset();
    Buscar( 0 );
    BestScore.Print();   

RestoreDups();
std::sort( Cards.begin(), Cards.end() );
//printf( " Ordenada " );
//Print();
}


int main(int argc, char* argv[])
{
    {
        Mano m;
        m.AddCard( 102 );
        m.AddCard( 103 );
        m.AddCard( 104 );
        m.AddCard( 105 );
        m.AddCard( 205 );
        m.AddCard( 305 );
        m.AddCard( 402 );
        printf( "*******************************************************\n" );
        printf( " MANO     " );
        m.Print();
        //printf( "*******************************************************\n" );
        m.FindBestScore();
        printf("\n");
    }

    if ( 1 )
    {
        Mano m;
        m.AddCard( 102 );
        m.AddCard( 202 );
        m.AddCard( 302 );
        m.AddCard( 105 );
        m.AddCard( 205 );
        m.AddCard( 305 );
        m.AddCard( 405 );
        printf( "*******************************************************\n" );
        printf( " MANO     " );       
        m.Print();
        //printf( "*******************************************************\n" );
        m.FindBestScore();
        printf("\n");
    }

    if ( 1 )
    {
        Mano m;
        m.AddCard( 102 );
        m.AddCard( 103 );
        m.AddCard( 104 );
        m.AddCard( 105 );
m.AddCard( 103 );
m.AddCard( 102 );
        m.AddCard( 202 );
        printf( "*******************************************************\n" );
        printf( " MANO     " );               
        m.Print();
        //printf( "*******************************************************\n" );
        m.FindBestScore();
        printf("\n");
    }

    if ( 1 )
    {
        Mano m;
        m.AddCard( 306 );
        m.AddCard( 402 );
        m.AddCard( 305 );
        m.AddCard( 403 );
        m.AddCard( 307 );
        m.AddCard( 404 );
        m.AddCard( 401 );
        printf( "*******************************************************\n" );
        printf( " MANO     " );               
        m.Print();
        //printf( "*******************************************************\n" );
        m.FindBestScore();
        printf("\n");
    }

    return 0;
}


[angel]

Hola, despues de mirar el codigo de Warchief, me puse manos a la obra a crear mi propio alogatirmo. Lo estoy haciendo en c# porque de paso me sirve para practicar para mi carrrea.

Hasta el momento, solo chequea escaleras:

- chequea cantidad de juegos en escalera.
- conserva juegos por separado.
- devuelve cantidad de cartas en escalera por juego (util para saber si hay chinchon)
- conserva internamente cartas consecutivas que no formen juego (por ejemplo 2 cartas en escalera util para IA de la pc)
- devuelve las cartas que no forman juegos (puntuacion).

Todavia tengo que depurarlo mas y aceitarlo, pero va tomando forma. El tema de los comodines ni idea, porque ahi ando medio perdido. si alguien me tira alguna idea se lo agradeceria.

en cuanto lo termine cuelgo el pseudocodigo asi cualquier puede aportar ideas.

Saludos!

[Warchief]

El tema de los comodines ni idea, porque ahi ando medio perdido. si alguien me tira alguna idea se lo agradeceria.

Simplemente sustituye el comodín, bien por una carta adyacente a otra o bien del mismo número. Luego relanza la búsqueda de jugada con la nueva combinación.

Por ejemplo:

Código [Seleccionar] Expand


(Notación XYY, X = palo, YY = número de carta)

101 102 204 207 306 309 COM

+ Se convierte en:
101 106 204 207 306 309 101 // si hay más de una baraja
101 106 204 207 306 309 201
101 106 204 207 306 309 301
101 106 204 207 306 309 401

101 106 204 207 306 309 106 // si hay más de una baraja
101 106 204 207 306 309 206
101 106 204 207 306 309 306
101 106 204 207 306 309 406

etc. para tríos. Y...

101 106 204 207 306 309 102
101 106 204 207 306 309 105
101 106 204 207 306 309 107
101 106 204 207 306 309 203
etc. para escaleras



Si tienes múltiples comodines, lo mismo pero con combinaciones.

[angel]

Hola Warchief, creo que lo voy asimilando jejeje....

1. Cuento cantidad de comodines en la mano.
2. copio la cantidad de comodines a una variable temporal.
3. busco escalera preguntando por carta siguiente o por comodin.
4. si efectivamente no hay carta siguiente, pero si comodin. le resto 1 a la variable temporal del comodin.

Con esto no relanzaria la busqueda, ya que simplemente el comodin entra al grupo de cartas en juego al menos hasta ese momento.

Tendria que ver como implementarlo y probarlo. El tema es preguntar si hay comodin en el mismo if de comparacion.

A ver si te parece que puede ser asi, igual voy a probarlo en cuanto pueda....


Gracias nuevamente por toda tu ayuda Warchief!

Saludos!.-

Edit:
Al parece funciona agregando los comodines de la manera que digo. Pero encontre un error en la busqueda de escaleras... cuando hay 2 juegos correlativos seguidos por una carta faltante por ejemplo: 1,2,3,4   -no hay 5-   6, 7, 8. el segundo juego no lo encuentra. no pasa si fuese asi:   1,2,3,4    -no hay 5 ni 6 -    7,8,9  asi que tengo que revisar eso.

Edit 2:
Ya funciona todo correcto las esclares + comodin (era un problema en el for). No era n tan simple, faltaban varios detalles con respecto al comodin. Quedara en 2 o 3 rutinas en total los chequeos. Si alguien le interesa seguire repontando como va todo.

Saludos!.-