БлогNot. Депрессивные крестики-нолики или Как Не Надо Писать :)

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

Депрессивные крестики-нолики или Как Не Надо Писать :)

Собственно, вот: ссылка

Некогда (очень давно) задумывалось, что выиграть у этого нельзя. Но, во-первых, можно, т.к. есть баг (см. ниже на картинке и помеченное "bug is here" место в исходнике), во-вторых, представим, что бага нет и всё работает, а писать так всё равно не надо. Почему? А достаточно взглянуть на этот самый исходник, он воистину страшен:

<script type="text/javascript">
 //Определение рисунков
 var k=new Image(); k.src="cross.gif";
 var n=new Image(); n.src="null.gif";
 var e=new Image(); e.src="empty.gif";

 var step=0; //Номер хода (1-5)
 var userpos=0;  //Клетка, занятая юзером
 var t=new Array(9); //Буфер для поля
 var win=0; //Побед компа
 var draw=0; //Ничьих
 var begin=0; //Метка обновления поля

 function start(compwin) { //Начало игры
  if (compwin) { win++; document.getElementById('score').innerHTML = "Вы проиграли"; }
  else { draw++; document.getElementById('score').innerHTML = "Ничья"; }
  document.getElementById('score').innerHTML += '. Общий счёт '+win+':'+draw+':0';
  begin=1;
  step=userpos=0;
 }

 function click (b) { //Клик по клетке b (0-9) :)
  if (begin) { for (var i=0; i<9; i++) document.images['pos'+i].src=e.src; begin=0; return; }
  document.getElementById('score').innerHTML = 'Играем. Общий счёт '+win+':'+draw+':0';
  if ((document.images['pos'+b].src==k.src) || (document.images['pos'+b].src==n.src)) return; //Занято тут!
  step++;
  document.images['pos'+b].src=k.src;
  userpos=b;
  test();
 }

 function rand() { //Случайное число 0-8 (без аргументов) или из списка
  if (arguments.length>0)return arguments[Math.floor(Math.random()*arguments.length)];
  else return Math.floor(Math.random()*9);
 }

 function test() { //Основная функция
  if (step==1) {
   if (document.images['pos4'].src==k.src) { //Лох занял центр на 1 шаге
    document.images['pos'+rand(0,2,6,8)].src=n.src; //Тогда случайненько из угловых
   }
   else { //Лох не занял центр - занять
    document.images['pos4'].src=n.src;
   }
  } //1
  else if (step==2) {
   if (document.images['pos4'].src==k.src) {
    b2=userpos-8; if(b2<0) b2=-b2;
    if(document.images['pos'+b2].src!==n.src) document.images['pos'+b2].src=n.src;
    else {
     if (document.images['pos0'].src==e.src) b2=0;
     else {
      if (rand()>5) b2=2; else b2=6;
     }
     document.images['pos'+b2].src=n.src
    }
   }
   else if (document.images[4].src==n.src) {
    if (testAll()==0) {
     if(testNols()!=1) {
      if(t[0]==e.src) document.images['pos0'].src=n.src;
      else {
       if(t[2]==e.src) document.images['pos2'].src=n.src;
       else {
        if(t[6]==e.src) document.images['pos6'].src=n.src;
        else {
         if(t[8]==e.src) document.images['pos8'].src=n.src;
        }
       }
      }
     }
    }
   }
  } //2
  else if (step==3) { //3
   if (document.images['pos4'].src==k.src) {
    if (testWin()==1) start(1);
    else {
     b3=userpos-8; if(b3<0) b3*=-1;
     if (document.images['pos'+b3].src==e.src) document.images['pos'+b3].src=n.src;
     else {
      if (document.images['pos0'].src==e.src) document.images['pos0'].src=n.src;
      else {
       if (document.images['pos2'].src==e.src) document.images['pos2'].src=n.src;
       else {
        if (document.images['pos6'].src==e.src) document.images['pos6'].src=n.src;
        else {
         if (document.images['pos8'].src==e.src) document.images['pos8'].src=n.src;
        }
       }
      }
     }
    }
   }
   else if (document.images['pos4'].src==n.src) {
    if (testWin()==1) start(1);
    else {
     if (testAll()==0) {
      if (document.images['pos8'].src==e.src) document.images['pos8'].src=n.src;
      else {
       if (document.images['pos6'].src==e.src) document.images['pos6'].src=n.src;
       else {
        if (document.images['pos2'].src==e.src) document.images['pos2'].src=n.src;
        else {
         if (document.images['pos0'].src==e.src) document.images['pos0'].src=n.src;
         else {
          if (document.images['pos1'].src==e.src) document.images['pos1'].src=n.src;
          else {
           if (document.images['pos3'].src==e.src) document.images['pos3'].src=n.src;
           else {
            if (document.images['pos5'].src==e.src) document.images['pos5'].src=n.src;
            else {
             if (document.images['pos7'].src==e.src) document.images['pos7'].src=n.src;
            }
           }
          }
         }
        }
       }
      }
     }
    }
   }
  } //3
  else if (step==4) {
   if (document.images['pos4'].src==k.src) {
    if (testWin()==1) start(1);
    else {
     b3=userpos-8; if (b3<0) b3*=-1;
     if (document.images['pos'+b3].src==e.src) document.images['pos'+b3].src=n.src;
     else {
      if (document.images['pos8'].src==e.src) document.images['pos8'].src=n.src;
      else {
       if (document.images['pos6'].src==e.src) document.images['pos6'].src=n.src;
       else {
        if (document.images['pos2'].src==e.src) document.images['pos2'].src=n.src;
        else {
         if (document.images['pos0'].src==e.src) document.images['pos0'].src=n.src;
         else {
          if (document.images['pos1'].src==e.src) document.images['pos1'].src=n.src;
          else {
           if (document.images['pos3'].src==e.src) document.images['pos3'].src=n.src;
           else {
            if (document.images['pos5'].src==e.src) document.images['pos5'].src=n.src;
            else {
             if (document.images['pos7'].src==e.src) document.images['pos7'].src=n.src;
            }
           }
          }
         }
        }
       }
      }
     }
    }
   }
   else if (document.images['pos4'].src==n.src) {
    if (testWin()==1) start(1);
    else {
     if (document.images['pos8'].src==e.src) document.images['pos8'].src=n.src;
     else {
      if (document.images['pos6'].src==e.src) document.images['pos6'].src=n.src;
      else {
       if (document.images['pos2'].src==e.src) document.images['pos2'].src=n.src;
       else {
        if (document.images['pos0'].src==e.src) document.images['pos0'].src=n.src;
        else {
         if (document.images['pos1'].src==e.src) { //bug is here
          document.images['pos1'].src=n.src;
         }
         else {
          if (document.images['pos3'].src==e.src) document.images['pos3'].src=n.src;
          else {
           if (document.images['pos5'].src==e.src) document.images['pos5'].src=n.src;
           else {
            if (document.images['pos7'].src==e.src) document.images['pos7'].src=n.src;
           }
          }
         }
        }
       }
      }
     }
    }
   }
  } //4
  else if(step==5) start(0);
 }

 function testAll() { //Тестирует всё :)
  var ta=0;
  for (var i=0; i<9; i++) t[i]=document.images['pos'+i].src;
  if (( ((t[1]==k.src)&&(t[2]==k.src)) || ((t[1]==n.src)&&(t[2]==n.src)) || ((t[3]==k.src)&&(t[6]==k.src)) || 
        ((t[3]==n.src)&&(t[6]==n.src)) || ((t[4]==k.src)&&(t[8]==k.src)) || ((t[4]==n.src)&&(t[8]==n.src)) )
      && (t[0]==e.src)
     ) { document.images['pos0'].src=n.src; ta=1; }
  if (( ((t[0]==k.src)&&(t[2]==k.src)) || ((t[0]==n.src)&&(t[2]==n.src)) || ((t[4]==k.src)&&(t[7]==k.src)) || 
        ((t[4]==n.src)&&(t[7]==n.src)) )
      && (t[1]==e.src)
     ) { document.images['pos1'].src=n.src; ta=1; }
  if (( ((t[1]==k.src)&&(t[0]==k.src)) || ((t[1]==n.src)&&(t[0]==n.src)) || ((t[5]==k.src)&&(t[8]==k.src)) ||
        ((t[5]==n.src)&&(t[8]==n.src)) || ((t[4]==k.src)&&(t[6]==k.src))|| ((t[4]==n.src)&&(t[6]==n.src)) )
      && (t[2]==e.src)
     ) { document.images['pos2'].src=n.src; ta=1; }
  if (( ((t[0]==k.src)&&(t[6]==k.src)) || ((t[0]==n.src)&&(t[6]==n.src)) || ((t[4]==k.src)&&(t[5]==k.src)) ||
        ((t[4]==n.src)&&(t[5]==n.src)) )
      && (t[3]==e.src)
     ) { document.images['pos3'].src=n.src; ta=1; }
  if (( ((t[2]==k.src)&&(t[8]==k.src)) || ((t[2]==n.src)&&(t[8]==n.src)) || ((t[4]==k.src)&&(t[3]==k.src)) ||
        ((t[4]==n.src)&&(t[3]==n.src)) )
      && (t[5]==e.src)
     ) { document.images['pos5'].src=n.src; ta=1; }
  if (( ((t[0]==k.src)&&(t[3]==k.src)) || ((t[0]==n.src)&&(t[3]==n.src)) || ((t[2]==k.src)&&(t[4]==k.src)) ||
        ((t[2]==n.src)&&(t[4]==n.src)) || ((t[7]==k.src)&&(t[8]==k.src)) || ((t[7]==n.src)&&(t[8]==n.src)) )
      && (t[6]==e.src)
     ) { document.images['pos6'].src=n.src; ta=1; }
  if (( ((t[1]==k.src)&&(t[4]==k.src)) || ((t[1]==n.src)&&(t[4]==n.src)) || ((t[6]==k.src)&&(t[8]==k.src)) ||
        ((t[6]==n.src)&&(t[8]==n.src)) )
      && (t[7]==e.src)
     ) { document.images['pos7'].src=n.src; ta=1; }
  if (( ((t[6]==k.src)&&(t[7]==k.src)) || ((t[6]==n.src)&&(t[7]==n.src)) || ((t[0]==k.src)&&(t[4]==k.src)) ||
        ((t[0]==n.src)&&(t[4]==n.src)) || ((t[2]==k.src)&&(t[5]==k.src)) || ((t[2]==n.src)&&(t[5]==n.src)))
      && (t[8]==e.src)
     ) { document.images['pos8'].src=n.src; ta=1; }
  return ta;
 }

 function testWin() { //Тестирует победу компа
  var nol=0;
  for (var i=0; i<9; i++) t[i]=document.images['pos'+i].src;
  if (( ((t[1]==n.src)&&(t[2]==n.src)) || ((t[3]==n.src)&&(t[6]==n.src)) || ((t[4]==n.src)&&(t[8]==n.src)))
      && (t[0]==e.src)) { document.images['pos0'].src=n.src; nol=1; }
  if (( ((t[0]==n.src)&&(t[2]==n.src)) || ((t[4]==n.src)&&(t[7]==n.src)))
      && (t[1]==e.src)) { document.images['pos1'].src=n.src; nol=1; }
  if (( ((t[1]==n.src)&&(t[0]==n.src)) || ((t[5]==n.src)&&(t[8]==n.src)) || ((t[4]==n.src)&&(t[6]==n.src)))
      && (t[2]==e.src)) { document.images['pos2'].src=n.src; nol=1; }
  if (( ((t[0]==n.src)&&(t[6]==n.src)) || ((t[4]==n.src)&&(t[5]==n.src)))
      && (t[3]==e.src)) { document.images['pos3'].src=n.src; nol=1; }
  if (( ((t[2]==n.src)&&(t[8]==n.src)) || ((t[4]==n.src)&&(t[3]==n.src)))
      && (t[5]==e.src)) { document.images['pos5'].src=n.src; nol=1; }
  if (( ((t[0]==n.src)&&(t[3]==n.src)) || ((t[2]==n.src)&&(t[4]==n.src)) || ((t[7]==n.src)&&(t[8]==n.src)))
      && (t[6]==e.src)) { document.images['pos6'].src=n.src; nol=1; }
  if (( ((t[1]==n.src)&&(t[4]==n.src)) || ((t[6]==n.src)&&(t[8]==n.src)))
      && (t[7]==e.src)) { document.images['pos7'].src=n.src; nol=1; }
  if (( ((t[6]==n.src)&&(t[7]==n.src)) || ((t[0]==n.src)&&(t[4]==n.src)) || ((t[2]==n.src)&&(t[5]==n.src)))
      && (t[8]==e.src)) { document.images['pos8'].src=n.src; nol=1; }
  return nol;
 }

 function testNols() {
  var nols=0;
  for (var i=0; i<9; i++) t[i]=document.images['pos'+i].src;
  if (( ((t[1]==k.src)&&(t[3]==k.src))) || ((t[3]==k.src)&&(t[2]==k.src))
      && (t[0]==e.src)) { document.images['pos0'].src=n.src; nols=1; }
  if (( ((t[1]==k.src)&&(t[5]==k.src))) || ((t[5]==k.src)&&(t[0]==k.src))
      && (t[2]==e.src)) { document.images['pos2'].src=n.src; nols=1; }
  if (( ((t[3]==k.src)&&(t[7]==k.src))) || ((t[3]==k.src)&&(t[8]==k.src))
      && (t[6]==e.src)) { document.images['pos6'].src=n.src; nols=1; }
  if (( ((t[5]==k.src)&&(t[7]==k.src))) || ((t[5]==k.src)&&(t[6]==k.src))
      && (t[0]==e.src)) { document.images['pos8'].src=n.src; nols=1; }
  if ((t[0]==k.src)&&(t[8]==k.src)) {
   if (rand()>5) document.images['pos3'].src=n.src;
   else document.images['pos5'].src=n.src;
   nols=1;
  }
  if ((t[6]==k.src)&&(t[2]==k.src)) {
   if (rand()>5) document.images['pos7'].src=n.src;
   else document.images['pos1'].src=n.src;
   nols=1; 
  }
  return nols;
 }

 //Отрисовка поля
 for (var i=0; i<9; i+=3) {
  document.writeln ('<div align="center">');
  for (var j=i; j<i+3; j++) document.writeln 
   ('<a href="javascript:click('+j+')"><img src="empty.gif" border=0 id="pos'+j+'"></a>');
  document.writeln ('</div>');
 }
 document.writeln ('<div align="center" id="score"></div>');
