Master mind (parte seconda)

Nell’articolo precedente ho mostrato un package PL/SQL che funge da “codemaker” e consente di giocare a Master Mind contro il db Oracle.
A questo punto mi sono anche posto il problema di scrivere un programma che potesse automaticamente giocare una partita nel modo migliore possibile.
Ho scritto quindi il package mmp (scaricatelo qui).

Ecco la spec:

create or replace package mmp is
function goAlone return number;
end;
/

Molto semplice, la funzione goAlone avvia una nuova partita e la gioca, restituendo il numero di tentativi che sono stati necessari a trovare la soluzione.

Vediamo un esempio:

SQL> select mmp.goAlone from dual;

   GOALONE
----------
         6
#######################################
01 C6 C2 C1 C5:BW
#######################################
TRY AGAIN.
After this guess there are still 660 possible solutions
#######################################
01 C6 C2 C1 C5:BW
02 C3 C2 C8 C1:W
#######################################
TRY AGAIN.
After this guess there are still 147 possible solutions
#######################################
01 C6 C2 C1 C5:BW
02 C3 C2 C8 C1:W
03 C5 C1 C4 C5:BW
#######################################
TRY AGAIN.
After this guess there are still 23 possible solutions
#######################################
01 C6 C2 C1 C5:BW
02 C3 C2 C8 C1:W
03 C5 C1 C4 C5:BW
04 C4 C6 C3 C5:B
#######################################
TRY AGAIN.
After this guess there are still 6 possible solutions
#######################################
01 C6 C2 C1 C5:BW
02 C3 C2 C8 C1:W
03 C5 C1 C4 C5:BW
04 C4 C6 C3 C5:B
05 C7 C5 C2 C5:BBW
#######################################
TRY AGAIN.
After this guess there are still 1 possible solutions
#######################################
01 C6 C2 C1 C5:BW
02 C3 C2 C8 C1:W
03 C5 C1 C4 C5:BW
04 C4 C6 C3 C5:B
05 C7 C5 C2 C5:BBW
06 C2 C5 C5 C5:BBBB
#######################################
YOU GOT IT! WELL DONE!!!
C2 C5 C5 C5

Qualche dettaglio sull’algoritmo:
All’inizio il package memorizza in un array associativo tutte le 4096 possibili combinazioni in ordine casuale.

procedure fillSolTab is
begin

  if solTab.count > 0 then
     solTab.delete(solTab.first,solTab.last);
  end if;

  with t as (
    select mm.c1 col from dual union all
    select mm.c2 from dual union all
    select mm.c3 from dual union all
    select mm.c4 from dual union all
    select mm.c5 from dual union all
    select mm.c6 from dual union all
    select mm.c7 from dual union all
    select mm.c8 from dual)
  select t1.col, t2.col, t3.col, t4.col
    bulk collect into solTab
    from t t1, t t2, t t3, t t4
  order by dbms_random.value;

end;

Poi prende la prima e la prova.

function nextTry return number is
res mm.t_res;
sol t_sol := solTab(solTab.first);
begin
  res := mm.tryThis(sol.s1,sol.s2,sol.s3,sol.s4);

  if res.game_over = 0 then
     cleanSolTab(res.r1||res.r2||res.r3||res.r4);
  end if;

  return res.game_over;
end;

Ovviamente ottiene dal package mm un feedback che viene utilizzato per eliminare dalla tabella di tutte le combinazioni quelle che non possono essere più valide.

procedure cleanSolTab(p_res in varchar2) is
i number;
currSol t_sol;
markForDelete number;
begin
  i := solTab.first;
  currSol := solTab(i);
  solTab.delete(i);
  i := solTab.first;
  loop
    if nvl(checkSol(solTab(i),currSol),'x') != nvl(p_res,'x') then
       markForDelete := i;
    else
       markForDelete := 0;
    end if;
    exit when i=solTab.last;
    i := solTab.next(i);
    if markForDelete>0 then
       solTab.delete(markForDelete);
    end if;
  end loop;

  if markForDelete>0 then
     solTab.delete(markForDelete);
  end if;

  dbms_output.put_line('After this guess there are still '||solTab.count||' possible solutions');
end;

Dopodiché continua a provare in questo modo finché non trova la combinazione giusta.

function goAlone return number is
num number:=0;
begin
  startGame;
  loop
    num := num+1;
  exit when nextTry != 0;
  end loop;

  return num;

end;

Se si gioca un numero molto alto di partite (non vi dimenticate di spegnere il serverout!!) si vede che il mio metodo ottiene la soluzione con un numero medio di circa 5,5 tentativi:

SQL> select min(g), max(g), avg(g), stddev(g)
  2  from (select mmp.goalone g from dual connect by level<=100);

    MIN(G)     MAX(G)     AVG(G)  STDDEV(G)
---------- ---------- ---------- ----------
         3          8       5.47 .968754277

Se qualcuno trova un algoritmo che consente di ottenere una media più bassa mi faccia sapere…

Massimo