Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Листинг 8.13. 
C4Piece.java
package 
chapter8;
public enum 
C4Piece 
implements 
Piece {
B
, 
R
, 
E
; // E — пустое поле
@Override
public 
C4Piece opposite() {
switch 
(
this
) {
case B
:
return 
C4Piece.
R
;
case R
:
return 
C4Piece.
B
;
default
: // E, пустое поле 
return 
C4Piece.
E
;
}
}
@Override
public 
String toString() {
switch 
(
this
) {
case B
:
return 
"B";
case R
:
return 
"R";
default
: // E, пустое поле
return 
" ";
}
}
}
Класс.
C4Piece
.практически.идентичен.классу.
TTTPiece
..У.нас.также.будет.удобный.
класс.
C4Location
.для.отслеживания.ячейки.в.сетке.поля.(пара.«столбец/строка»)..
Connect.Four.—.это.игра,.ориентированная.на.столбцы,.поэтому.мы.реализуем.
весь.код.ее.сетки.в.необычном.формате:.сначала.столбец.(листинг.8.14).
Затем.переходим.к.классу.
C4Board
..Он.определяет.несколько.статических.констант.
и.один.статический.метод..Статический.метод.
generateSegments()
.возвращает.
список.массивов.ячеек.сетки.(
C4Locations
)..Каждый.массив.в.списке.содержит.
четыре.ячейки.сетки..Мы.называем.каждый.из.этих.массивов.из.четырех.точек.

---

