Здраствуйте. Когда-то давно придумал 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 шаг вперед — выбирают лучший, затем на два — опять выбирают лучший, ну и т.д. Затем ходят по лучшему ходу, забывая про остальные. Теперь о нашем: допустим, мы смогли построить базу расстановок и начинаем расставлять мощности на ходы с конца. Что нам мешает удалить из базы все расстановки и связи, которые вообще никогда не будут использоваться? Правда тут другой вопрос — будет ли их настолько много, что база уменьшится на много?
То, что ты описал — называется альфа-бета-отсечением.
Это не самый эффективный алгоритм, какой можно представить: он обшаривает варианты ходов в ширину, совершая много лишних телодвижений.
Не знаю, как устроены современные хорошие программы, но в свое время читал книгу М.Ботвинника о его программе "Каисса".
Там в основу был поставлен алгоритм постановки целей (то есть рассматривается набор осмысленных задач и способы их достижения).
Вполне возможно, что современные программы делают нечто подобное, плюс база сыгранных партий, плюс база типичных концовок.
, то покажи здесь.
Перекуём баги на фичи!
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
