Здраствуйте. Когда-то давно придумал AI для шахмат. Потом, иногда, размышлял над ним, но не смог найти противоречия, что он не будет работать как задуман. Итак. Создаем базу, в которой собраны все возможные расстановки всех возможных фигур на доске.
Создаем связи между расстановками, т.е. связь есть, если одну расстановку можно привести к другой с помошью одного
шахматного хода, иначе связи нет.
Делим связи на "ход черных" и "ход белых".
Проставляем очередность связей, приняв за первые связи все те, которые выходят из расстановки "начало шахматной партии" и удовлетворяют условию "ход белых".
В результате, если пройти по всем связям, с учетом очередности, чередуя условия "ход черных" и "ход белых" и начиная с расстановки "начало шахматной партии", то получим все возможные "партии".
Удаляем все следующие связи после связей, приводящие к концу игры, например, если при ходе одного цвета, королю другого цвета получается единственный ход — "под сруб" и он сам находится "под ударом". Трудновато придется с обработкой ничьи.
Начиная с конца партий, проставляем приорет на связи для черных и белых по принципу: если связь приводит к концу игры, то на неё ставится приоритет, равный 1, далее +1, на каждую предыдущую. Если проставляем приоритет на связь, на которой уже есть приоритет, то приоритеты суммируются.
Это построили базу ходов. Ходим с учетом приоритета — в ту сторону, где он меньше.
А если коротко, то просчитываем все возможные ходы заранее, а потом ходим по схеме. Всё.
Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей?
Спасибо за внимание.
Здравствуйте, Apostate, Вы писали:
A>А выкладки сколько вариантов существует и сколько тактов надо чтобы их просчитать и байтов чтобы со связями их разместить ты делал? A>Если делал и получились более менее реальные типа — все машины что есть в интернете по 2 года процессорного времени , то покажи здесь.
Прикидывал. Знаю что два раза дофига, а может и больше , но 64х-битный ключ у криптоалгоритма по началу тоже не могли сломать. А вот если откинуть эти технические детали, что тогда?
Здравствуйте, Real 3L0, Вы писали:
R3>Здравствуйте, Apostate, Вы писали:
A>>А выкладки сколько вариантов существует и сколько тактов надо чтобы их просчитать и байтов чтобы со связями их разместить ты делал? A>>Если делал и получились более менее реальные типа — все машины что есть в интернете по 2 года процессорного времени , то покажи здесь.
R3>Прикидывал. Знаю что два раза дофига, а может и больше , но 64х-битный ключ у криптоалгоритма по началу тоже не могли сломать. А вот если откинуть эти технические детали, что тогда?
я не в шутку просил привести выкладки... интересно.
Глядишь напишем скринсейвер, раздадим всем жилающим и через n-ое время будем знать алгоритм "белые начинают и как бы черные не рыпались выигрывают" или док-во что такого алгоритма не существует
Здравствуйте, Real 3L0, Вы писали:
R3>Прикидывал. Знаю что два раза дофига, а может и больше , но 64х-битный ключ у криптоалгоритма по началу тоже не могли сломать. А вот если откинуть эти технические детали, что тогда?
Тогда это бы выглядело так: садятся два гроссмонстера, подкидывают монетку (для определения, кто какими играет), пожимают друг другу руки и встают.
А технических деталей...
Если хранить каждую позицию без сжатия, то нужно 64 клетки * 19 состояний.
Верхняя планка количества позиций = 19^64 ~ 6*10^81 ~ 2^272.
Никаких дисков на это не хватит (пока что).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Real 3L0, Вы писали:
R3>>Прикидывал. Знаю что два раза дофига, а может и больше , но 64х-битный ключ у криптоалгоритма по началу тоже не могли сломать. А вот если откинуть эти технические детали, что тогда?
К>Тогда это бы выглядело так: садятся два гроссмонстера, подкидывают монетку (для определения, кто какими играет), пожимают друг другу руки и встают.
К>А технических деталей... К>Если хранить каждую позицию без сжатия, то нужно 64 клетки * 19 состояний. К>Верхняя планка количества позиций = 19^64 ~ 6*10^81 ~ 2^272. К>Никаких дисков на это не хватит (пока что).
Ну можно придумать моменты как сократить, например в из-за зеркальности и еще пешки не везде стоять, но врядли поможет — 19^64 это 82 значное число что вообще дофига — количество элетронов в этой галактике и то кажется меньше =).
Сомневаюсь что дисков всего интернета когда либо хватит.
Здравствуйте, Кодт, Вы писали:
К>А технических деталей... К>Если хранить каждую позицию без сжатия, то нужно 64 клетки * 19 состояний. К>Верхняя планка количества позиций = 19^64 ~ 6*10^81 ~ 2^272. К>Никаких дисков на это не хватит (пока что).
А для Го еще веселее — 3^(19*19), причем там верхняя планка ближе к реальности
Здравствуйте, Кодт, Вы писали:
К>Тогда это бы выглядело так: садятся два гроссмонстера, подкидывают монетку (для определения, кто какими играет), пожимают друг другу руки и встают.
Толку-то им играть? Ведь ясно же сразу, что ничья будет!
К>Если хранить каждую позицию без сжатия, то нужно 64 клетки * 19 состояний. К>Верхняя планка количества позиций = 19^64 ~ 6*10^81 ~ 2^272. К>Никаких дисков на это не хватит (пока что).
Ну, приблизительно, за 5 лет, ёмкость жестких дисков увеличилась в 4500 раз ...
Здравствуйте, Real 3L0, Вы писали:
К>>Если хранить каждую позицию без сжатия, то нужно 64 клетки * 19 состояний. К>>Верхняя планка количества позиций = 19^64 ~ 6*10^81 ~ 2^272. К>>Никаких дисков на это не хватит (пока что).
R3>Ну, приблизительно, за 5 лет, ёмкость жестких дисков увеличилась в 4500 раз ...
То есть на 3.5 десятичных порядка. А там их — 82.
Такими темпами мы успеем за 5*82/3.5 ~ 110-120 лет. Если сумеем к тому времени вовлечь все электроны вселенной в это бестолковое занятие.
Перекуём баги на фичи!
Re[6]: Как 82 порядка? 3^(19*19)=3^361 =~= 1.74 e172 (-)
Здравствуйте, Apostate, Вы писали:
К>> Если сумеем к тому времени вовлечь все электроны вселенной в это бестолковое занятие. A>Плюс сколько будут просчитыватся связи одного со всеми... A>И тогда наступит конец света.
В одном уединенном монастыре сидят монахи отшельники и непрерывно играют в шахматы.
Когда будут сыграны все возможные партии, наступит конец света.
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, Apostate, Вы писали:
К>>> Если сумеем к тому времени вовлечь все электроны вселенной в это бестолковое занятие. A>>Плюс сколько будут просчитыватся связи одного со всеми... A>>И тогда наступит конец света.
UgN>В одном уединенном монастыре сидят монахи отшельники и непрерывно играют в шахматы. UgN>Когда будут сыграны все возможные партии, наступит конец света.
Здравствуйте, Real 3L0, Вы писали:
R3>Здраствуйте. Когда-то давно придумал AI для шахмат. Потом, иногда, размышлял над ним, но не смог найти противоречия, что он не будет работать как задуман. Итак. R3>
Скипед... R3>R3>Это построили базу ходов. Ходим с учетом приоритета — в ту сторону, где он меньше.
R3>А если коротко, то просчитываем все возможные ходы заранее, а потом ходим по схеме. Всё.
Я тоже когда-то об этом мечтал . Этот алгоритм встречался мне в какой-то научно-фантастической книге, только для более простой игры. R3>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей?
Будет, если ответ действительно есть. Можно моделировать данный перебор для более простых игр
К сожалению, оценка времени и ресурсов для построение полного решения — ужасны. Возможно, ее можно уменьшить, модифицировав алгоритм.
Здравствуйте, King Oleg, Вы писали:
R3>А если коротко, то просчитываем все возможные ходы заранее, а потом ходим по схеме. Всё. KO>Я тоже когда-то об этом мечтал . Этот алгоритм встречался мне в какой-то научно-фантастической книге, только для более простой игры.
Ну всё, пойду я писать фантастику. Алгоритм я придумал сам. Честно.
R3>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? KO>Будет, если ответ действительно есть.
Это как? Дважды два равно четыре, если дважды два действительно равно четыре?
KO>Можно моделировать данный перебор для более простых игр KO>К сожалению, оценка времени и ресурсов для построение полного решения — ужасны. Возможно, ее можно уменьшить, модифицировав алгоритм.
Я тут ещё подумал. Как, по моему, сейчас работают сегодняшние шахматные алгоритмы: просчитывают на 1 шаг вперед — выбирают лучший, затем на два — опять выбирают лучший, ну и т.д. Затем ходят по лучшему ходу, забывая про остальные. Теперь о нашем: допустим, мы смогли построить базу расстановок и начинаем расставлять мощности на ходы с конца. Что нам мешает удалить из базы все расстановки и связи, которые вообще никогда не будут использоваться? Правда тут другой вопрос — будет ли их настолько много, что база уменьшится на много?
R3>Я тут ещё подумал. Как, по моему, сейчас работают сегодняшние шахматные алгоритмы: просчитывают на 1 шаг вперед — выбирают лучший, затем на два — опять выбирают лучший, ну и т.д. Затем ходят по лучшему ходу, забывая про остальные. Теперь о нашем: допустим, мы смогли построить базу расстановок и начинаем расставлять мощности на ходы с конца. Что нам мешает удалить из базы все расстановки и связи, которые вообще никогда не будут использоваться? Правда тут другой вопрос — будет ли их настолько много, что база уменьшится на много?
тогда программу можно будет сбить с толку, сделав нелогичный ход...
Здравствуйте, Real 3L0, Вы писали:
R3>Я тут ещё подумал. Как, по моему, сейчас работают сегодняшние шахматные алгоритмы: просчитывают на 1 шаг вперед — выбирают лучший, затем на два — опять выбирают лучший, ну и т.д. Затем ходят по лучшему ходу, забывая про остальные. Теперь о нашем: допустим, мы смогли построить базу расстановок и начинаем расставлять мощности на ходы с конца. Что нам мешает удалить из базы все расстановки и связи, которые вообще никогда не будут использоваться? Правда тут другой вопрос — будет ли их настолько много, что база уменьшится на много?
Программа не моя, но мне понравилась Особенно то, что в ней почти невозможно разобраться (во всяком случае мне).
/** Вот программа, занявшая первое место ("Best of Show") в этом году.
Она вызывается с необязательным числовым параметром (по умолчанию 2) и
играет в шахматы. Параметр определяет глубину просмотра (при глубине
большей, чем 3, она будет думать очень долго). Ходы задаются двумя
восьмеричными числами (откуда куда - см. доску в начале игры, например, "e2-e4"
нужно будет вводить как "64 44"), в приглашении к приему указывается
количество просмотренных ходов и оценка позиций - своей и противника, т.е.
Вас).
Правила игры несколько упрощены - пешки превращаются только в ферзей,
нет взятия на проходе и длинной рокировки (мне и короткую сделать не
удалось), а также контроля правил повторения позиций и 50
ходов.*/#include <stdio.h>
#include <stdlib.h>
#define m(x)(x<0?-1:!!x)
#define g tj()-J
#define a(x)(x<0?-x:x)
#define h(x)((x)<=K?x:N-(x))
#define f 9999
#define A return
#define H printf(
#define R double
#define U int
#define V for
#define b else
#define u while
#define B if
U v,w,Y= -1,W,J,p,F,o=f,M,N,K,X,YY,_,P[f],s();
typedef U(*L)(); L q[f];
tj()
{
U S=m(v)+(m(w)<<K);
B(!S)A J;
V(v=W+S;v!=J&&!q[v]; v+=S);
A v;
}
k()
{
_=K;
A v?a(v)>1||w-Y||!q[J]:(w-Y&&(w-Y*2||q[W+Y*(N+1)] || (J>>K)-K+(Y-1)/ 2))||q[J];
}
z()
{
_=5;
A v*w||g;
}
e(){
_= -2;
A (v*v*v-v||w*w*w-w)&&(J-W-2||(W&N)-4||(W>>K!=(Y-1?N:0))||
q[W+1]||q[W+2]||q[W+K]!=z||P[W+K]*Y<0);
}
R VR()
{
int PZ=0x7fff;
A (R)(rand()&PZ)/(R)PZ;
}
l()
{
_=K+1;
A(v*w&&a(v)-a(w))||g;
}
R UC()
{
R i=0,d;
u((i+=d=VR())<1.0);
A d;
}
c()
{
_= -11;
A a(v)-a(w)||g;
}
I(ur,n,x)
{
W=ur;
J=n;
B(P[W]!=Y||P[J]==Y)A J+1;
v=(J&N)-(W&N);
w=(J>>K)-(W>>K);
A q[W]()||(x&&QL(W,J,s));
}
TT(W)
{
v=w=0;
A q[W]()+K;
}
s()
{
U j= -1,i;
Y= -Y;
V(i=0; i<M; ++i)
{
B(j<0&&P[i]== -Y&&TT(i)&&_== -2)
{
j=i;
i= -1;
}
b B(j>=0&&!I(i,j,0))A
Y= -Y;
}
A!(Y= -Y);
}
bb()
{
_=1;
A a(v*w)-2;
}
uv()
{
V(v=0; v<f; ++v)
{
B(h(v>>K)==0)
{
U S=h(v&N);
q[v]=!S?z:(S==1?bb:(S==2?c:(v&N>K?l:e)));
}
b B(h(v>>K)==1)
q[v]=k;
b q[v]=0;
P[v]=!!q[v]*(28-v);
}
}
y()
{
U G=Y,i;
J=0;
V(i=0; i<M; ++i)
{
i%8||H"\n%4o ",i);
B((Y=P[i]=m(P[i]))&& TT(i))H"%c ",_+93+Y*16); b H"- ");
}
H"\n ");
do H"%2d",i++&N);
u(i&N);
Y=G;
H"\n");
}
O(W,J)
{
B((q[J]=q[W])==k&&h(J>>K)==0) q[J]=l;
B(q[W]==e)B(J-W==2)O(J+1,J-1);
b B(W-J==2)O(W-1,W+1);
P[J]=P[W];
q[W]=0;
P[W]=0;
}
QL(W,J,D)L D;
{
U HQ=P[J],YX;
L AJ=q[J],XY=q[W];
O(W,J);
YX=D();
O(J,W);
q[J]=AJ;
q[W]=XY;
P[J]=HQ;
A YX;
}
C()
{
U i,j,BZ=0;
V(i=0; i<M; ++i)
{
L Z=q[i];
B(Z)
{
U r=h(i>>K)+h(i&N),G=Y, S=Z==z?88:(Z==k?11 +r+(P[i]<0?N-(i>>K):(i>>K)):
(Z==l?124-((YY<8&&((i&N)!=K|| (i>>K)!=(P[i]>0?0:N)))?M:0):
(Z==c?41+r:(Z==e?f-r-r:36+r+r))));
Y=P[i];
V(j=0; j<M; ++j)
B(!I(i,j,0))
S+=(P[j]?5:1);
BZ+=G==Y?S:-S; Y=G;
}
}
B(!(++X&M-1))
write(1,".",1);
A BZ;
}
PX(){
U i,Q=0,XP=0,JZ=M*M,E= -f,t,S=o;
B(!F--)
A++F+C();
V(i=0; i<JZ; ++i)
B(!I(i>>K+K,i&M-1,1))
{
Y= -Y;
o= -E;
t=-QL(i>>K+K,i&M-1,PX);
Y= -Y;
B(t>E)
{
++XP;
Q=i;
E=t;
B(E>=S)
A++F,E;
}
}
B(!XP)
E=s()?-f+1:0;
p=Q;
A++F,E;
}
RZ(){
U i,j,T=0;
V(; ; ){
y();
o=f;
do{
H"\n%d %d %d %s ",X,T,C(),s()?"!":">");
fflush(stdout);
}
u(scanf("%o%o",&i,&j)!=2||I(i,j,1));
O(i,j);
y();
X=0;
++YY;
Y= -Y;
T=PX();
i=p>>(K<<1);
j=p&(M-1);
B(I(i,j,1))
{
H"Rats!\n");
A;
}
O(i,j);
Y= -Y;
B(T>M*M)
H"\nHar har.\n");
}
}
main(ac,av)char**av;
{
long time(),j=time(&j);
R i=0;
srand((U)j);
V(M=0; M<=f; ++M)
i+=UC();
M=i/100;
B(M&3)
++M;
B(M&1)
--M;
V(N=1; N*N<M; ++N);
K= --N/2;
F=ac>1?atoi(av[1]):2;
uv();
RZ();
}
Здравствуйте, Real 3L0, Вы писали:
R3>Я тут ещё подумал. Как, по моему, сейчас работают сегодняшние шахматные алгоритмы: просчитывают на 1 шаг вперед — выбирают лучший, затем на два — опять выбирают лучший, ну и т.д. Затем ходят по лучшему ходу, забывая про остальные. Теперь о нашем: допустим, мы смогли построить базу расстановок и начинаем расставлять мощности на ходы с конца. Что нам мешает удалить из базы все расстановки и связи, которые вообще никогда не будут использоваться? Правда тут другой вопрос — будет ли их настолько много, что база уменьшится на много?
То, что ты описал — называется альфа-бета-отсечением.
Это не самый эффективный алгоритм, какой можно представить: он обшаривает варианты ходов в ширину, совершая много лишних телодвижений.
Не знаю, как устроены современные хорошие программы, но в свое время читал книгу М.Ботвинника о его программе "Каисса".
Там в основу был поставлен алгоритм постановки целей (то есть рассматривается набор осмысленных задач и способы их достижения).
Вполне возможно, что современные программы делают нечто подобное, плюс база сыгранных партий, плюс база типичных концовок.
К>Не знаю, как устроены современные хорошие программы, но в свое время читал книгу М.Ботвинника о его программе "Каисса". К>Там в основу был поставлен алгоритм постановки целей (то есть рассматривается набор осмысленных задач и способы их достижения).
Ботвинник М. Алгоритм игры в шахматы. Тираж 25.000 экз. М. Наука 1968г. 96 с. Ботвинник М. М. О кибернетической цели игры. М.: Сов. радио. 1976г.
-- именно ее я и читал. Возможно, даже валяется где-то дома.
В инете книга не опубликована. (Я не обнаружил, во всяком случае).
Здравствуйте, Real 3L0, Вы писали:
R3>Ну, приблизительно, за 5 лет, ёмкость жестких дисков увеличилась в 4500 раз ...
Это где так, у тебя в компьютере?
Сейчас максимальный размер диска, который можно просто купить в магазине по разумной цене — 120-200GB. Пять лет назад (1998 год) это было что-то около 10-20GB. Итого 10-12 раз. Если бы это было 4500 раз, то максимальный размер диска, доступный в 1998 году, был бы 25-45MB. Персоналки с такими дисками массово поставлялись примерно так в 1988 году (15 лет назад, а не 5).
Здравствуйте, Vadim B, Вы писали:
VB>Это где так, у тебя в компьютере?
Нет, судил по всяким высказываниям из разных источников, например, "максимальный размер диска, доступный в 1998 году, был бы 25-45MB" (извините, за копирование)
VB>Сейчас максимальный размер диска, который можно просто купить в магазине по разумной цене — 120-200GB. Пять лет назад (1998 год) это было что-то около 10-20GB. Итого 10-12 раз. Если бы это было 4500 раз, то максимальный размер диска, доступный в 1998 году, был бы 25-45MB. Персоналки с такими дисками массово поставлялись примерно так в 1988 году (15 лет назад, а не 5).
Вполне возможно, не буду спорить. Мои данные касаются только российских (советских) пользователей.
Здравствуйте, Real 3L0, Вы писали:
VB>>Это где так, у тебя в компьютере?
R3>Нет, судил по всяким высказываниям из разных источников, например, "максимальный размер диска, доступный в 1998 году, был бы 25-45MB" (извините, за копирование)
VB>>Сейчас максимальный размер диска, который можно просто купить в магазине по разумной цене — 120-200GB. Пять лет назад (1998 год) это было что-то около 10-20GB. Итого 10-12 раз. Если бы это было 4500 раз, то максимальный размер диска, доступный в 1998 году, был бы 25-45MB. Персоналки с такими дисками массово поставлялись примерно так в 1988 году (15 лет назад, а не 5).
R3>Вполне возможно, не буду спорить. Мои данные касаются только российских (советских) пользователей.
Вот как раз у советских пользователей в 1988-89 году массово шли винты на 20-40 MB. Ну, скажем, в провинции было обычно 20, а 40 считалось барством, а в столицах уже 40 у многих было. Я, конечно, понимаю, что 1988 год сейчас уже выглядит как доисторическая эра, но тут есть люди, которые его еще хорошо помнят
Здравствуйте, Кодт, Вы писали:
R3>Ну, приблизительно, за 5 лет, ёмкость жестких дисков увеличилась в 4500 раз ... К>То есть на 3.5 десятичных порядка. А там их — 82. К>Такими темпами мы успеем за 5*82/3.5 ~ 110-120 лет. Если сумеем к тому времени вовлечь все электроны вселенной в это бестолковое занятие.
Ну, на счет бестолковости, посмотри какой ажиотаж, какие бабки крутятся вокруг соревнования машины и человека!
Здравствуйте, Real 3L0, Вы писали:
R3>Создаем базу, в которой собраны все возможные расстановки всех возможных фигур на доске.Создаем связи между расстановками, т.е. связь есть, если одну расстановку можно привести к другой с помошью одного шахматного хода, иначе связи нет.Делим связи на "ход черных" и "ход белых".
Ok. Возможно лучше очередность хода привешивать к позиции, тогда получаем просто ориентированный граф. R3>Проставляем очередность связей, приняв за первые связи все те, которые выходят из расстановки "начало шахматной партии" и удовлетворяют условию "ход белых".
Не совсем ясно, что значит очередность связи? Во первых, в одну и ту же позицию можно придти разными путями. Во вторых, в разных партиях могут возникать одинаковые позиции, но в разном порядке. R3>В результате, если пройти по всем связям, с учетом очередности, чередуя условия "ход черных" и "ход белых" и начиная с расстановки "начало шахматной партии", то получим все возможные "партии".
Опять таки, причем здесь какая-то очередность? Нужно ходить только по ребрам графа. Кстати при этом мы можем зациклиться и придется вовлекать дополнительные правила (троекратное повторение позиции/ходы без "съедений" и ходов пешками)... Вот теперь действительно все партии. R3>Удаляем все следующие связи после связей, приводящие к концу игры, например, если при ходе одного цвета, королю другого цвета получается единственный ход — "под сруб" и он сам находится "под ударом". Трудновато придется с обработкой ничьи.
(уточнение) Связь можно удалить
1. если ее начало непосредственно в финальной позиции (кому-то мат)
2. если в ее начало можно попасть только через уже удаленные связи.
3. возможно образовавшиеся связные куски, в которые уже нельзя попасть из исходной позиции (с учетом того, что какие-то связи удалили) R3>Начиная с конца партий, проставляем приорет на связи для черных и белых по принципу: если связь приводит к концу игры, то на неё ставится приоритет, равный 1, далее +1, на каждую предыдущую. Если проставляем приоритет на связь, на которой уже есть приоритет, то приоритеты суммируются. Представь, что мы, выйдя из позиции, попали опять в нее же. Так можно накрутить до бесконечности. R3>
настоящая проблема это сам алгоритм — под него нужно строить СУПЕР-ЭВМ, да-да именно все буквы большие, в которой для хранения этого графа будут задействованы все электроны вселенной,... представляешь себе такую?
Здравствуйте, Apostate, Вы писали:
A> это доработки, корректировка багов по мелочи...
A>настоящая проблема это сам алгоритм — под него нужно строить СУПЕР-ЭВМ, да-да именно все буквы большие, в которой для хранения этого графа будут задействованы все электроны вселенной,... представляешь себе такую?
Согласен, что электронов может и не хватить.
Но мне кажется, что есть проблемы с распутыванием партий с конца на уровне самой идеи.
Поэтому не будет смысла строить эту СУПЕР-ПУПЕР-ЭВМ
Не совсем точная цитата, может кто поправит.
Механитис --- болезнь ...(не помню кого), считающих, что любую проблему, даже если они не могут ее формализовать, можно будет решить, если заполучить достаточно мощную ЭВМ.
«Механитис – профессиональное заболевание тех, кто верит, что ответ математической задачи, которую он не может ни решить, ни даже сформулировать, легко будет найти, если получить доступ к достаточно дорогой вычислительной машине».
KA>Механитис --- болезнь ...(не помню кого), считающих, что любую проблему, даже если они не могут ее формализовать, можно будет решить, если заполучить достаточно мощную ЭВМ.
Программистов?
Заказчиков?
ЗЫ. А название точное?, а то больно термин хороший —
"Э, товарищ, да у вас механитис. Вам нужен покой, а ТЗ мы без вас составим, вы не беспокойтесь ".
R3>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? R3>Спасибо за внимание.
Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать). А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, KonstantinA, Вы писали:
KA> Представь, что мы, выйдя из позиции, попали опять в нее же. Так можно накрутить до бесконечности.
Согласно современным шахматным правилам, такого быть не может, ибо полная информация о шахматной позиции кроме расположения фигур включает еще признаки для каждого короля и ладьи, о том, двигались они или нет, а также признак возможности взятия на проходе для пешек и счетчик количества повторений этой позиции в партии.
Здравствуйте, fAX, Вы писали:
R3>>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? R3>>Спасибо за внимание.
fAX>Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать).
"Антагонистическая игра с полной информацией"
fAX>А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
Нет.
Бывают такие игры вообще без ничьей, например то же Го или Ним.
Здравствуйте, Les, Вы писали:
Les>Здравствуйте, fAX, Вы писали:
R3>>>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей? R3>>>Спасибо за внимание.
fAX>>Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать).
Les>"Антагонистическая игра с полной информацией"
Я нашёл также перевод: "игрa с нулевой суммой", но Ваше определение мне нравится больше.
fAX>>А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
Les>Нет. Les>Бывают такие игры вообще без ничьей, например то же Го или Ним.
Хорошо, сформулируем так: первый ход в такой игре не даёт решающего преимущества, т.к. у противоположной стороны всегда есть адекватный ответ
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
Les>>Бывают такие игры вообще без ничьей, например то же Го или Ним. fAX>Хорошо, сформулируем так: первый ход в такой игре не даёт решающего преимущества, т.к. у противоположной стороны всегда есть адекватный ответ
Не простой вопрос. Обычно первый ход дает преимущество. В Го это решается за счет "коми" — платы в 5.5 очков которую платит первый игрок. В ниме же, победа при идеальной игре определяется начальными условиями, причем чаще победа достается первому.
Рассмотрим упрощенный вариант нима из "форта Байар" — кучка палочек, из которой игроки вытаскивают поочередно две или одну палочки по своему усмотрению, надо забрать последнюю. Выигрышная стратегия — оставлять после себя 3к палочек. Это можно сделать только если вы не получили эти самые 3к на входе. Если же 3к получает ваш противник, вам достаточно вытянуть 3 минус х, где х — количество вытянутых противником.
Если игру начинаете вы, то в зависимости от начального количества палочек, ваши шансы выиграть в идеальной игре приблизительно 2 к 1.
Здравствуйте, Les, Вы писали:
Les>>>Бывают такие игры вообще без ничьей, например то же Го или Ним. fAX>>Хорошо, сформулируем так: первый ход в такой игре не даёт решающего преимущества, т.к. у противоположной стороны всегда есть адекватный ответ
Les>Не простой вопрос. Обычно первый ход дает преимущество. В Го это решается за счет "коми" — платы в 5.5 очков которую платит первый игрок.
Извините, в го я не силён, только в рамках некогда взятого курса по AI . Но ведь заключение о преимуществе первого хода чисто математическое, и даже в изначально неравных условиях можно ввести дополнительные условия, которые нивелируют это преимущество, как Вы продемонстрировали на примере го.
А шахматы... Шахматы хорошая игра !!! Даже если докажут, что у белых или чёрных есть то самое преимущество, то вряд ли его найдут завтра (если, конечно, его ещё нет у автора темы ). Ну... или введут новое правило...
В ниме же, победа при идеальной игре определяется начальными условиями, причем чаще победа достается первому.
Les>Рассмотрим упрощенный вариант нима из "форта Байар" — кучка палочек, из которой игроки вытаскивают поочередно две или одну палочки по своему усмотрению, надо забрать последнюю. Выигрышная стратегия — оставлять после себя 3к палочек. Это можно сделать только если вы не получили эти самые 3к на входе. Если же 3к получает ваш противник, вам достаточно вытянуть 3 минус х, где х — количество вытянутых противником.
Les>Если игру начинаете вы, то в зависимости от начального количества палочек, ваши шансы выиграть в идеальной игре приблизительно 2 к 1.
Да, это так, но каким образом тогда Ним относится к "антагонистичным играм"?!
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
fAX>А шахматы... Шахматы хорошая игра !!! Даже если докажут, что у белых или чёрных есть то самое преимущество, то вряд ли его найдут завтра (если, конечно, его ещё нет у автора темы ). Ну... или введут новое правило...
Здравствуйте, KonstantinA, Вы писали:
R3>Создаем базу... R3>Проставляем очередность связей, приняв за первые связи все те, которые выходят из расстановки "начало шахматной партии" и удовлетворяют условию "ход белых". KA>Не совсем ясно, что значит очередность связи? Во первых, в одну и ту же позицию можно придти разными путями. Во вторых, в разных партиях могут возникать одинаковые позиции, но в разном порядке.
Вы сами и ответили на сой вопрос. По простому "очередность связи" == "очередность хода". Это надо для выбора в какую сторону, какими фигурами идти, в зависимости от того, в какую сторону, какими фигурами были предыдущие ходы. Напомню, что (теоретически) мы имеем все расстановки шахматных фигур на доске => ситуации "в одну и ту же позицию можно придти разными путями" будут обязательно.
R3>В результате, если пройти по всем связям, с учетом очередности, чередуя условия "ход черных" и "ход белых" и начиная с расстановки "начало шахматной партии", то получим все возможные "партии". KA>Опять таки, причем здесь какая-то очередность? Нужно ходить только по ребрам графа. Кстати при этом мы можем зациклиться и придется вовлекать дополнительные правила (троекратное повторение позиции/ходы без "съедений" и ходов пешками)... Вот теперь действительно все партии.
В этом нам связи и помогут, а именно, одно из указанных мной свойств связей — очередность. В конечном варианте, на связи придется вешать очень много свойств, например, как писал m.a.g., "признаки для каждого короля и ладьи, о том, двигались они или нет, а также признак возможности взятия на проходе для пешек и счетчик количества повторений этой позиции в партии"
R3>Удаляем... R3>Начиная с конца партий, проставляем приорет на связи для черных и белых... KA> Представь, что мы, выйдя из позиции, попали опять в нее же. Так можно накрутить до бесконечности.
Представить можно, но накрутить до бесконечности, согласно текущим шахматным правилам, не представляется возможным. Ещё раз: у нас в связях заложена вся информация о том, какую именно часть, какого именно множества партий мы сыграли, а для дальнейшего хода видим все будущие разветвления партий. R3>
Здравствуйте, fAX, Вы писали:
fAX>Предполагается, что шахматы — это zero-sum game with perfect information (извините, по-русски не знаю, как правильно сказать).
"Игра с нулевой суммой и полной информацией".
fAX>А посему должна заканчиваться ничьёй. Доказано ли это, не помню, но, по-моему, да. Ещё раз, "по-моему, да"....
Из одного другое не следует.
1) Игры, в которых ничья не предусмотрена.
Пример: игра Баши (кажется, так?) — имеется кучка из K камней, за один ход можно взять любое количество от 1 до N. Выигрывает(проигрывает) тот, кто возьмет последний камень.
. Выигрывает первый.
При желании можно выдумать игру, в которой выиграет второй. Например, зафиксировать начальную позицию в шахматах, из которой "белые начинают и получают мат в 2 хода".
---
Примечание: игра Ним — это расширение игры Баши на несколько кучек (за один ход можно тащить из одной кучки).
К>При желании можно выдумать игру, в которой выиграет второй. Например, зафиксировать начальную позицию в шахматах, из которой "белые начинают и получают мат в 2 хода".
есть такая позиция, называется задача Алехина.
смысл такой, при начальной расстановке фигур белые делают роковой неправильный первый ход, и после этого гарантировано получают мат в 4 хода. подробности завтра расскажу, откопаю вырезку
Здравствуйте, Real 3L0, Вы писали:
R3>Итак, вопрос: будет ли этот алгоритм всегда приводить к выигрышу или ничьей?
Поздравляю. Лет тридцать пять назад так исследовали эндшпили "ладья с пешкой против ладьи" и "ферзь с пешкой против ферзя". На сегодня самая известная реализация этого алгоритма сделана сибиряком Евгением Налимовым, после этого перешедшим на работу в MS. Исходники доступны и входят сейчас в каждую серьезную шахматную программу. Таблицы занимают мегов тридцать для четырехфигурных эндшпилей (3+1 и 2+2, включая королей) и шесть гигов для пятифигурных (только 3+2, потому что 4+1 слишком просты). Таблица для какого-нибудь одного 3+2, например, ферзь с пешкой против ферзя, считается три дня на pii-350/512. Для шестифигурных на ftp://ftp.cis.uab.edu/pub/hyatt/ (сейчас почему-то недоступен) уже посчитали 3+3 без пешек — сотня-две гигов. Дальше пока не берутся
Здравствуйте, mogadanez, Вы писали:
M>есть такая позиция, называется задача Алехина. M>смысл такой, при начальной расстановке фигур белые делают роковой неправильный первый ход, и после этого гарантировано получают мат в 4 хода. подробности завтра расскажу, откопаю вырезку
Так называемый детский мат (какая замечательная идиома ).
(c) Вячеслав Шилов.
Здравствуйте, desperado_gmbh, Вы писали:
_>... Таблица для какого-нибудь одного 3+2, например, ферзь с пешкой против ферзя, считается три дня на pii-350/512. ...
Здравствуйте, Real 3L0, Вы писали:
R3>Здравствуйте, fAX, Вы писали:
fAX>>А шахматы... Шахматы хорошая игра !!! Даже если докажут, что у белых или чёрных есть то самое преимущество, то вряд ли его найдут завтра (если, конечно, его ещё нет у автора темы ). Ну... или введут новое правило...
R3>Нету ещё. Подожду прихода квантовых компьютеров.
Здравствуйте, KonstantinA, Вы писали:
KA>>Не совсем точная цитата, может кто поправит.
KA>Вот как все было...
KA>«Механитис – профессиональное заболевание тех, кто верит, что ответ математической задачи, которую он не может ни решить, ни даже сформулировать, легко будет найти, если получить доступ к достаточно дорогой вычислительной машине».
KA>Б. Купман, Исследование операций, 4, 442 (1956).
Здравствуйте, folk, Вы писали:
KA>«Механитис – профессиональное заболевание тех, кто верит, что ответ математической задачи, которую он не может ни решить, ни даже сформулировать, легко будет найти, если получить доступ к достаточно дорогой вычислительной машине».
F>А кто знает на какой слог ударение?
... << RSDN@Home 1.0 beta 7a >>
Вселенная бесконечна как вширь, так и вглубь.
Re[8]: Как 82 порядка? 3^(19*19)=3^361 =~= 1.74 e172 (-)
Здравствуйте, Apostate, Вы писали:
Les>>>>3^(19*19)
A>точно 172, опечатался наверно когда на калькуляторе считал — как теперь и сам не пойму)
Ты не на калькуле опечатался, вот тебе без учета повторов пешек и свойств фигур(а свойств ой как много:типа слоны одного цвета на разных цветах и т.п.)
int i,j;
double Result = 0;
for(j = 1;j < 32; j++){
double Res = 1;
for(i = 1;i <= j; i++) Res *= (64 — i)*(32 — i);
Result += Res;
}
где-то 6^100
Относительная ошибка у тя примерно 10^260
Re[9]: Как 82 порядка? 3^(19*19)=3^361 =~= 1.74 e172 (-)
, то покажи здесь.
Перекуём баги на фичи!
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
это доработки, корректировка багов по мелочи...
