:: Игры Разума
Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Здравствуйте!

Новая серия - алгоритмы и соответствующие программы.
На форуме рассматриваются в основном проблемы, связанные с базами данных. Да, Фокс был задуман как язык СУБД. И потому в его ранних версиях не было даже оператора цикла ФОР ... НЕКСТ и кое-чего еще... Но сейчас он полноценный язык высокого уровня. И его смело можно привлекать для других целей.

Итак, задача 1. Игра "Квадратобоязнь"

Эту игру предложил известный американский популяризатор науки Мартин Гарднер в своей книге "Математические игры и развлечения".
Игра ведется на доске размером nхn, содержащей n^2 полей (рис 1). Играют двое. Один игрок имеет фишки белого, другой – чёрного цветов. Ходят по очереди, и ход игрока заключается в том, что он помещает свою фишку на одно из свободных полей доски. Проигрывает тот, у кого после очередного хода какие-либо свои четыре фишки окажутся расположенными в вершинах одного из возможных на доске квадратов.

[attachment 4729 .JPG]

Квадраты могут быть любого размера и наклонены под любыми (фиксированными!) углами. На рис. 1 выделены вершины трёх таких квадратов. Введём систему координат, как показано на рис.1. Тогда можно обозначить каждое поле двузначным числом, первая цифра которого покажет ряд, а вторая цифра – место в этом ряду, занимаемое фишкой. Например, самая верхняя чёрная фишка имеет координату 73, а самая нижняя чёрная фишка – 15.
Выписав рядом координаты всех четырёх вершин квадрата, получим восьмизначный код квадрата. Например, верхний квадрат из белых фишек будет иметь обозначение 46546775, нижний белый – 12132223, а большой чёрный квадрат – 15315773. Гарднер приводит формулу, дающую число квадратов на доске размером nхn :

N = (n^4-n^2)/12

Эта игра, порождает много алгоритмических проблем, связанных с поиском квадратов. Вот некоторые из них:

Составить алгоритм и программу на фоксе для составления каталога квадратов, существующих на доске размером 7х7. По формуле их будет 196 штук.

Первый квадрат таков 11122122, ..... Последний 11177177.

Мне пришлось задействовать 4 вложенных цикла. Кто сможет сделать проще?


------------------




Исправлено 1 раз(а). Последнее : Joys, 01.07.07 00:08
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
А простота оценивается по количеству вложенных циклов? Тогда можно вообще без циклов написать, только код будет очень длинный. А с одним циклом - без проблем, только вряд ли это оптимально с точки зрения скорости.
local ar1(4), arx(4), ary(4)
create cursor tmp (kv C(8))
for i=0 to 7^8-1
if i%100=0
wait window allt(str(i))+"/"+allt(str(7^8-1)) nowait
endif
j=i
ar1(1)=j%49
j=int(j/49)
ar1(2)=j%49
j=int(j/49)
ar1(3)=j%49
j=int(j/49)
ar1(4)=j%49
asort(ar1)
if ar1(1)=ar1(2) or ar1(2)=ar1(3) or ar1(3)=ar1(4)
loop
endif
if (ar1(3)%7)>(ar1(2)%7)
m.t=ar1(3)
ar1(3)=ar1(2)
ar1(2)=m.t
endif
arx(1)=ar1(1)%7
ary(1)=int(ar1(1)/7)
arx(2)=ar1(2)%7
ary(2)=int(ar1(2)/7)
arx(4)=ar1(3)%7
ary(4)=int(ar1(3)/7)
arx(3)=ar1(4)%7
ary(3)=int(ar1(4)/7)
if ary(3)-ary(2)=arx(2)-arx(1) ;
and arx(2)-arx(3)=ary(2)-ary(1) ;
and ary(4)-ary(3)=arx(3)-arx(2) ;
and arx(3)-arx(4)=ary(3)-ary(2)
insert into tmp values (str(arx(1)+1,1,0)+ ;
str(ary(1)+1,1,0)+ ;
str(arx(2)+1,1,0)+ ;
str(ary(2)+1,1,0)+ ;
str(arx(3)+1,1,0)+ ;
str(ary(3)+1,1,0)+ ;
str(arx(4)+1,1,0)+ ;
str(ary(4)+1,1,0))
endif
next
wait clear
select distinct kv from tmp order by 1 into cursor kvadr
browse
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
matod

