Xogar ao escondite, xogar a Afundir a flota ou a outros xogos onde hai que desenvoler unha estratexia para atopar obxectos é un dos retos que nos gustan ás persoas. Pero, como lle explicamos a unha máquina como buscar cousas de maneira eficiente?. A continuación propoñemos unha serie de xogos que vos axudarán a afondar nestes conceptos.
Primeiro xogo: Adiviña quen ten a carta
O xogo trata de adiviñar quen ten unha carta determinada dunha baralla facendo o mínimo número de preguntas. A persoa que debe adiviñar ten 5 chuches que poderá empregar como pago polas respostas. Poderá quedarse cos chuches restantes.
-
Escollemos 15 persoas e asignámoslle unha carta cun número aleatorio a cada unha.
-
Outra persoa debe adiviñar quen ten un número determinado. A esta persoa se lle dan 5 caramelos, que debe empregar como pago por cada pregunta que faga para adiviñar quen ten o número pedido (en canto acerte pode quedar co resto dos caramelos).
-
Repítese o xogo, pero desta vez ordénanse ás persoas de menor a maior carta. Agora a persoa que debe adiviñar pode empregar unha estratexia: dar un caramelo á persoa do medio. Repetindo esta estratexia debería gastar so 3 caramelos.
-
Podemos rematar xogando ao clásico xogo de Afundir a flota, pensando en cales son as estratexias de busca que empregamos.
Segundo xogo: A serpe quere comer
Para realizar este xogo imos dividirnos en tres grupos, de maneira que cada un dos grupos tratará de alimentar á súa serpe buscando os vermes (ou cempés, dependendo do gusto das serpes).Cada grupo empregará diferentes técnicas de busca, que poremos en común cando remato o xogo.
Organizamos cada grupo en parellas aos que lles repartiremos as tarxetas A e B (coa advertencia de que non ensinen a tarxeta aos seus compañeiros).
O xogo consiste en adiviñar en que letra está posicionado o verme cun número determinado:
- Empeza o xogador A, sinalando un dos vermes e dicindo en alto o seu número. O xogador B terá que ir tenteando letras ata adiviñar onde estaba o verme indicado. Cada vez que falla a adiviña terá que apuntarse un punto.
- Tócalle a quenda ao xogador B, que repite a estratexia do primeiro xogador.
- Gañará o xogador que teña adiviñado onde están todos os vermes coa mínima puntuación .
A diferenza entre os tres grupos será o tipo de tarxetas que lles repartimos. Todas as tarxetas poderás descargalas nesta ligazón
1º Subgrupo: Tarxetas de busca lineal
A busca lineal consiste en ir tenteando onde está o verme de maneira lineal, un a un, sen ningunha pista. Como este método de busca é o máis lento, en xeral, para equilibrar os tempos con outros subgrupos poderemos limitar a busca ao número de vermes que igualen tempo cos outros subgrupos.
2º Subgrupo: Tarxetas de busca binaria
Neste caso hai que advertir aos xogadores que os números están ordenados de menor a maior, por tanto para acertar non deben facer un tenteo ao chou, senón que deberían comezar polo do medio e dividir en dous (binario) as posibilidades e así repetidamente ata atopar a letra.
(Dependendo do tempo que dispoñamos podemos deixar que xoguen unha partida libremente e que reflexionen na estratexia que seguiron).
3º Subgrupo: Tarxetas de busca por transformación de claves (hashing)
Neste caso a cuestión é saber que os vermes están ordenados en diferentes fendas, segundo unha clave. Na ligazón coas tarxetas podedes atopar dúas claves diferentes:
- As tarxetas de clave SUMA, nas que para saber en que fenda están so hai que sumar todos números do verme e quedarse coa última cifra do resultado.
- As tarxetas en clave IMPAR, nas que para saber en que fenda están os vermes so hai que sumar os números impares e quedarse coa última cifra.
Posta en común dos tres tipos de procura
Cada subgrupo expón aos outros subgrupos en que consistía o seu xogo, respondendo ás seguintes preguntas:
-
Que estratexia empregou a persoa gañadora?
-
Cales son os barcos máis rápidos de achar? (so haberá diferencia na busca por clave)
-
Cantos puntos obtivo a persoa gañadora?
-
Na segunda partida. Aprendiches algo da estratexia da túa parella ou dos teus propios erros?.
-
Describe detalladamente o proceso de busca seguido.
Unha vez expostos os tres métodos de busca, reflexionamos cal é o máis rápido e cales son as vantaxes e desvantaxes dos tres métodos (o segundo é máis rápido que o primeiro, pero precisa de ter os vermes ordenados, a terceira estratexia é máis rápida, en xeral, pero pode tocar que haxa moitos vermes na mesma fenda e entón tornase igual que a primeira).
No caso da busca binaria podemos tamén facer ver cal será o máximo número de intentos que hai que facer para localizar un verme, en función do número total de vermes que teñamos (se temos 100 vermes a busca é 7, para 1000 o máximo número é 10 e para 10000 os intentos so aumentan a 14. ( En xeral, para n vermes o máximo número de intentos sería log2n (lembramos que n = 2nº intentos ). Deixamos unha ligazón cunha calculadora para seguir probando e comprobar que o número de intentos non aumenta ao mesmo tempo que o número de vermes senón moito menos.
3º Xogo : Realizar taboleiros para busca con clave.
Neste caso deberás realizar os teus propios pares de taboleiros, pero sen especificar a clave que vas empregar, de xeito que sexa o propio xogador o que teña que adiviñala primeiro, antes de poñerse a xogar.
Neste caso primeiro haberá que descifrar un algoritmo, podemos aproveitar para introducir o concepto de Criptografía, no que é habitual empregar o método de busca por clave (hashing).
Basado en: https://classic.csunplugged.org/