✍ 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

Última actualização/Last updated: 2014-11-13 [00:04]


1999-2014 (ç) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.