Сообщений: 3062
Откуда: Иркутск
Дата регистрации: 31.10.2001
Обычно подобные задачи решаются по принципу "порождение и проверка". Т.е. алгоритм перебирает все возможные состояния и проверяет, являются ли они решениями. Интересен другой подход - сразу генерировать решения. Это не всегда эффективнее и не всегда возможно (например, для бесконечного числа состояний), но наверное стоит попробовать.
Если для данной задачи найти способ последовательного порождения решений, то алгоритм может оказаться эффективнее, поскольку любой переборный алгоритм потребует перебора порядка n^8 вариантов, в то время как порождающий потребует порядка n^4 (в соответствии с формулой из постановки задачи) итераций.
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет всем!

Матод прав.

matod
Обычно подобные задачи решаются по принципу "порождение и проверка". Т.е. алгоритм перебирает все возможные состояния и проверяет, являются ли они решениями.
Если для данной задачи найти способ последовательного порождения решений, то алгоритм может оказаться эффективнее

Вот алгоритм , в котором реализован способ выбора вариантов: Менее 1 секунды на 196 квалратов.

** Cоставление каталога квадратов на доске размером mxn (7x7)
SET SAFETY OFF
CREATE TABLE katalog (nomer n(5), pole n(8))
USE katalog
M=7
N=7
K=0
I=1
DO WHILE I<=M
J=1
A1=1
A2=M-I
DO WHILE J<=N
B1=1-J
B2=0
DI=A1
DO WHILE DI<=A2
DJ=B1
DO WHILE DJ<=B2
O=I+DI
P=J+DJ
Q=O-DJ
R=P+DI
S=Q-DI
T=R-DJ
IF NOT (Q>M OR T>N OR R>N OR S>M )
nkvadr= ((((((I*10+J)*10+O)*10+P)*10+Q)*10+R)*10+S)*10+T && числовой тип
ckvadr=ALLTRIM(STR(I))+ALLTRIM(STR(J))+ALLTRIM(STR(O))+ALLTRIM(STR(P));
+ALLTRIM(STR(Q))+ALLTRIM(STR(R))+ALLTRIM(STR(S))+ALLTRIM(STR(T)) && символьный
K=K+1
? ckvadr
APPEND BLANK
replace nomer WITH K && recno()
REPLACE pole WITH nkvadr
ENDIF
DJ=DJ+1
ENDDO
DI=DI+1
ENDDO
J=J+1
ENDDO
I=I+1
ENDDO

? "Всего ", k , " квадратов."
BROWSE
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет всем!

Итак, каталог составлен. Восьмизначные коды полей можно загнать в массив, а можно ив таблицу. Я выбрал второе. Нижеследующие коды полей:

11212212 11313313 11414414 11515515 11616616 11717717 12213223 12222313 12314324 12323414 12415425 12424515 12516526 12525616 12617627 12626717 13214234 13223324 13232414 13315335 13324425 13333515 13416436 13425526 13434616 13517537 13526627 13535717 14215245 14224335 14233425 14242515 14316346 14325436 14334526 14343616 14417447 14426537 14435627 14444717 15216256 15225346 15234436 15243526 15252616 15317357 15326447 15335537 15344627 15353717 16217267 16226357 16235447 16244537 16253627 16262717 21313222 21414323 21515424 21616525 21717626 22314233 22323323 22415334 22424424 22516435 22525525 22617536 22626626 22727727 23315244 23324334 23333424 23416345 23425435 23434525 23517446 23526536 23535626 23627637 23636727 24316255 24325345 24334435 24343525 24417356 24426446 24435536 24444626 24527547 24536637 24545727 25317266 25326356 25335446 25344536 25353626 25427457 25436547 25445637 25454727 26327367 26336457 26345547 26354637 26363727 31414232 31515333 31616434 31717535 32415243 32424333 32516344 32525434 32617445 32626535 32727636 33416254 33425344 33434434 33517355 33526445 33535535 33627546 33636636 33737737 34417265 34426355 34435445 34444535 34527456 34536546 34545636 34637647 34646737 35427366 35436456 35445546 35454636 35537557 35546647 35555737 36437467 36446557 36455647 36464737 41515242 41616343 41717444 42516253 42525343 42617354 42626444 42727545 43517264 43526354 43535444 43627455 43636545 43737646 44527365 44536455 44545545 44637556 44646646 44747747 45537466 45546556 45555646 45647657 45656747 46547567 46556657 46565747 51616252 51717353 52617263 52626353 52727454 53627364 53636454 53737555 54637465 54646555 54747656 55647566 55656656 55757757 56657667 56666757 61717262 62727363 63737464 64747565 65757666 66767767 ,