</script>
<noscript>Извините, для работы приложения нужен включённый Javascript</noscript>

А вот и ситуация бага:

Баг - лженичья
Баг - лженичья

Надо ли говорить, что перебор, да ещё и "одномерный", зависящий от абсолютной координаты игрового поля в массиве - не решение, и уже на размерности поля 4 на 4 код никуда не будет годиться?

Попробуем слегка исправить ситуацию, привлекая пока пусть не грамотные и теоретически обоснованные алгоритмы, так хотя бы естественные соображения о проверке и оценке своей позиции и позиции соперника.

 Крестики-нолики - более грамотная версия

<script type="text/javascript">
 var c=new Image(); c.src="cross.gif";
 var n=new Image(); n.src="null.gif";
 var e=new Image(); e.src="empty.gif"; //определение рисунков
 var size=3; //размер поля
 var f=new Array(size); //поле; 0-пусто,'c','n'
 for (i=0; i<size; i++) f[i]=new Array(size);
 var count=new Array ('0','0','0'); //счет
 var begin=0; //метка обновления поля
 var step=0; //номер хода
 var timeOutID;

 for (i=0; i<size; i++) { //отрисовка поля
  document.writeln ('<div align="center">');
  for (j=0; j<size; j++) {
   f[i][j]=0;
   document.writeln 
    ('<a href="javascript:click('+i+','+j+')"><img src="empty.gif" border=0 id="#'+i+'#'+j+'"></a>');
  }
  document.writeln ('</div>');
 }
 document.writeln ('<div align="center" id="score"></div>');

 function start() { //Начало игры
  var win=1;
  if (search_line('c')) win=0;
  else if (search_line('n')) win=2;
  var msg=new Array('Вы выиграли','Ничья','Вы проиграли');
  count[win]++;
  document.getElementById('score').innerHTML = msg[win];
  document.getElementById('score').innerHTML += '. Общий счёт '+count[0]+':'+count[1]+':'+count[2];
  begin=1; step=0;
 }

 function click (rr,cc) { //Клик по клетке rr,cc
  if (begin) { 
   for (i=0; i<size; i++) {
    for (j=0; j<size; j++) { f[i][j]=0; document.images['#'+i+'#'+j].src=e.src; }
   }
   begin=0; return; 
  }
  document.getElementById('score').innerHTML = 'Играем. Общий счёт '+count[0]+':'+count[1]+':'+count[2];
  if (f[rr][cc]=='c' || f[rr][cc]=='n') return; //Занято тут!
  document.images['#'+rr+'#'+cc].src=c.src; f[rr][cc]='c';
  step++;
  if (empty()==0 || search_line('c') || search_line('n')) { start (); return; }
  timeOutID = window.setTimeout ("comp()",300); //Задержка перед ходом компа
 }

 function comp() {
  window.clearTimeout (timeOutID);
  test();
  if (empty()==0 || search_line('c') || search_line('n')) start ();
 }

 function rand(n) { //Случайное целое число [0;n-1]
  return Math.floor(Math.random()*n);
 }

 function test() { //Основная функция
  if (step==1) { //Первый шаг - отдельно
   var div=Math.floor(size/2),mod=size%2;
   if (f[div][div]==0) { document.images['#'+div+'#'+div].src=n.src; f[div][div]='n'; }
   else { 
    var i,j;
    if(rand(2)==0) i=0; else i=size-1;
    if(rand(2)==0) j=0; else j=size-1;
    document.images['#'+i+'#'+j].src=n.src; f[i][j]='n';
   } 
   return;
  }
  //Можем победить этим ходом?
  for (i=0; i<size; i++) {
   for (j=0; j<size; j++) {
    if (f[i][j]==0) {
     f[i][j]='n';
     bool=(count_row(i,'n')==size || count_col(j,'n')==size || 
           count_diag1('n')==size || count_diag2('n')==size);
     f[i][j]=0;
     if (bool) { document.images['#'+i+'#'+j].src=n.src; f[i][j]='n'; return; }
    }
   }
  }
  //Соперник может победить следующим ходом?
  for (i=0; i<size; i++) if (count_row(i,'c')==size-1)  {
   j = search_col(i,0);
   document.images['#'+i+'#'+j].src=n.src; f[i][j]='n'; return;
  }
  for (j=0; j<size; j++) if (count_col(j,'c')==size-1)  {
   i = search_row(j,0);
   document.images['#'+i+'#'+j].src=n.src; f[i][j]='n'; return;
  }
  if (count_diag1('c')==size-1)  {
   i = search_diag1(0);
   document.images['#'+i+'#'+i].src=n.src; f[i][i]='n'; return;
  }
  if (count_diag2('c')==size-1)  {
   i = search_diag2(0);
   document.images['#'+i+'#'+(size-1-i)].src=n.src; f[i][size-1-i]='n'; return;
  }
  //У нас будет ход до победы, а у него нет?
  for (i=0; i<size; i++) {
   for (j=0; j<size; j++) {
    if (f[i][j]==0) {
     f[i][j]='n';
     bool=(count_row(i,'n')==size-1 || count_col(j,'n')==size-1); //Диагонали здесь не смотрим
     f[i][j]=0;
     if (bool) { document.images['#'+i+'#'+j].src=n.src; f[i][j]='n'; return; }
    }
   }
  }
  //Автоматическая ничья
  var draw=1;
  for (i=0; i<size; i++) {
   if (search_col(i,'c')==-1) { draw=0; break; }
   if (search_col(i,'n')==-1) { draw=0; break; }
  }
  for (j=0; j<size; j++) {
   if (search_row(j,'c')==-1) { draw=0; break; }
   if (search_row(j,'n')==-1) { draw=0; break; }
  }
  if (draw) {
   count[1]++;
   document.getElementById('score').innerHTML = 
    'Ничья, дальше играть бессмысленно. Общий счёт '+count[0]+':'+count[1]+':'+count[2];
   begin=1; step=0; 
   return;
  }
  //Ищем макс.выгоду для следующего хода
  var mmax=0,mm,ii=-1,jj=-1;
  for (i=0; i<size; i++) {
   for (j=0; j<size; j++) {
    if (f[i][j]==0) {
     f[i][j]='n'; 
     mm=count_row(i,'n')+count_col(j,'n');
     if (i==j) mm+=count_diag1('n');
     if (i==size-1-j) mm+=count_diag2('n');
     f[i][j]=0;
     if (mm>mmax) { mmax=mm; ii=i; jj=j; }
    }
   }
  }
  //Ищем макс.ущерб для соперника следующим ходом
  var nmax=0,nn,iii=-1,jjj=-1;
  for (i=0; i<size; i++) {
   for (j=0; j<size; j++) {
    if (f[i][j]==0) {
     f[i][j]='c'; 
     nn=count_row(i,'c')+count_col(j,'c');
     if (i==j) nn+=count_diag1('c');
     if (i==size-1-j) nn+=count_diag2('c');
     f[i][j]=0;
     if (nn>nmax) { nmax=nn; iii=i; jjj=j; }
    }
   }
  }
  if (nmax>=mmax && iii>-1 && jjj>-1) { document.images['#'+iii+'#'+jjj].src=n.src; f[iii][jjj]='n'; }
  else if (ii>-1 && jj>-1) { document.images['#'+ii+'#'+jj].src=n.src; f[ii][jj]='n'; }
 }

 function compare(f,c) {
  if (f==c) return 1;
  else if (f==0) return 0;
  else return -1;
 }

 function count_row (row,side) {
  cnt=0;
  for (j=0; j<size; j++) cnt+=compare(f[row][j],side);
  return cnt;
 }

 function count_col (col,side) {
  cnt=0;
  for (i=0; i<size; i++) cnt+=compare(f[i][col],side);
  return cnt;
 }

 function count_diag1 (side) {
  cnt=0;
  for (i=0; i<size; i++) cnt+=compare(f[i][i],side);
  return cnt;
 }

 function count_diag2 (side) {
  cnt=0;
  for (i=0; i<size; i++) cnt+=compare(f[i][size-1-i],side);
  return cnt;
 }

 function search_col(row,side) {
  for (j=0; j<size; j++) if (f[row][j]==side) return j;
  return -1;
 }

 function search_row(col,side) {
  for (i=0; i<size; i++) if (f[i][col]==side) return i;
  return -1;
 }

 function search_diag1(side) {
  for (i=0; i<size; i++) if (f[i][i]==side) return i;
 }

 function search_diag2(side) {
  for (i=0; i<size; i++) if (f[i][size-1-i]==side) return i;
 }

 function empty () { //кол-во пустых полей
  var k=0;
  for (i=0; i<size; i++) for (j=0; j<size; j++) if (f[i][j]==0) k++;
  return k;
 }

 function search_line (side) {
  for (i=0; i<size; i++) if (count_row(i,side)==size) return 1;
  for (j=0; j<size; j++) if (count_col(j,side)==size) return 1; 
  if (count_diag1(side)==size || count_diag2(side)==size) return 1;
  return 0;
 }
</script>
<noscript>Извините, для работы приложения нужен включённый Javascript</noscript>

Собственно, полезной в этом коде, кроме возможности изменить размер поля size, может оказаться "неожиданная" похожесть блоков "Ищем макс.выгоду для следующего хода" и "Ищем макс.ущерб для соперника следующим ходом". Ещё немного раздумий - и можно дойти до понятия минимакса, с которого, на самом деле, и нужно начинать изучение программирования игр (особенно с нулевой суммой).

Очень толковая статья про игры с нулевой суммой и минимакс есть вот тут... на примере рэндзю-подобной игры в крестики-нолики на поле 10x10, есть реализация и исходники на java.

Вот картинки для игры, имена указаны в начале кода, предполагается, что лежат в той же папке, что и скрипт.

cross.gif
cross.gif
null.gif
null.gif
empty.gif
empty.gif

 Крестики-нолики для 2 человек на JQuery с исходником и демо

 Схема игры 3x3 есть в Вики :)


теги: javascript программирование игра алгоритм ошибка

комментарии (0)

19.06.2014, 19:39; рейтинг: 10178

  свежие записипоиск по блогукомментироватьстатистика

Наверх Яндекс.Метрика
© PerS
вход