232
Глава 8.
Состязательный поиск
сетки.
сегментом
..Если.какой-либо.сегмент.на.доске.окажется.окрашен.в.один.
цвет,.это.будет.означать,.что.данный.цвет.выиграл.
Листинг 8.14. 
C4Location.java
package 
chapter8;
public final class 
C4Location {
public final int 
column, row;
public 
C4Location(
int 
column, 
int 
row) {
this
.column = column;
this
.row = row;
}
}
Возможность.быстрого.поиска.всех.сегментов.на.доске.позволяет.не.только.про-
верить,.закончилась.ли.игра.(кто-то.выиграл),.но.и.оценить.позицию..Поэтому,.как.
вы.увидите.в.следующем.фрагменте.кода.(листинг.8.15),.мы.кэшируем.сегменты.
для.доски.заданного.размера.в.виде.переменной.
SEGMENTS
.в.классе.
C4Board
.
Листинг 8.15. 
C4Location.java
package 
chapter8;
import 
java.util.ArrayList;
import 
java.util.Arrays;
import 
java.util.List;
public class 
C4Board 
implements 
Board {
public static final int NUM_COLUMNS 
= 7;
public static final int NUM_ROWS 
= 6;
public static final int SEGMENT_LENGTH 
= 4;
public static final 
ArrayList 
SEGMENTS 
= 
generateSegments
();
// генерируем все сегменты для данного поля, 
// этот статический метод запускается только один раз
private static 
ArrayList generateSegments() {
ArrayList segments = 
new 
ArrayList<>();
// генерируем вертикальные сегменты
for 
(
int 
c = 0; c < 
NUM_COLUMNS
; c++) {
for 
(
int 
r = 0; r <= 
NUM_ROWS — SEGMENT_LENGTH
; r++) {
C4Location[] bl = 
new 
C4Location[
SEGMENT_LENGTH
];
for 
(
int 
i = 0; i < 
SEGMENT_LENGTH
; i++) {
bl[i] = 
new 
C4Location(c, r + i);
}
segments.add(bl);
}
}
// генерируем горизонтальные сегменты
for 
(
int 
c = 0; c <= 
NUM_COLUMNS — SEGMENT_LENGTH
; c++) {
for 
(
int 
r = 0; r < 
NUM_ROWS
; r++) {

---

8.3. Connect Four
233
C4Location[] bl = 
new 
C4Location[
SEGMENT_LENGTH
];
for 
(
int 
i = 0; i < 
SEGMENT_LENGTH
; i++) {
bl[i] = 
new 
C4Location(c + i, r);
}
segments.add(bl);
}
}
// генерируем сегменты диагонали из нижнего левого в верхний правый угол
for 
(
int 
c = 0; c <= 
NUM_COLUMNS — SEGMENT_LENGTH
; c++) {
for 
(
int 
r = 0; r <= 
NUM_ROWS — SEGMENT_LENGTH
; r++) {
C4Location[] bl = 
new 
C4Location[
SEGMENT_LENGTH
];
for 
(
int 
i = 0; i < 
SEGMENT_LENGTH
; i++) {
bl[i] = 
new 
C4Location(c + i, r + i);
}
segments.add(bl);
}
}
// генерируем сегменты диагонали из нижнего правого в верхний левый угол
for 
(
int 
c = 
NUM_COLUMNS — SEGMENT_LENGTH
; c >= 0; c--) {
for 
(
int 
r = 
SEGMENT_LENGTH — 
1; r < 
NUM_ROWS
; r++) {
C4Location[] bl = 
new 
C4Location[
SEGMENT_LENGTH
];
for 
(
int 
i = 0; i < 
SEGMENT_LENGTH
; i++) {
bl[i] = 
new 
C4Location(c + i, r — i);
}
segments.add(bl);
}
}
 return 
segments;
}
Мы.сохраняем.текущую.позицию.
position
.в.двумерном.массиве.
C4Piece
..В.боль-
шинстве.случаев.двумерные.массивы.индексируются,.начиная.с.первой.строки..
Но.представление.о.поле.Connect.Four.как.о.группе.из.семи.столбцов.упрощает.
написание.остальной.части.класса.
C4Board
..Например,.сопутствующий.массив.
columnCount
.отслеживает,.сколько.частей.одновременно.находится.в.любом.за-
данном.столбце..Это.упрощает.создание.допустимых.ходов,.поскольку.каждый.
ход.представляет.собой.выделение.незаполненного.столбца.
Следующие.четыре.метода.очень.похожи.на.их.эквиваленты.в.игре.в.крестики-
нолики.(листинг.8.16).
Листинг 8.16. 
C4Board.java (продолжение)
private 
C4Piece[][] position; // сначала столбец, затем строка
private int
[] columnCount; // количество фишек в каждом столбце
private 
C4Piece turn;
public 
C4Board() {
// обратите внимание на то, что мы сначала создаем столбцы
position = 
new 
C4Piece[
NUM_COLUMNS
][
NUM_ROWS
];

---

234
Глава 8.
Состязательный поиск
for 
(C4Piece[] col : position) {
Arrays.
fill
(col, C4Piece.
E
);
}
// ints по умолчанию инициализируются значением 0
columnCount = 
new int
[
NUM_COLUMNS
];
turn = C4Piece.
B
; // черные ходят первыми
}
public 
C4Board(C4Piece[][] position, C4Piece turn) {
this
.position = position;
columnCount = 
new int
[
NUM_COLUMNS
];
for 
(
int 
c = 0; c < 
NUM_COLUMNS
; c++) {
int 
piecesInColumn = 0;
for 
(
int 
r = 0; r < 
NUM_ROWS
; r++) {
if 
(position[c][r] != C4Piece.
E
) {
piecesInColumn++;
}
}
columnCount[c] = piecesInColumn;
}
this
.turn = turn;
}
@Override
public 
Piece getTurn() {
return 
turn;
}
@Override
public 
C4Board move(Integer location) {
C4Piece[][] tempPosition = Arrays.
copyOf
(position, position.length);
for 
(
int 
col = 0; col < 
NUM_COLUMNS
; col++) {
tempPosition[col] = Arrays.
copyOf
(position[col], 
position[col].length);
}
tempPosition[location][columnCount[location]] = turn;
 return new 
C4Board(tempPosition, turn.opposite());
}
@Override
public 
List getLegalMoves() {
List legalMoves = 
new 
ArrayList<>();
for 
(
int 
i = 0; i < 
NUM_COLUMNS
; i++) {
if 
(columnCount[i] < 
NUM_ROWS
) {
legalMoves.add(i);
}
}
return 
legalMoves;
}
Вспомогательный.метод.
countSegment()
.возвращает.количество.черных.и.крас-
ных.фишек.в.определенном.сегменте..За.ним.следует.метод.проверки.выигрыша.
isWin()
,.который.просматривает.все.сегменты.на.поле.и.определяет,.была.ли.игра.

---

8.3. Connect Four
235
выиграна,.используя.метод.
countSegment()
,.чтобы.подсчитать,.есть.ли.в.каком-
либо.сегменте.четыре.фишки.одного.цвета.(листинг.8.17).
Листинг 8.17. 
C4Board.java (продолжение)
private int 
countSegment(C4Location[] segment, C4Piece color) {
int 
count = 0;
for 
(C4Location location : segment) {
if 
(position[location.column][location.row] == color) {
count++;
}
}
return 
count;
}
@Override
public boolean 
isWin() {
for 
(C4Location[] segment : 
SEGMENTS
) {
int 
blackCount = countSegment(segment, C4Piece.
B
);
int 
redCount = countSegment(segment, C4Piece.
R
);
if 
(blackCount == 
SEGMENT_LENGTH 
|| redCount == 
SEGMENT_LENGTH
) {
return true
;
}
}
return false
;
}
Как.и.
TTTBoard
,.
C4Board
.может.использовать.свойство.
isDraw()
.абстрактного.
базового.класса.
Board
.без.изменений.
Чтобы.оценить.позицию,.мы.по.очереди.оценим.все.представляющие.ее.сегменты,.
суммируем.оценки.и.вернем.результат..Сегмент.с.красными.и.черными.фишками.
будет.считаться.бесполезным..Сегмент,.имеющий.два.поля.с.фишками.одного.
цвета.и.два.пустых.поля,.получит.1.балл..Сегмент.с.тремя.фишками.одного.цвета.
будет.оценен.в.100.баллов..Наконец,.сегмент.с.четырьмя.фишками.одного.цвета.
(победа).набирает.1.000.000.баллов..Если.сегмент.принадлежит.противнику,.то.
его.очки.вычитаются..Функция.
evaluateSegment()
.—.вспомогательный.метод,.
который.оценивает.сегмент.с.применением.предыдущей.формулы..Суммарная.
оценка.всех.сегментов.методом.
evaluateSegment()
.выполняется.с.помощью.
evaluate()
.(листинг.8.18).
Листинг 8.18. 
C4Board.java (продолжение)
private double 
evaluateSegment(C4Location[] segment, Piece player) {
int 
blackCount = countSegment(segment, C4Piece.
B
);
int 
redCount = countSegment(segment, C4Piece.
R
);
if 
(redCount > 0 && blackCount > 0) {
return 
0.0; // смешанные сегменты нейтральны 
}

---

236
Глава 8.
Состязательный поиск
int 
count = Math.
max
(blackCount, redCount);
double 
score = 0.0;
if 
(count == 2) {
score = 1.0;
} 
else if 
(count == 3) {
score = 100.0;
} 
else if 
(count == 4) {
score = 1000000.0;
}
C4Piece color = (redCount > blackCount) ? C4Piece.
R 
: C4Piece.
B
;
if 
(color != player) {
 
return 
-score;
}
return 
score;
}
@Override
public double 
evaluate(Piece player) {
double 
total = 0.0;
for 
(C4Location[] segment : 
SEGMENTS
) {
total += evaluateSegment(segment, player);
}