а их всего 196 штук, заполнены в таблицу katalog (nomer n(5), pole n(8))
В дальнейшем при разработке алгоритма игры возникает необходимость
поиска квадратов с вершиной в заданном поле. Ведь прежде чем поставить свою фишку на какое-то поле доски , игрок должен выяснить заранее какая ситуация может сложиться во всех квадратах, для которых это поле является вершиной. И тогда для организации поиска придется каждый элемент массива расщеплять на вершины (4 двузначных числа). Например, первый элемент каталога 11212212 надо будет разбить на 11, 21, 12 и 22.
Вопросы:

1) Удобно ли программировать это расщепление , когда элемент каталога имеет числовой тип (нумерик), а может стоит заполнять каталог символьными данными, т.е. стоит создать таблицу katalog (nomer n(5), pole с(8))?
2) Как расщепить элемент каталога на коды вершин а) для числового случая б) для символьного варианта? Коды пожалуйста-так сказал Фокстрот.
3) Как склеить вновь расщепленные вершины в порядке упорядочения вершин по возрастанию, например для первого элемента 11122122, ведь очевидно, что программировать упорядоченные масивы легче.
4) Можно ли пункт 3 выполнить одним или двумя селектами?

Чего-то Фокстрота давно не видно. Это он ратовал вернуться в лоно программирования, и мы прислушались к его мудрому совету!

Удачи!
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
mayil
Вот алгоритм , в котором реализован способ выбора вариантов: Менее 1 секунды на 196 квалратов.
Тогда уж лучше так (у меня получилось 0.022 сек)
close data all
m.sc=seconds()
m.xdim=7
m.ydim=7
create cursor xcoor (x I)
create cursor ycoor (y I)
for i=1 to m.xdim
insert into xcoor values (i)
next
for i=1 to m.ydim
insert into ycoor values (i)
next
select x,y from xcoor, ycoor into cursor xycoor
select xy1.x as x1, xy1.y as y1, xy2.x as x2, xy2.y as y2 ;
from xycoor xy1 join xycoor xy2 on xy1.x<xy2.x and xy1.y<=xy2.y ;
into cursor ver12
select x1, y1, x2, y2, x2+y1-y2 as x3, y2+x2-x1 as y3, ;
x1+y1-y2 as x4, y1+x2-x1 as y4 ;
from ver12 where x1+y1-y2>0 and y2+x2-x1<=m.ydim ;
into cursor ver1234
select str(x1,1,0)+str(y1,1,0)+str(x2,1,0)+str(y2,1,0)+ ;
str(x3,1,0)+str(y3,1,0)+str(x4,1,0)+str(y4,1,0) as kv ;
from ver1234 order by 1 into cursor kvadr
?seconds()-m.sc
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi leonid!

Нет смысла полностью квадрат описывать - достаточно лишь одно ребро (ver12) - по нему уже автоматом достраиваются остальные.

Я тоже исходил из идеи "урезанного квадранта" - от каждой точки, беря её за "начало отсчёта" строим квадрант (например как у тебя - в I квадрант, если принять стандартные геометрические обозначения) при этом сама "ось Ох" (точки на ней лежащие) принадлежит квадранту (y2 может быть равен y1), а вот ось Оу уже исключается (x2 строго больше x1)... Это то что получается в ver12.
Сам квадрат от начального ребра будет достраиваться тоже как у тебя - вверх и влево.
Вот с дополнительными граничными условиями надо ещё разбираться... сливать запросы в смысле


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет всем!

Правильно, Игорь!

Самый разумный и бесхитростный способ.

Алгоритм поиска всех возможных квадратов
на доске размером MхN.

Этот алгоритм составляет каталог всех квадратов, существующих на доске размером MхN.
Для фиксированного поля с координатами (I;J), алгоритм находит на доске все квадраты с вершиной в данном поле по следующему правилу. Выберем для определенности в северо-западном направлении от поля (I;J) вторую вершину и затем двигаясь по ходу часовой стрелки находим третью и четвертую вершины квадрата, причем, когда известны две вершины, третью и четвертую можно найти, давая координатам определенные приращения .

[attachment 4751 omega.JPG]

Простите за неудачный чертеж.

Таким образом, квадрат однозначно определяется выбором второй вершины в северо-западном квадранте OMEGA. Вторая вершина с координатами (О;Р) выбирается из области OMEGA (рис.2), задаваемой системой неравенств:
1 <= Р <= J
I+1 <= O <= M

Или в приращениях DJ и DI:
1–J <= DJ <= 0 ( 1 )
1 <= DI <= M – I
Координаты второй, третьей и четвертой вершины при этом вычисляются по формулам:
0 = I + DI ; P = J + DJ
Q = 0 – DJ ; R = P + DI
S = Q – DI ; T = R – DJ
Однако, каждый раз после этого проверяется: не вышла ли точка за границы доски, т.е. проверяется выполнение условий:
Q <= M ; R <= N
S <= M ; T <= N
Напечатанные рядом как одно число, восемь цифр I, J, O, P, Q, R, S, T и дадут нам один квадрат, один элемент каталога. Итак, меняя DI и DJ во всем диапазоне их изме-нения (см. систему неравенств 1), получим множество квадратов с вершиной в поле ( I;J ) – так называемое семейство поля (I;J ). Если теперь менять I и J во всём диапазоне их изменения, определяемом системой неравенств:
1 <= I <= M
1 <= J <= N ( 2 )
то получим множество всех квадратов, существующих на доске размером MxN.
Окончательно можно подытожить, что алгоритм представляет из себя сложный цикл, состоящий из четырех вложенных друг в друга циклов: циклы по I, J, DI и DJ.

Майкл
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
И еще...

Если элементы каталога собирать в символьном виде, то время работы моего алгоритма сравнимо со временем леонидовского, а если в чмсловом то мой вдвое быстрее. Не ожидал. Обычно обработка символьныз величин идет быстрее, а числовых медленнее- в программе 7 сложений и столько же умножений, а они тяжеловесные.

Оба кода дают по 196 восьмизначных чисел, неупорядоченных по вершинам.
Например предпоследний элемент Леонидовского алгоритма дал 65766756.
Как быстрее всего переставить вершины по возрастанию , т.е. преобразовать его в 56656776?

Можно ли и это сделать без циклов - одними селектами?
Удачи!
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет всем!

Мои все 4 вопроса остались без ответа.

Если дело пойдет споро, и все нюансы алгоритма будут нами обмозгованы , тогда можно будет создать игру "Квадратобоязнь".

Я собрал ее на VB6. Интересно мне сделать ее и на фоксе.

И опубликовал даже статейку с таким же названием в "ИНФО".
Алгоритм был тут же включен в список заданий , выставленных на Всероссийскую олимпиаду по информатике для школьников.

Удачи.
Майкл.
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
mayil
Как быстрее всего переставить вершины по возрастанию , т.е. преобразовать его в 56656776?
Я не уверен, что просто упорядочивать вершины по координатам имеет смысл. В моем примере они тоже определенным образом упорядочены. Первой идет вершина с минимальной координатой у, а если таких две, то та из них, у которых меньше координата х. А остальные вершины идут в порядке обхода квадрата против часовой стрелки.
Насчет четырех вопросов, я не совсем понял их направленность, но по-моему хранить вершины и работать с ними проще всего в курсоре с восьмью числовыми полями, как в моем примере курсор ver1234
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет.

