Федеральное агентство по образованию Российской Федерации
Брянский Государственный Технический Университет
Кафедра«Информатика и программное обеспечение»
Курсоваяработа
по предмету: «Интеллектуальныесистемы»
на тему: «Разработкаалгоритма и реализация игры “реверси”»
Выполнил:
студент гр.07-ПО3
Черкесов М.В.
Преподаватель:
БулатицкийД.И.
Брянск
2010
Содержание/>/>
Введение
1. Алгоритм
1.1 Алгоритм альфа-бета отсечения
2. Описание программного средства
2.1 Руководство пользователя
2.2 Листинг программы
Заключение
Список литературы
Введение
В игре используетсяквадратная доска размером 8 × 8 клеток (все клетки могут быть одного цвета)и 64 специальные фишки, окрашенные с разных сторон в контрастные цвета,например, в белый и чёрный. Клетки доски нумеруются от верхнего левого угла:вертикали — латинскими буквами, горизонтали — цифрами. Один из игроков играетбелыми, другой — чёрными. Делая ход, игрок ставит фишку на клетку доски «своим»цветом вверх.
В начале игры в центрдоски выставляются 4 фишки: чёрные на d5 и e4, белые на d4 и e5.
Первый ход делают чёрные.Далее игроки ходят по очереди.
Делая ход, игрок долженпоставить свою фишку на одну из клеток доски таким образом, чтобы между этойпоставленной фишкой и одной из имеющихся уже на доске фишек его цвета находилсянепрерывный ряд фишек соперника, горизонтальный, вертикальный или диагональный(другими словами, чтобы непрерывный ряд фишек соперника оказался «закрыт»фишками игрока с двух сторон). Все фишки соперника, входящие в «закрытый» наэтом ходу ряд, переворачиваются на другую сторону (меняют цвет) и переходят кходившему игроку.
Если в результате одногохода «закрывается» одновременно более одного ряда фишек противника, топереворачиваются все фишки, оказавшиеся на всех «закрытых» рядах.
Игрок вправе выбиратьлюбой из возможных для него ходов. Если игрок имеет возможные ходы, он не можетотказаться от хода. Если игрок не имеет допустимых ходов, то ход передаётсясопернику.
Игра прекращается, когдана доску выставлены все фишки или когда ни один из игроков не может сделатьхода. По окончании игры проводится подсчёт фишек каждого цвета, и игрок, чьихфишек на доске выставлено больше, объявляется победителем. В случае равенстваколичества фишек засчитывается ничья.
Игра была изобретена вВеликобритании в 1880 году и пользовалась большой популярностью, новпоследствии была забыта. Возродили её в Японии, где она в 1971 году под названиемотелло вновь стала популярна. С 1977 года регулярно проводятся чемпионаты мирапо игре в реверси.
Реверси являетсястратегической игрой, схожей с шашками и шахматами. Так же как и в шахматах,принято разделять партию на три части: дебют (начало), миттельшпиль (серединаигры) и эндшпиль (концовка). Однако, в отличие от шахмат, количество возможныхдебютов здесь намного меньше, и все они легко запоминаются. Все сколько-либосерьёзные игроки знают дебюты на 5-6 ходов вперёд, чтобы избежать заведомо проигрышныхходов на данной стадии. Миттельшпиль, пожалуй, является наиболее «свободной» иодновременно сложной частью игры, когда положение можно либо упрочить, либоизменить в свою пользу. Несмотря на это, многие, казалось бы, проигранные вмиттельшпиле партии обретают новые качества при вступлении в конечную стадиюигры — эндшпиль. Золотое правило концовки — не спешить и считать. Считатьпринято фишки, которые результируют конечный исход игры для конкретной тактики.Естественно, количество исходов зависит от того, с какого хода начинатьсчитать, и именно поэтому компьютеры играют намного лучше людей — они могутпозволить себе просчитать все возможные варианты (их, по компьютерным меркам,немного) и всегда выбирают тот, при котором минимизируется результат человека имаксимизируются очки компьютера.
Существует достаточномного различных стратегий игры в реверси[1], и выбор определяется уровнемподготовки и наклонностями игрока. Простейшей для новичков может быть игра зазахват угловых клеток доски, которые впоследствии уже невозможно «перекрасить»в другой цвет, и последовательное занятие доски от углов. Более продвинутойтактикой считается ограничение возможных ходов противника: создаётся позиция, вкоторой противнику остаются только устраивающие игрока ходы, и игра проходит вудобном для игрока русле. Как правило, большинство японских мастеров отличаетсяименно этой, отточенной до совершенства, тактикой. Ещё более продвинутойтактикой является тактика «темпов» (англ. temp), которую можно охарактеризовать правилом «отними упротивника его самые выгодные ходы и сделай их своими». Данная стратегиятребует, однако, чрезвычайно сильного «чувства позиции».
Варианты реверси:
· Реверсиn × n
Игра на поле n × nклеток. От игры 8 × 8 отличается тем, что фишки одного цвета в началеигры ставятся не в шахматном порядке, а рядом. Существуют варианты реверси сразмером поля 10 × 10 и больше. Они не отличаются от обычных ничем, кромеразмера поля. В целом, варианты размером меньше 8 × 8 не представляютинтереса, поскольку являются детерминированными и при идеальной стратегиивсегда выигрывает второй игрок (тот, кто ходит вторым).
· Антиреверси
Отличается только тем,что при подведении результатов игры выигрывает тот, у кого фишек меньше.
· Реверси с чёрнойдырой
Отличается только тем,что одна из клеток доски (случайно выбирается в начале игры) помечается как«черная дыра». При этом на неё нельзя сделать ход, и фишки с одной сторонытакой клетки не могут захватить фишки с другой.
Компьютерные программыреверси уже с середины 1990-х годов играют намного сильнее людей. Программа Logistello в 1997 году обыграла чемпиона мираТакэси Мураками 6:0.[4]
Как и многие игры,реверси довольно распространены в Интернете. Однако, отсутствие «культового»статуса, позволяет наткнуться в онлайне на игроков мирового уровня (так,например, на сайте рамблер.ру, одно время играл основатель Ассоциации реверси вСССР Олег Степанов, а трёхкратный чемпион мира Хидеси Таменори до сих пориграет на www.kurnik.pl подником becky2002jan). Практически все уважающие себя гейм-порталы имеютраздел реверси, однако вследствие того, что компьютеры играют намного лучшелюдей, в Интернете считается хорошим тоном играть только блицы (обычно до двухминут на каждого игрока).
разработкаалгоритм программа листинг
1.Алгоритм
Для компьютера эта играявляется достаточно простой и хорошие программы без особого труда обыгрываютдаже чемпионов среди людей. Данное качество достигается на данном этаперазвития техники алгоритмом альфа-бета отсечения, с использованием большой базыданных уже прошедших партий. В игре существует порядка 10^28 позиций, и около10^58 возможных партий./>
1.1 Алгоритм альфа-бетаотсечения
Альфа-бета отсечение(англ. Alpha-beta pruning) — это алгоритм поиска, стремящийся сократитьколичество узлов, оцениваемых в дереве поиска алгоритмом минимакс. Этоталгоритм предназначен для антагонистических игр и используется для машиннойигры (в шахматах, го и других). В основе алгоритма лежит идея, что оцениваниеветви дерева поиска может быть досрочно прекращено (без вычисления всехзначений оценивающей функции), если было найдено, что для этой ветви значениеоценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви.(Рис.1) Альфа-бета отсечение является оптимизацией, так как результаты работыоптимизируемого алгоритма не изменяются.
/>
Рис.1 Алгоритм альфа-бетаотсечения
Преимущество альфа-бетаотсечения фактически заключается в том, что некоторые из ветвей подуровнейдерева поиска могут быть исключены после того, как хотя бы одна из ветвейуровня рассмотрена полностью. Так как отсечения происходят на каждом уровневложенности (кроме последнего), эффект может быть весьма значительным. Наэффективность метода существенно влияет предварительная сортировка вариантов(без перебора или с перебором на меньшую глубину) — при сортировке чем больше вначале рассмотрено «хороших» вариантов, тем больше «плохих» ветвей может бытьотсечено без исчерпывающего анализа. минимаксный поиск осуществляется вглубину, поэтому в любой момент времени достаточно рассматривать узлы вдольединственного пути в дереве. Алгоритм альфа-бета-отсечения получил своеназвание по следующим двум параметрам, которые представляют пределы взарезервированных значениях, присутствующих во всех узлах вдоль этого пути: а =значение наилучшего варианта (т.е. варианта с самым высоким значением), которыйбыл до сих пор найден в любой точке выбора вдоль пути для игрока МАХ; Р =значение наилучшего варианта (т.е. варианта с самым низким значением), которыйбыл до сих пор найден в любой точке выбора вдоль пути для игрока MIN. Алгоритмальфа-бета-поиска в процессе своей работы обновляет значения а и Р, а такжеотсекает оставшиеся ветви в узле (т.е. прекращает рекурсивные вызовы), кактолько становится известно, что значение текущего узла хуже по сравнению стекущим значением а или Р для игрока МАХ или MIN соответственно.
2.Описание программного средства/>
2.1 Руководствопользователя
Для работы с программойнеобходимо активизировать её. Для этого нужно на рабочем столе двойным кликоммыши щелкнуть по ярлыку «Reversi»:Спустя мгновение перед вами откроется рабочее окно приложения (Pиc.2).
Оно состоит из элементов:
· Игровое поле, гденаходятся фишки игрока и противника.
· Поле подсчётаочков (количества фишек).
· Кнопка началановой игры.
/>
Рис. 2 Окно программы.
Затем нажимая левойклавишей мыши на игровом поле делаем ходы, ставя свои фишки, руководствуясьстандартными правилами игры. Игра продолжается до тех пор, пока всё поле небудет заставлено фишками игрока и противника. Затем программа предлагает начатьновую игру./>
2.2 Листинг программы
unit Reversi;
interface
type sPosData= record // Информация о текущей позиции
corner: boolean; // Захвачен ли угол
square2x2: boolean;// площадь 2х2 в углах захвачена
edge: boolean;
stable:integer; // Число стоящихфишек
internal: integer; // Число внутренних фишек
disks: integer; // Количество всех фишек
mx, my: integer; // движениекоординаты x и y
end;
tBoard=array[0..7,0..7] of byte;
pBoard=^tBoard;
functionCalculateData(cc: byte; cx, cy: integer): sPosData;
functionCheckMove(color:byte; cx, cy: integer): integer;
functionDoStep(data: pBoard): word;
implementation
var brd, brd2,brd3: tBoard;
functionCalculateData(cc: byte; cx, cy: integer): sPosData;
// Calculatedata about current position
// Parameter:cc — Who do move, black or white?
// if (cc ==1) White makes a move
// if (cc ==2) Black makes a move
var data:sPosData;
i, j: integer;
intern:boolean;
begin
data.corner:=FALSE;
data.disks:=0;
data.internal:=0;
data.stable:=0;
data.square2x2:=FALSE;
data.edge:=FALSE;
data.mx:= cx;
data.my:= cy;
// делаем копию доски ивычислите сумму фишек
for i:=0 to 7do
for j:=0 to 7do
begin
brd3[i,j]:=brd2[i,j];
if brd2[i,j]=cc then inc(data.disks);
end;
// Заполняем «угловые» данные
if ((cy=0) and(cx=0)) or ((cy=0) and (cx=7)) or
((cy=7) and(cx=0)) or ((cy=7) and (cx=7)) then
data.corner:=TRUE;
// Fill the«square2x2» data
if ((cy=6)) or
((cy>=6)and (cx=6) and (cx>=6)) then
data.square2x2:=TRUE;
// Fill the«edge» data
if (cy=0) or(cx=0) or (cy=7) or (cx=7) then
data.edge:= TRUE;
// Вычисляем числостоящих фишек
for i:=0 to 7do // Left-Upper corner
begin
if brd3[i,0] cc then break;
for j:=0 to 7do
begin
if brd3[i,j] cc then break;
inc(data.stable);
brd3[i,j]:= 0;
end;
end;
for i:=7downto 0 do // Left-Lower corner
begin
if brd3[i,0] cc then break;
for j:=0 to 7do
begin
if brd3[i,j] cc then break;
inc(data.stable);
brd3[i,j]:= 0;
end;
end;
for i:=7downto 0 do // Right-Bottom corner
begin
if brd3[i,7] cc then break;
for j:=7downto 0 do
begin
if brd3[i,j] cc then break;
inc(data.stable);
brd3[i,j]:= 0;
end;
end;
for i:=0 to 7do // Right-Upper corner
begin
if brd3[i,7] cc then break;
for j:=7downto 0 do
begin
if brd3[i,j] cc then break;
inc(data.stable);
brd3[i,j]:= 0;
end;
end;
// Calculatenumber of internal discs
for i:=0 to 7do
for j:=0 to 7do
if brd2[i,j] =cc then
begin
intern:= TRUE;
if (i>0)and (j>0) and (brd[i-1, j-1]=0) then intern:= FALSE;
if (i>0)and (brd[i-1, j]=0) then intern:= FALSE;
if (i>0)and (j
if (i0) and (brd[i+1, j-1]=0) then intern:= FALSE;
if (i
if (i
if (j>0)and (brd[i, j-1]=0) then intern:= FALSE;
if (j
if intern theninc(data.internal);
end;
result:=data;
end;
functionCheckMove(color:byte; cx, cy: integer): integer;
// Functioncheck: is move to (cx, cy) possible?
// Parameter:color — Who makes the move, black or white?
// if (colour== 0) White do a move
// if (colour== 1) Black do a move
// return: 0 — if impossible
// 1 — ifpossible, and number
// value isamount of the seized disks
var test,passed: boolean;
i, j, total:integer;
wc1, wc2:byte; // What to check
begin
total:=0;
// do a copyof board
for i:=0 to 7do
for j:=0 to 7do
brd2[i, j]:=brd[i, j];
if color=0then //white
begin
wc1:= 2;
wc2:= 1;
end
else
begin
wc1:= 1;
wc2:= 2;
end;
if brd[cy,cx] 0 then begin result:= 0; exit; end;
passed:=FALSE;
test:= FALSE;
for i:=cx-1downto 0 do // Check left
begin
if brd[cy, i]= wc1 then test:= TRUE
else
if ((brd[cy,i] = wc2) and (test)) then
begin
passed:= TRUE;
for j:=cx-1downto i+1 do inc(total);
for j:=cx-1downto i+1 do brd2[cy, j]:= wc1; ////???????
break;
end
else break;
end;
test:= FALSE;
for i:=cx+1 to7 do // Check Right
begin
if (brd[cy, i]= wc1) then test:= TRUE
else
if ((brd[cy,i] = wc2) and test) then
begin
passed:= TRUE;
for j:=cx+1 toi-1 do inc(total);
for j:=cx+1 toi-1 do brd2[cy, j]:= wc1;
break;
end
else break;
end;
test:= FALSE;
for i:=cy-1downto 0 do // Check Up
begin
if (brd[i, cx]= wc1) then test:= TRUE
else
if ((brd[i,cx] = wc2) and test) then
begin
passed:= TRUE;
for j:=cy-1downto i+1 do inc(total);
for j:=cy-1downto i+1 do brd2[j, cx]:= wc1;
break;
end
else break;
end;
test:= FALSE;
for i:=cy+1 to7 do // Check Down
begin
if (brd[i, cx]= wc1) then test:= TRUE
else
if ((brd[i,cx] = wc2) and (test)) then
begin
passed:= TRUE;
for j:=cy+1 toi-1 do inc(total);
for j:=cy+1 toi-1 do brd2[j, cx]:= wc1;
break;
end
else break;
end;
test:= FALSE;
for i:=1 to 7do // Check Left-Up
begin
if (((cy-i)>= 0) and ((cx-i) >= 0)) then
if (brd[cy-i,cx-i] = wc1) then test:= TRUE
else
if ((brd[cy-i,cx-i] = wc2) and (test)) then
begin
passed:= TRUE;
for j:=1 toi-1 do inc(total);
for j:=1 toi-1 do brd2[cy-j, cx-j]:= wc1;
break;
end
else break
else break;
end;
test:= FALSE;
for i:=1 to 7do // Check Left-Down
begin
if (((cy+i)= 0)) then
if (brd[cy+i,cx-i] = wc1) then test:= TRUE
else
if ((brd[cy+i,cx-i] = wc2) and (test)) then
begin
passed:= TRUE;
for j:=1 toi-1 do inc(total);
for j:=1 toi-1 do brd2[cy+j, cx-j]:= wc1;
break;
end
else break
else break;
end;
test:= FALSE;
for i:=1 to 7do // Check Right-Up
begin
if (((cy-i)>= 0) and ((cx+i)
if (brd[cy-i,cx+i] = wc1) then test:= TRUE
else
if ((brd[cy-i,cx+i] = wc2) and (test)) then
begin
passed:= TRUE;
for j:=1 toi-1 do inc(total);
for j:=1 toi-1 do brd2[cy-j, cx+j]:= wc1;
break;
end
else break
else break;
end;
test:= FALSE;
for i:=1 to 7do // Check Right-Down
begin
if (((cy+i)
if (brd[cy+i,cx+i] = wc1) then test:= TRUE
else
if ((brd[cy+i,cx+i] = wc2) and (test)) then
begin
passed:= TRUE;
for j:=1 toi-1 do inc(total);
for j:=1 toi-1 do brd2[cy+j, cx+j]:= wc1;
break;
end
else break
else break;
end;
if passed thenresult:= total
elseresult:=0;
end;
functionDoStep(data: pBoard): word;
var i, j, k,l, value, value1, value2, value3: integer;
pd, pdb,savedData: sPosData;
fMove, fMoveb:boolean; // First move?
begin
for i:=0 to 7do // Copy data from source data to brd
for j:=0 to 7do
brd[j,i]:=data^[j,i];
fMove:= TRUE;
for i:=0 to 7do
for j:=0 to 7do
begin
if(CheckMove(0, j, i) > 0) then
begin
pd:=CalculateData(1, j, i);
fMoveb:= TRUE;
value:= 0;
for k:=0 to 7do
for l:=0 to 7do
if (CheckMove(1, l, k) > 0) then
begin
pdb:=CalculateData(2, l, k);
if pdb.cornerthen value3:=200 else value3:=0;
value3:=value3+pdb.stable*4;
value3:=value3+pdb.internal*3;
//value3:=value3+pdb.disks;
//if pdb.edgethen value3:=value3+ 1;
ifpdb.square2x2 then value3:=value3-50;
if fMoveb then
begin
value:=value3;
fMoveb:=FALSE;
end
else
if (value3> value) then value:= value3;
end;
if fMove then
begin
savedData:=pd;
fMove:= FALSE;
end
else
begin
if pd.cornerthen value1:=200 else value1:=0;
value1:=value1+pd.stable*5;
value1:=value1+pd.internal*3;
value1:=value1+pd.disks;
if pd.edgethen value1:=value1+ 1;
ifpd.square2x2 then value1:=value1- 50;
value1:=value1-value;
ifsavedData.corner then value2:=200 else value2:=0;
value2:=value2+savedData.stable*5;
value2:=value2+savedData.internal*3;
value2:=value2+savedData.disks;
ifsavedData.edge then value2:=value2+ 1;
if savedData.square2x2then value2:=value2-50;
if (value1> value2) then
move(pd,savedData,sizeof(sposdata));//savedData:= pd;
end;
end;
end;
if not fMovethen result:=savedData.my * 256 + savedData.mx
else result:=65535;
end;
end.
Заключение
В результате выполненияработы была разработана программа реализующая алгоритм игры «Реверси». Былиполучены навыки реализации алгоритмов по предмету «Интеллектуальные системы».
Списоклитературы
1. Strategyguide // URL; radagast.se/othello/Help/strategy.html
2. Рукотворный разум// URL
3. А. Я.Архангельский Программирование в Delphi 7 Издательство: Бином-Пресс, 2003 г. ISBN 5-9518-0042-0
4. А. Я.Архангельский Приемы программирования в Delphi Издательство: Бином-Пресс, 2004 г. ISBN 5-9518-0067-6
5. А. Жуков ИзучаемDelphi Издательство: Питер, 2001 г. ISBN 5-272-00202-4