elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  ¿Cual es el método más eficiente para ver si hay una línea de S signos?
0 Usuarios y 2 Visitantes están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: ¿Cual es el método más eficiente para ver si hay una línea de S signos?  (Leído 1,435 veces)
Tachikomaia


Desconectado Desconectado

Mensajes: 1.507


Hackentifiko!


Ver Perfil
¿Cual es el método más eficiente para ver si hay una línea de S signos?
« en: 7 Enero 2025, 18:05 pm »

Conocen el juego 3 en línea, tic tac toe, tateti, etc.

Yo estoy haciendo un S en línea, es decir, que el juego permita elegir cuántos signos debe haber en la línea (y qué tan grande es el tablero).

Anduve pensando cual es el método más eficiente de ver si alguien ganó.

Se me ocurrieron 2 métodos.

El 1ero es bastante bruto, más o menos así:
Código:
Se apunta al superior izquierdo.
Repetir:
Si no está vacío:
   Se miran sus contiguos de diagonal derecha-arriba:
   Si no hay o no marcan victoria:
      Se miran sus contiguos de la derecha:
      Si no hay o no marcan victoria:
         Se miran sus contiguos de diagonal derecha-abajo:
         Si no hay o no marcan victoria:
            Se miran sus contiguos de abajo:
            Si no hay o no marcan victoria:
                  Si hay un casillero hacia abajo:
                     Se empieza a mirar ese.
                  sino si hay casilleros en la derecha:
                     Se empieza a mirar el superior de esa columna.
No es necesario que los ifs se repitan, sólo que al escribirlo así nomás quedaba más claro.

El otro método intentaba usar menos repeticiones o variaciones de variables, pero a medida que lo analicé llegó un punto en que me parecía igual. En la misma repetición, se apunta a 2 casilleros (al principio son el mismo), y en cada repetición se varía a cual se apunta (y analiza como puse arriba), el 1ero es cada vez más hacia la derecha y el 2ndo hacia abajo. Cuando no quedan, se apunta al diagonal derecho-abajo y se repite el proceso hasta que el apuntado sea el inferior derecho.