Насчет тех 4-х вопросов.

В перспективе построение алгоритма игры. Играют двое: комп и человек.

Человек думает головой , а комп работает по нашему алгоритму (которого пока еще нет!).
Итак, человек поставил свою очередную фишку на какое-то поле. Для определенности - на поле 47. Комп должен просмотреть все квадраты, для которых это поле является вершиной (семейство квадратов поля 47). Надо же ему выяснить, к чему привел этот ход , может человек достроил таки свой квадрат и этим, стало быть, проиграл. А где комп может выявить это семейство? В массиве квадратов, который мы получили 2-мя твоими и одним моим кодом! А как он из 196 элементов массива может выбрать это семейство. Просматривая каждую восьмерку символов на предмет нахождения в оной числа 47 или текста "47".
Так вот, это можно сделать либо с помощью функции подстроки, если восьмерка символьная, или как-то по-другому если восьмерка числовая!
А в числовом виде хлопот побольше, хотя с другой стороны зачем же "склеивать" найденные 4 вершины в одно число, если потом их надо будет "расклеить".
Можно держать найденные квадраты в матрице katalog(196,4) и тогда поиск не вызовет трудностей. А еще лучше в курсоре или таблице katalog (pole1 n(2) , pole2 n(2) , pole3 n(2),pole4 n(2)), содержащей 196 записей, и проделывать поиски селектами.

И все тот же вопрос - какой метод более быстр?

Удачи!
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Вопрос скорости здесь совершенно второстепенный. Если написать все более ли менее правильно, то разница в скорости массивы-курсоры и числа-строки будет где-нибудь в районе 1.5-2 раза (массивы все-таки чуть-чуть побыстрее, чем курсоры), но эта разница совершенно не существенна, и выбирать надо то, с чем проще будет работать. А здесь, я думаю, у курсоров большое преимущество, поскольку появляется возможность использовать SQL.
Предположим, что квадраты строятся с помощью кода
m.xdim=7
m.ydim=7
create cursor xcoor (x I)
create cursor ycoor (y I)
for i=1 to m.xdim
insert into xcoor values (i)
next
for i=1 to m.ydim
insert into ycoor values (i)
next
select x,y from xcoor, ycoor into cursor xycoor
select xy1.x as x1, xy1.y as y1, xy2.x as x2, xy2.y as y2 ;
from xycoor xy1 join xycoor xy2 on xy1.x<xy2.x and xy1.y<=xy2.y ;
into cursor ver12
select x1, y1, x2, y2, x2+y1-y2 as x3, y2+x2-x1 as y3, ;
x1+y1-y2 as x4, y1+x2-x1 as y4 ;
from ver12 where x1+y1-y2>0 and y2+x2-x1<=m.ydim ;
into cursor ver1234
select str(x1,1,0)+str(y1,1,0) as v1, str(x2,1,0)+str(y2,1,0) as v2, ;
str(x3,1,0)+str(y3,1,0) as v3, str(x4,1,0)+str(y4,1,0) as v4 ;
from ver1234 order by 1 into cursor kvadr
а ходы черных хранятся в курсоре
create cursor cher_hody (hod C(2))
тогда проверить, не получился ли у черных квадрат, можно с помощью кода
select * from kvadr where ;
v1 in (select * from cher_hody) and ;
v2 in (select * from cher_hody) and ;
v3 in (select * from cher_hody) and ;
v4 in (select * from cher_hody);
into cursor kv
if _tally>0
&& есть квадрат
endif
На основе подобного кода совсем нетрудно написать программу, которая играла бы за компьютер, выбирая случайным образом ходы, которые не строят квадраты, но такая стратегия вряд ли была бы разумной. Нахождение более разумной страгегии - это уже совсем другая проблема, и, вероятно, значительно более сложная. А, кстати, у Гарднера было что-нибудь по поводу оптимальной стратегии?
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi leonid!

Насчёт массивы vs курсоры - тут слишком много "если" - и размеры, и стратегия доступа (одно дело если у тебя "разные" данные в ячейках - типа ID, Name, Address и совсем другое, когда там "однородные" данные, типа как у нас - координаты вершин квадрата - т.е. когда имеет смысл искать в массиве "забыв" про его двумерность).

В курсорах можно создать индексы - массив же просматривается "по порядку" если нужно что-то найти. В курсоре гораздо быстрее проводятся операции удаления/вставки записей - в массиве это может занять много времени...

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


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет!

Цитата:
Леонид. Нахождение более разумной страгегии - это уже совсем другая проблема, и, вероятно, значительно более сложная. А, кстати, у Гарднера было что-нибудь по поводу оптимальной стратегии?

У Гарднера нет, но есть у меня! Я построил программу на VB6.
Могу прислать, коли хотите!

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

Итак, общие соображения! От первого лица - от имени компьютера.

Ход мыслей компьютера: "Допустим я поставлю фишку на поле ik. Этот ход изменит состояние нескольких квадратов сразу - ведь поле ik служит вершиной многих квадратов! В одном из этих квадратов уже две вершины заняты моими фишками, я тогда сделаю его более опасным для себя, еще бы - в нем станут уже 3 мои фишки. В другом квадрате есть по одной фишке - моей и противника. Этот квадрат нейтральный , т. е. не опасный - ни я, ни противник не можем достроить его до полного квадрата. Назовем такие квадраты смешанными. В другом квадрате были 3 фишки противника , и этим ходом я нейтрализовал квадрат потенциально опасный для противника. А в каком то еще квадрате уже три вершины заняты моими фишками, стало быть ставя 4-ую , я проигрываю!

Итак , просмотрев все семейство квадратов для поля ik, мы находим среди них квадрат, самый опасный для меня.
Применяем эту логику для всей всободных полей доски.
И для каждого из них находим максимальный уровень опасности.

И в конце концов выбираем ход на то поле , где этот максимальный уровень опасности самый низкий. Стандартный МИНИМАКС.

А вот как оценить этот самый "уровень опасности" - над этим надо подумать!

1) Во первых, составьте алгоритм поиска семейства квадратов для поля ik.

Определить состояние квадрата можно, разумеется, по фишками, сидящим в вершинах оного! Различных ситуаций в вершинах квадратов всего несколько штук.
2) Придумайте способ оценки ситуации в квадрате, т. е. его уровень опасности!

Леонидовские селекты хороши, слов нет!


Удачи.
Майкл
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Я как-то решел одну задачку, у которой каждый вариант просчитывался около суток, а их было несколько десятков. Там на оптимизацию и разные эксперименты я потратил довольно много времени и у меня получилось, что на масивах процентов 20-30 выигрыша по сравнению с курсорами. Но на других задачах, конечно, может быть по-другому. Особенно если индексы и SQL удасться хорошо использовать.
Насчет стратегии: там есть примитивные варианты с симметричной стратегией, если количество рядов или столбцов четное. В связи с этим интересен вопрос: а бесконечную доску можно ли заполнить так, чтобы ни у белых ни у черных не было ни одного квадрата. Наверное нельзя. А как доказать? Что-то простое доказательство в голову не приходит. Если это верно, то на достаточно больших досках с четным числом столбцов или рядов симметричная стратегия будет оптимальной и обеспечит выигрыш тому, кто ходит вторым. Но это не интересно. А вот если число рядов и столбцов нечетно, то симметричная стратегия не прокатывает из-за хода в центр (который вероятно и разумно делать первым).
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Hi mayil!

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

Что касается собчтвенно оценки - думаю лучше всего брать число "потенциальных квадратов" проходящих через точку (т.е. незавершенных квадратов, имеющих вершину в анализируемой точке, а в других вершинах либо свои точки, либо пусто - если там "чужая" точка, то надо исключать квадрат из подсчёта), а не искать среди них "самый опасный" - плюс к тому можно каждый квадрат при подсчёте взвешивать (например если нашими точками уже занято 3 вершины, то взять вес 1, а если только 1 а две другие пусты - то вес 0.3. Что интересно - даже если все 3 потенциальные вершины пусты, то надо учитывать квадрат как опасный - но конечно минимально опасный . Коэффициенты кстати лучше вынести вовне кода - это будут параметры "агрессивности/тупости" алгоритма).

Другой вариант - составить полный список "небезопасных для нас" квадратов (т.е. где ни одна вершина не перекрыта чужой точкой), а потом в этом списке посумировать каждую имеющуюся точку. Наибольшая сумма, как я понимаю, будет у наиболее опасной позиции.

2 leonid

Я не уверен что симметричная стратегия на "чётном поле" вообще выигрывает - хотя очевидно что она и не проигрывает Мне кажется что она ведёт к ничьей, при правильной стратегии первого игрока. Кстати вариант оценки позиции №2 показывает преимущество второго игрока - ведь в начале игры у каждого игрока равное число "опасных квадратов", первый игрок своим ходом своё число "опасных" не меняет, а вот число опасных для второго - очевидно меняется... Хотя тут сложно сказать как потом игра будет развиваться - может начальный проигрыш окупается "инициативой"


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Igor Korolyov
Я не уверен что симметричная стратегия на "чётном поле" вообще выигрывает - хотя очевидно что она и не проигрывает Мне кажется что она ведёт к ничьей, при правильной стратегии первого игрока.
Я попробовал строить ничейные позиции на полностью заполненных полях. Еще на 5х5 у меня получилось, но уже на 5х6 - никак. Очень похоже, что на больших полностью заполненных полях ничейных позиций быть не может, а, следовательно, симметричная стратегия на "четных полях" выигрышна. Поэтому надо рассматривать только нечетные поля, начиная с 7х7. Я немного покопался в интернете, и похоже, что оптимальная стратегия для этого случая неизвестна. Еще одно соображение. Может быть при оценке позиции наиболее существенным фактором является разница между числом полей на которые еще могут ходить белые и числом полей, на которые могут ходить черные (не проигрывая при этом), вне зависимости от "опасности квадратов"?
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
mayil
Автор

Сообщений: 277
Откуда: Гянджа, Азербайд
Дата регистрации: 20.06.2006
Привет!

Гарднер пишет, что на досках четного порядка ничья возможна. При правильной игре!

А вот на досках нечетного порядка ничьи нет!

На таких досках запросто можно разоблачить (программно - в процессе игры!) симметричную стратегию противника (как центральную, так и осевую) и последующими ходами нейтрализовать ее!

К делу! Как оценить ситуацию в вершинах одного, отдельно взятого квадрата?!

Но сначала надо как-то различать ситуацию в одном, отдельно взятом поле. Имеются 3 случая:
1 - поле пустое, 2- занято фишкой компьютера, 3 - занято фишкой человека.

Надо подобрать три разных значения для однозначной идентификации этих трех случаев . И более того, эти значения должны быть таковы, чтобы ситуации в квадратах ( а это есть сумма вершин) также различались. В квадрате возможны 15 вариантов расположения (и отсутсвия!) фишек в вершинах.

Итак, надо подобрать три числа, чтобы между ситуациями в квадрате и суммой вершин его установить взаимно-однозначное соответствие!

