Axiom: Man over Machine

Jogo intitulado de Hi-Lo.

Tenho guardado o livro Master Library da TI Programable 58/59 uma calculadora da Texas Instruments; um verdadeiro prodígio da computação para a altura (1977).

A página 21 inclui a descrição de um jogo chamado de Hi-Lo game. É descrito como

The game is a easy to play, permitting almost immediate hands-on experience for any user.

O objectivo do jogo é simples, adivinhar o número entre 1 e 1023 escolhido inicialmente pela calculadora. Depois do jogador fazer uma escolha a calculadora responde "too high" ou "too low" conforme o caso ou ainda "correct" indicando que a nossa escolha é a correcta e o jogo acaba.

O jogo pode também ser jogado com os papeis invertidos, agora escolhemos nós o número e a máquina joga para o adivinhar.

O último parágrafo coloca a dúvida sobre o axioma "man over machine" sugerindo ao utilizador jogar o jogo com a máquina escolhendo ele um número previamente usado num jogo em que estaria a adivinhar esse número determinado pela máquina, e comparar desempenhos.

Qual a estratégia mais eficiente, isto é, aquela que minimiza o número de jogadas/escolhas, que permite encontrar o número escolhido?

Uma trivialidade dirão uns, e os outros?

Knuth diz-nos que (TAOCP, pg. 410):

"Although the basic idea of binary search is comparatively straight forward, the details can be surprisingly tricky, and many good programmers have done it wrong the first few times they tried."

e claro que as notícias correm depressa

"Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken"

Uma implementação em Emacs Lisp "bug free":

(defun hilo (choice low high)
"Hi-Lo Game: a recursive bug-free binary
                        search algorithm implementation."
(let*
    ((x (+ low (/ (- high low) 2))))
  (cond (
         (< x choice)
         (hilo choice x high))
        ((> x choice)
         (hilo choice low x))
        ((= x choice)
         (message  (number-to-string x))))))

Este código está mesmo TODO errado! O correcto é este:

(defun binary-search (k l u)
  (let ((i (+ l (floor (/ (- u l) 2)))))
    (cond ((> i k)
           (binary-search k i (- u 1)))
           ((< i k)
           (binary-search k (+ l 1) i))
           ((= i k)
         i))))

Palavras chave/keywords: Lisp, Jogos, Hi-Lo, Emacs

Criado/Created: NaN

Última actualização/Last updated: 10-10-2022 [14:26]

Voltar à página inicial.