Empecé a aplicar el método 1:
Código
  1. // Por practicidad al calcular, las filas se cuentan desde 0:
  2. Fila = -1;
  3. // Las columnas no, desde 1:
  4. Columna = 0;
  5. do {
  6. Fila++;
  7. SemiReferenciaAlCas = "Casillero"+Fila+"_";
  8. do {
  9. Columna++;
  10. // Si el casillero no está vacío:
  11. if (eval(SemiReferenciaAlCas+Columna != 2)) {
  12. // Esto va variando qué siguientes...
  13. // casilleros se analizan:
  14. Extra = 0;
  15. do {
  16. Extra++;
  17. //

Ahí iría lo de analizar hacia la diagonal arriba-derecha, y el resto de las cosas. Pero siento que es tan poco eficiente que prefiero que me digan algo mejor, que probablemente haya. Sino, más adelante le pregunto a GPT.

Por cierto, tengo pensado que la máquina aprenda a jugar experimentando, por eso los valores de los casilleros están grabados de 2 formas, por ejemplo el superior izquierdo:
// 2 es vacío, 1 es cruz, 0 es 0.
Casillero1 = 2;
Casillero1_1 = 2;
Porque al hacer referencia a una situación es más fácil variar sólo una variable (no fila y columna).
Lo necesito para hacer árboles, no sé cómo lo hacen uds, hablaremos en otra ocasión de eso.

Mientras hacía el tema me di cuenta que alcanza con analizar solamente las líneas que impliquen al casillero recién modificado  :xD así que intentaré eso y podría borrar todo esto, pero igual puede ser interesante, luego pongo lo que logre.


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.392


Ver Perfil
Re: ¿Cual es el método más eficiente para ver si hay una línea de S signos?
« Respuesta #1 en: 30 Enero 2025, 18:05 pm »

El modo más sencillo no es investigar todo el 'tablero', si no a partir el último movimiento de un jugador, antes de pasarle el turno a otro jugador revisar si ese último movimiento, tiene 2 contiguas más en alguna de las 4 direcciones (vertical, horizontal, diagonal izquierda y diagonal derecha).
Para no incurrir en complicaciones de errores por estar fuera del tablero, es adecuado dimensionar el tablero a una casilla más perimetralmente... (solo en código, obviamente). Partamos pues de un esquema mental inicial con sus oportunas explicaciones...

Tablero 0:
 | 3 | 3 | 3 | 3 | 3 |
 | 3 | 0 | 0 | 0 | 3 |
 | 3 | 0 | 0 | 0 | 3 |
 | 3 | 0 | 0 | 0 | 3 |
 | 3 | 3 | 3 | 3 | 3 |


El tablero que se dibuja es el central (de 3x3), donde figuran las casillas vacías (valor 0). Perimetralmente se observa un valor 3 en todas las casilla.
El jugador 1 marca las casillas suyas con un 1, el jugador 2 con un 2.
Nota que son valores elegidos arbitrariamente, se puede elegir el conjunto que se desee siempre que se sea consecuente.

Veamos ahora una partida empezada, olvidemos los pasos previos, en ellos se hará lo mismo que ahora se comenta, pero como solo habria inicialmente 1 casilla, marcada y luego 2, no ofrece el interés (explicativo y aclaratorio) que cuando ya el tablero está más avanzado...

Tablero 1:
 | 3 | 3 | 3 | 3 | 3 |
 | 3 | 1 | 2 | 1 | 3 |
 | 3 | 0 | 1 | 0 | 3 |
 | 3 | - | 0 | 2 | 3 |
 | 3 | 3 | 3 | 3 | 3 |

Empezaba el jugador 1, luego el 2... ahora es el turno del 2, y va a poner su ficha en la casilla marcada con '-' (solo para verla fácilmente), procede pues analizar el si jugador 2 ha conseguido las 3 en raya, sabiendo que su último movimiento es la casilla 3-A, o también 3-1 (Tercerá fila columna 1).

Una función recibe: qué jugador tiene el turno y qué casilla marcó, queda pues mirar si a su alrededor las casillas contiguas son también son suyas hasta sumar 3:

Código:
buleano = funcion Validar(jugador, fila, columna)
    puntos tipo byte

    puntos =1
    Si (Buscar(jugador, fila-1, columna, -1, 0) = FALSE) luego        // 1 buscar hacia arriba:        // Buscar en vertical
        Si (Buscar(jugador, fila+1, columna, 1, 0) = FALSE) luego         // 2 buscar hacia abajo:    // Buscar en vertical
            puntos =1  //reset puntos a 1.
            Si (Buscar(jugador, fila, columna-1, 0, -1) = FALSE) luego         // 3 buscar hacia izquierda:     // Buscar en horizontal
                Si (Buscar(jugador, fila, columna+1, 0, 1) = FALSE) luego         // 4 buscar hacia derecha:    // Buscar en horizontal

                    // Ahora las diagonales...
                    puntos =1  //reset puntos a 1.
                    Si (Buscar(jugador, fila-1, columna-1, -1, -1) = FALSE) luego         // 5 buscar hacia diagonal izquierda y arriba:     // Buscar en diagonal '\'
                        Si (Buscar(jugador, fila+1, columna+1, 1, 1) = FALSE) luego         // 6 buscar hacia diagonal derecha y abajo:    // Buscar en diagonal '\'
                            puntos =1  //reset puntos a 1.
                            Si (Buscar(jugador, fila-1, columna+1, -1, 1) = FALSE) luego         // 7 buscar hacia diagonal derecha y arriba:      // Buscar en diagonal '/'
                                Si (Buscar(jugador, fila+1, columna-1, 1, -1) = FALSE) luego         // 8 buscar hacia diagonal izquierda y abajo:    // Buscar en diagonal '/'
                                    devolver FALSE
                                fin si
                            fin si
                        fin si
                    fin si
                fin si
            fin si
        fin si
    fin si
    
    devolver TRUE
fin funcion

Todas las verificaciones se derivan a esta única función para no repetir código,  donde solo cambia el avance de fila o columna para revisar...
El parámetro puntos se recibe por referencia, es decir conserva su valor tras salir de la función.
El tablero tiene perimetralmente una casilla adicional luego es del tamaño 0 a 4 de ancho y lo mismo de alto, siendo útiles a los jugadores solo las casillas 1,2,3.
 en ese perímetro hay un valor que no corresponde al tablero (valor 0), ni a los jugadores (1 ni 2).
Un jugador solo podría ocupar así una casilla del tablero con valor 0... etc... las normas son bien conocidas (en jerga se dice 'well known') por todos los interesados.  
Código:
buleano funcion Buscar(puntos, jugador, Fila, Columna, dF, dC)
    mientras tablero(Fila, Columna) = jugador
        puntos +=1
        Si (puntos = 3) devolver TRUE

        Fila += dF        // df puede ser -1, 0, 1
        Columna += dC   // dC puede ser -1, 0, 1
    repetir

    devolver FALSE
fin funcion

Si se examina el código con el estado actual en el 'tablero 2', se verá que devuelve  false, el jugador 2, no tiene 3 en raya.
Ahora supongamos que el jugador 2, (ver tablero 3) en vez de marcar la casilla 3,A hubiera marcado la casilla 3,B con intención luego de marcar la 3,A para hacer 3 en raya en la fila C.
Entonces el jugador 1, sí marca la casilla 3,A que si se comprueba con la función, devolverá TRUE tras la búsqeuda 7 (se han enumerado en los comentarios las 8 búsquedas), que es la diagonal '/' y que empieza a buscar desde la casilla marcada 3A  (3,1)

Tablero 3:
 | 3 | 3 | 3 | 3 | 3 |
 | 3 | 1 | 2 | 1 | 3 |
 | 3 | 0 | 1 | 0 | 3 |
 | 3 | - | 2 | 2 | 3 |
 | 3 | 3 | 3 | 3 | 3 |

La lógica es bastante simple, pero como se ve, no se precisa recorrer todas las líneas, ni todas las columnas, ni todas las diagonales, sino solo alrededor de la casilla recién marcada por el jugador.


« Última modificación: 30 Enero 2025, 19:09 pm por Serapis » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[ayuda]cual es metodo para imprimir
Programación C/C++
adamsst 0 2,082 Último mensaje 3 Agosto 2012, 17:48 pm
por adamsst
Cual es el mojor metodo para aprender programacion C++ en linea
Programación C/C++
Mister12 0 2,201 Último mensaje 1 Junio 2013, 03:39 am
por Mister12
¿Cual es el metodo para ser Poliglota?
Foro Libre
bacanzito 2 3,089 Último mensaje 19 Octubre 2013, 23:21 pm
por Stakewinner00
Metodo eficiente para poder factorizar un numero
Java
Tronos154 0 6,801 Último mensaje 16 Febrero 2016, 21:32 pm
por Tronos154
¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor?
Programación General
pran_krr 1 2,727 Último mensaje 27 Noviembre 2019, 16:45 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines