Депрессивные крестики-нолики или Как Не Надо Писать :)
Собственно, вот: ссылка
Некогда (очень давно) задумывалось, что выиграть у этого нельзя. Но, во-первых, можно, т.к. есть баг (см. ниже на картинке и помеченное "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
null.gif
empty.gif
Крестики-нолики для 2 человек на JQuery с исходником и демо
19.06.2014, 19:39 [13862 просмотра]