ГО и полный перебор вариантов.

Тут полемика возникла:

>> Автор: Les
>> Описать формально задачу оптимальной го-игры труда не
>> составляет. Такое описание можно скормить машине
>> и она отыщет наилучший ход с помощью полного перебора.

>> Автор: Максим Подоляк
>> Лес, вон, предлагает скормить машине составленную без труда
>> формально описанную задачу го.
>> скормите уже наконец, да проверьте на маленькой доске,
>> если всё так просто.

В самом деле, почему бы, для начала, не написать прогу для доски 5х5
или 4х4 чтобы счётных ресурсов хватило.

Дело в том, что после рассмотрения какого-либо варианта,
надо в конце, то есть после двух пасов, вычислить ценность данного
варианта, ну просто посчитать результат партии.

А так как варианты перебираются все,
то мы непременно выходим на иррациональные позиции,
в которых результат партии посчитать нет возможности даже человеку
(с его интеллектом, что уж говорить о машине :)).
Поэтому полный перебор в ГО не работает.

Но это ещё пол беды.
Очень трудно для машины, при полном переборе вариантов,
определить, когда заканчивается партия.
В некоторых вариантах машине кажется, что игра продолжается
и продолжается.

Так что Подоляк, к сожалению прав,
даже на маленькой, балин, доске, перебор не работает.

Да зачем далеко ходить,
у меня в базе данных лежит простая законченная партия 19х19,
c двумя пасами в конце,
а машина посчитать результат не может, алгоритм слишком слабый.

(;GM[1]PB[maple]PW[pei]RB[6D]RW[6D]HA[0]KM[5.5]SZ[19]
;B[dp];W[pp];B[dc];W[pd];B[nc];W[qf];B[pb];W[df];B[ce];W[cn];B[cf];W[fq];B[fp]
;W[gp];B[eq];W[fo];B[ep];W[fr];B[go];W[hp];B[fn];W[ho];B[eo];W[dh];B[dg];W[eg]
;B[cg];W[eh];B[co];W[er];B[bn];W[cq];B[nq];W[lq];B[lp];W[kq];B[no];W[pn];B[pr]
;W[mq];B[pq];W[op];B[np];W[qq];B[rq];W[rp];B[qr];W[qp];B[sq];W[nr];B[or];W[mr]
;B[oq];W[pk];B[qc];W[ec];B[db];W[jd];B[re];W[nd];B[mc];W[oc];B[ob];W[md];B[rf]
;W[qg];B[rg];W[qh];B[rh];W[qj];B[ci];W[dj];B[cj];W[jj];B[lc];W[ld];B[kc];W[jc]
;B[kd];W[ke];B[je];W[hd];B[ie];W[gd];B[kf];W[le];B[ih];W[kh];B[gf];W[dd];B[cd]
;W[ff];B[hj];W[ig];B[hg];W[jg];B[ji];W[ki];B[he];W[hk];B[gj];W[nm];B[fe];W[fd]
;B[ee];W[ge];B[ef];W[rs];B[rr];W[ss];B[ln];W[ko];B[kp];W[mp];B[os];W[qs];B[nn]
;W[lo];B[om];W[nl];B[pm];W[qm];B[ql];W[pl];B[qn];W[rm];B[po];W[rn];B[mm];W[mo]
;B[mn];W[km];B[on];W[ro];B[ri];W[eb];B[jf];W[mg];B[ij];W[ik];B[jb];W[ib];B[hb]
;W[ia];B[id];W[ic];B[hc];W[kb];B[fb];W[gc];B[gb];W[fa];B[de];W[gk];B[fk];W[fl]
;B[el];W[gm];B[fm];W[gl];B[rk];W[rj];B[sj];W[rl];B[dr];W[cr];B[dq];W[bp];B[bo]
;W[ds];B[cp];W[bq];B[lf];W[mf];B[qe];W[pe];B[qi];W[pi];B[gn];W[hn];B[pc];W[od]
;B[lg];W[lh];B[hf];W[hh];B[ej];W[jh];B[ii];W[ao];B[an];W[ap];B[qd];W[qk];B[sk]
;W[sl];B[si];W[kj];B[fg];W[tt];B[tt];W[tt])

Засеките, сколько секунд Вам надо, чтобы посчитать результат.
Если по-правильному считать, то надо проверить все разрезания
внутри территорий, а вдруг партия до конца не доиграна.



Отправка отредактированного (22/08/04 19:41)

Отправка отредактированного (01/09/04 19:42)

Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi

Да мы так, поболтать вышли. :))

Если серьёзно, то я, например, экономлю время будующих разработчиков,
отбрасывая тупиковые ветки в разработке.

Ведь зарплата хорошего программиста выше чем зарплата хорошего
тренера по ГО, поэтому человеко-часы программистов надо экономить
любыми способами.

а) как можно больше говорить по теме (без устали от нас :)).
б) отбрасывать тупиковые ветки в разработке.
в) как можно дольше не начинать программировать.

И тогда количество разговоров перейдёт в качество понимания задачи,
кто-нибудь из новых программеров созреет и сделает прорыв.
Таким образом мы напишем вместе сильную программу.

Мелсу: аплодисменты за последнюю реплику.
:))
Да, кстати, когда я говорил "маленькая доска", я имел ввиду 9х9.
И ни центом меньше.



Отправка отредактированного (27/08/04 17:33)

<Китай в нашем сердце>

Браво!!!!

>> Да, кстати, когда я говорил "маленькая доска", я имел ввиду 9х9.

Для 9х9 это около 81 факториал вариантов.
посчитать пока не хватит вычислительных ресурсов.

Доска 5х5 это 25! вариантов, тоже слишком много вариантов.

Вот доска 4х4 это всего 16 факториал вариантов - машина посчитать может,
но для 4х4 я сам могу за день найти оптимальную стратегию игры.

Во втором постинге заголовок партии имеет вид:

(;GM[1]RE[W+5.5]DT[September 22, 2001]PB[maple]PW[pei]RB[6D]RW[6D]HA[0]KM[5.5]SZ[19]

Следовательно результат партии - белые выиграли 5.5 очка при коми 5.5 очка.

>> kit144
>> Отправка отредактированного (01/09/04 19:42)

Kit ты чего :)) , стыдно что ли ?

Погорячился человек ;)



Эксперимент продолжается...

Не в настроении был.
Тем более, что с этой долбаной графикой воюю.
Я ее терпеть ненавижу.......

P.S.
Решил объединить два языка программирования:
ASM и LISP.
на Lisp многие варианты решения программируются проще.
Только вот для перебора позиций, этот язык медленный.



Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[www2.psy.uq.edu.au]
[www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[habrahabr.ru]
[shogi.by] - Shuogi