Удачи!
Ratings: 0 negative/0 positive
Re: Алгоритмы и программы
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
mayil
Гарднер пишет, что на досках четного порядка ничья возможна. При правильной игре!
Вот насчет этого у меня очень большие сомнения. Попробуйте сделать ничью на доске 6х6. Ходить надо даблкликом. Компьютер играет по симметричной стратегии.
close all
clear all
set talk off
set deleted on
#DEFINE XCNT 6
#DEFINE YCNT 6
#DEFINE SHAG 40
declare Sleep in Win32API Integer
create cursor cher_hody (hod C(2))
m.xdim=XCNT
m.ydim=YCNT
create cursor xcoor (x I)
create cursor ycoor (y I)
for i=1 to m.xdim
insert into xcoor values (i)
next
for i=1 to m.ydim
insert into ycoor values (i)
next
select x,y from xcoor, ycoor into cursor xycoor
select xy1.x as x1, xy1.y as y1, xy2.x as x2, xy2.y as y2 ;
from xycoor xy1 join xycoor xy2 on xy1.x<xy2.x and xy1.y<=xy2.y ;
into cursor ver12
select x1, y1, x2, y2, x2+y1-y2 as x3, y2+x2-x1 as y3, ;
x1+y1-y2 as x4, y1+x2-x1 as y4 ;
from ver12 where x1+y1-y2>0 and y2+x2-x1<=m.ydim ;
into cursor ver1234
select str(x1,1,0)+str(y1,1,0) as v1, str(x2,1,0)+str(y2,1,0) as v2, ;
str(x3,1,0)+str(y3,1,0) as v3, str(x4,1,0)+str(y4,1,0) as v4 ;
from ver1234 order by 1 into cursor kvadr
oForm=NEWOBJECT("form1")
for m.i=1 to YCNT
oForm.ADDOBJECT("linex"+allt(str(i)),"line")
with eval("oForm.linex"+allt(str(i)))
.Height = 0
.Left = SHAG
.Top = SHAG*m.i
.Width = SHAG*(XCNT-1)
.visible=.t.
endwith
next
for m.i=1 to XCNT
oForm.ADDOBJECT("liney"+allt(str(i)),"line")
with eval("oForm.liney"+allt(str(i)))
.Height = SHAG*(YCNT-1)
.Left = SHAG*m.i
.Top = SHAG
.Width = 0
.visible=.t.
endwith
next
for m.i=1 to XCNT
for m.j=1 to YCNT
oForm.ADDOBJECT("fishka"+allt(str(m.i))+allt(str(m.j)),"fishka")
with eval("oForm.fishka"+allt(str(m.i))+allt(str(m.j)))
.Top = SHAG*m.j-SHAG/4
.Left = SHAG*m.i-SHAG/4
.visible=.t.
endwith
next
next
oform.Show
RETURN
DEFINE CLASS form1 AS form
Autocenter=.t.
Height = SHAG*(YCNT+1)
Width = SHAG*(XCNT+1)
DoCreate = .T.
Caption = "Kvadratobojaznj"
WindowType = 1
MinButton=.f.
MaxButton=.f.
Name = "Form1"
Procedure otv_hod
lparameters m.xcoor, m.ycoor
m.xy=allt(str(m.xcoor))+allt(str(m.ycoor))
insert into cher_hody values(m.xy)
select * from kvadr where ;
v1 in (select * from cher_hody) and ;
v2 in (select * from cher_hody) and ;
v3 in (select * from cher_hody) and ;
v4 in (select * from cher_hody);
into cursor kv
if _tally>0
Thisform.setall("enabled", .f.)
for m.j=1 to 3
for m.i=1 to 4
with eval("Thisform.fishka"+eval("kv.v"+allt(str(m.i))))
.backcolor=RGB(255,0,0)
endwith
next
doevents()
sleep(250)
for m.i=1 to 4
with eval("Thisform.fishka"+eval("kv.v"+allt(str(m.i))))
.backcolor=0
endwith
next
doevents()
sleep(250)
next
for m.i=1 to 4
with eval("Thisform.fishka"+eval("kv.v"+allt(str(m.i))))
.backcolor=RGB(255,0,0)
endwith
next
return
endif
with eval("Thisform.fishka"+allt(str(XCNT+1-m.xcoor))+allt(str(YCNT+1-m.ycoor)))
.backstyle=1
.backcolor=0xFFFFFF
endwith
ENDDEFINE
DEFINE CLASS fishka AS shape
Height = SHAG/2
Width = SHAG/2
BackStyle = 0
BorderStyle = 0
Curvature = 90
Procedure DblClick
if This.backstyle=1
return
endif
This.BackColor = 0
This.backstyle=1
Thisform.otv_hod((This.left+SHAG/4)/SHAG,(This.top+SHAG/4)/SHAG)
ENDDEFINE
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 1 (Гостей: 1)

© 2000-2024 Fox Club 
Яндекс.Метрика