비대칭 KOTH : 고양이를 잡아라
UPDATE :
Controller.java가 예외를 포착하지 않아 (오류 만) gist 파일이 업데이트됩니다 (새로운 서브 미슨 포함). 이제 오류와 예외를 포착하고 인쇄합니다.
이 도전은 두 개의 스레드로 구성되며, 이것은 고양이 스레드이며 포수 스레드는 여기 에서 찾을 수 있습니다 .
컨트롤러는 여기에서 다운로드 할 수 있습니다 .
이것은 비대칭 KOTH입니다. 각 제출물은 고양이 또는 포수 입니다. 고양이와 포수의 각 쌍 사이에 게임이 있습니다. 고양이와 포수는 별개의 순위를 가지고 있습니다.
포수
육각형 격자에 고양이가 있습니다. 당신의 임무는 가능한 한 빨리 잡는 것입니다. 매 턴마다 고양이가 물에 빠지지 않도록 물통을 하나의 격자 셀에 놓을 수 있습니다. 그러나 고양이는 (아마도) 바보가 아니며 양동이를 놓을 때마다 고양이는 다른 그리드 셀로 이동합니다. 격자는 육각형이므로 고양이는 6 가지 방향으로 갈 수 있습니다. 당신의 목표는 물통으로 고양이를 둘러싸고, 더 빠를수록 좋습니다.
고양이
당신은 포수가 당신 주위에 물통을 놓아서 당신을 붙잡고 싶어한다는 것을 알고 있습니다. 물론 당신은 피하려고 노력하지만, 당신은 게으른 고양이 (고양이처럼)로서 한 번에 정확히 한 걸음을 내딛습니다. 이것은 당신이 같은 곳에 머물 수는 없지만 6 개의 주변 지점 중 하나로 이동해야한다는 것을 의미합니다. 포수가 새로운 물통을 놓았다는 것을 볼 때마다 다른 세포로갑니다. 물론 당신은 가능한 한 오랫동안 피하려고 노력합니다.
그리드
격자는 육각형이지만 육각형 데이터 구조가 없으므로 11 x 11
정사각형 2d 배열을 취하여 고양이가 6 방향으로 만 이동할 수있는 육각형 ‘동작’을 모방합니다.
토폴로지는 환상적입니다. 즉, 어레이의 ‘외부’셀을 밟으면 어레이의 다른쪽에있는 해당 셀로 전송됩니다.
경기
고양이는 그리드의 지정된 위치에서 시작합니다. 포수는 첫 번째 이동을 할 수 있으며, 고양이와 캐처는 고양이가 잡힐 때까지 교대로 움직입니다. 걸음 수는 해당 게임의 점수입니다. 고양이는 가능한 한 높은 점수를 얻으려고 노력하고, 포수는 가능한 한 낮은 점수를 얻으려고 시도합니다. 참여한 모든 게임의 평균 합계가 제출 점수가됩니다. 고양이와 포수를위한 두 가지 등급이 있습니다.
제어 장치
주어진 컨트롤러는 Java로 작성되었습니다. 포수 또는 고양이로서 각각 Java 클래스를 구현하고 (이미 몇 가지 기본 예제가 있음)players
패키지에 하며 컨트롤러 클래스의 고양이 / 포수 목록을 업데이트해야합니다. 해당 클래스 내의 추가 기능. 컨트롤러에는 간단한 고양이 / 캐처 클래스의 두 가지 실제 예제가 제공됩니다.
이 필드는 셀의 현재 상태 값을 저장 하는 11 x 11
2D int
배열입니다. 셀이 비어 0
있으면 값 이 있고, 고양이가 -1
있으면 값이 있고, 버킷이 있으면가 있습니다 1
.
사용할 수있는 몇 가지 기능이 있습니다 : isValidMove()
/isValidPosition()
이동 (고양이) / 위치 (포수)가 유효한지 확인하기위한 것입니다.
차례가 될 때마다 함수 takeTurn()
가 호출됩니다. 이 인수는 현재 그리드의 사본을 포함하며 read(i,j)
에서 셀을 읽는 것과 같은 메소드를 가지고 (i,j)
있습니다.isValidMove()/ isValidPosition()
답의 유효성을 그 검사를. 또한 토 로이드 토폴로지의 랩핑을 관리합니다. 즉, 그리드가 11 x 11 인 경우에도 셀에 액세스 할 수 있습니다 (-5,13).
이 메서드는 int
가능한 이동을 나타내는 두 요소 의 배열을 반환해야 합니다. 고양이 {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}
의 경우 고양이가 가고 싶은 위치의 상대 위치를 나타내며, 포수는 양동이를 놓을 위치의 절대 좌표를 반환합니다 {i,j}
.
분석법이 유효하지 않은 이동을 제출하면 제출이 실격 처리됩니다. 목적지에서 버킷이 이미 있거나 이동이 이미 허용 된 목적지 / 고양이 (고양이) 또는 버킷 / 고양이 (캐처) 인 경우 이동이 유효하지 않은 것으로 간주됩니다. 주어진 기능으로 미리 확인할 수 있습니다.
제출물은 합리적으로 빠르게 작동해야합니다. 각 단계마다 방법이 200ms보다 오래 걸리면 실격 처리됩니다. (바람직하게는 훨씬 적습니다 …)
프로그램은 단계 사이에 정보를 저장할 수 있습니다.
제출물
- 원하는만큼 제출할 수 있습니다.
- 이미 제출 한 제출물을 크게 변경하지 마십시오.
- 각 답변을 새로운 답변으로 작성하십시오.
- 각 제출물에는 고유 한 이름이 있어야합니다.
- 제출물은 수업 코드와 제출 방식을 알려주는 설명으로 구성되어야합니다.
<!-- language: lang-java -->
자동 구문 강조를 얻기 위해 소스 코드에 대한 행을 작성할 수 있습니다 .
채점
모든 고양이 는 모든 포수 와 같은 횟수로 경쟁 합니다. 나는 현재 점수를 자주 업데이트하려고 노력할 것이며, 활동이 감소하면 승자가 결정됩니다.
이 도전은 이 오래된 플래시 게임에서 영감을 얻었습니다.
테스트하고 건설적인 피드백을 준 @PhiNotPi에게 감사합니다.
현재 점수 (페어링 당 100 게임)
Name Score Rank Author
RandCatcher 191962 8 flawr
StupidFill 212688 9 flawr
Achilles 77214 6 The E
Agamemnon 74896 5 The E
CloseCatcher 54776 4 randomra
ForwordCatcher 93814 7 MegaTom
Dijkstra 47558 2 TheNumberOne
HexCatcher 48644 3 randomra
ChoiceCatcher 43834 1 randomra
RandCat 77490 9 flawr
StupidRightCat 81566 6 flawr
SpiralCat 93384 5 CoolGuy
StraightCat 80930 7 CoolGuy
FreeCat 106294 3 randomra
RabidCat 78616 8 cain
Dijkstra's Cat 115094 1 TheNumberOne
MaxCat 98400 4 Manu
ChoiceCat 113612 2 randomra
답변
프리 캣
필드가 변경되지 않으면 3 단계 후 가장 가능한 경로를 제공하는 이동을 선택합니다.
프리 캣 vs 아킬레스 :
package players;
/**
* @author randomra
*/
import java.util.Arrays;
import main.Field;
public class FreeCat implements Cat {
final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
{ 0, -1 }, { 1, -1 } };// all valid moves
final int turnCheck = 3;
public String getName() {
return "FreeCat";
}
public int[] takeTurn(Field f) {
int[] pos = f.findCat();
int[] bestMove = { 0, 1 };
int bestMoveCount = -1;
for (int[] t : turns) {
int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
int moveCount = free_count(currPos, turnCheck, f);
if (moveCount > bestMoveCount) {
bestMoveCount = moveCount;
bestMove = t;
}
}
return bestMove;
}
private int free_count(int[] pos, int turnsLeft, Field f) {
if (f.isValidPosition(pos) || Arrays.equals(pos, f.findCat())) {
if (turnsLeft == 0) {
return 1;
}
int routeCount = 0;
for (int[] t : turns) {
int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
int moveCount = free_count(currPos, turnsLeft - 1, f);
routeCount += moveCount;
}
return routeCount;
}
return 0;
}
}
답변
다이크 스트라의 고양이
그는 마스터의 마스터 알고리즘을 배우고 적용했습니다. 그는 해당 포수 클래스의 일부 메소드에 의존합니다.
Dijkstra ‘s Cat vs Hexcatcher (필요한 업데이트) :
package players;
import main.Field;
import players.Dijkstra; //Not needed import. Should already be available.
/**
* @author TheNumberOne
*
* Escapes from the catcher.
* Uses Dijkstras methods.
*/
public class DijkstrasCat implements Cat{
private static final int[][] possibleMoves = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};
@Override
public String getName() {
return "Dijkstra's Cat";
}
@Override
public int[] takeTurn(Field f) {
int[] me = f.findCat();
int[] bestMove = {-1,1};
int bestOpenness = Integer.MAX_VALUE;
for (int[] move : possibleMoves){
int[] newPos = Dijkstra.normalize(new int[]{me[0]+move[0],me[1]+move[1]});
if (!f.isValidMove(move)){
continue;
}
int openness = Dijkstra.openness(newPos, f, true)[1];
if (openness < bestOpenness || (openness == bestOpenness && Math.random() < .5)){
bestOpenness = openness;
bestMove = move;
}
}
return bestMove;
}
}
그가 일하는 방식 :
그는 자신과 관련하여 보드의 엄격함을 최소화하는 움직임을 찾으려고 노력합니다. 자세한 내용은 해당 포수의 게시물을 참조하십시오.
업데이트 :
그는 이제 물통이 때때로 형성하는 이상한 기하학적 모양을 피합니다.
답변
맥스 캣
Minimax 알고리즘을 구현하려고했습니다. 그러나 제한된 시간으로 인해 성능이 좋지 않습니다. 편집 : 이제 멀티 스레딩을 사용하지만 (내 컴퓨터에서 가장 작음) 깊이를 더 높게 설정할 수 없습니다. 그렇지 않으면 시간 초과가 발생합니다. 코어가 6 개 이상인 PC를 사용하면이 제출이 훨씬 나을 것입니다. 🙂
MaxCat vs Dijkstra :
package players;
import java.util.ArrayList;
import java.util.List;
import main.Field;
public class MaxCat implements Cat {
final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 1, -1 } };
public String getName() {
return "MaxCat";
}
public int[] takeTurn(Field f) {
List<CatThread> threads = new ArrayList<>();
int[] pos = f.findCat();
for (int[] turn : turns) {
if(f.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY){
CatThread thread = new CatThread();
thread.bestMove = turn;
thread.field = new Field(f);
thread.start();
threads.add(thread);
}
}
for (CatThread thread : threads) {
try {
thread.join();
} catch (InterruptedException e) {}
}
int best = Integer.MIN_VALUE;
int[] bestMove = { -1, 1 };
for (CatThread thread : threads) {
if (thread.score > best) {
best = thread.score;
bestMove = thread.bestMove;
}
}
return bestMove;
}
class CatThread extends Thread {
private Field field;
private int[] bestMove;
private int score;
private final int DEPTH = 3;
@Override
public void run() {
score = max(DEPTH, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
int max(int depth, int alpha, int beta) {
int pos[] = field.findCat();
if (depth == 0 || field.isFinished()) {
int moveCount = 0;
for (int[] turn : turns) {
if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY)
moveCount++;
}
return DEPTH-depth + moveCount;
}
int maxValue = alpha;
for (int[] turn : turns) {
if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY) {
field.executeMove(turn);
int value = min(depth-1, maxValue, beta);
field.executeMove(new int[]{-turn[0], -turn[1]});
if (value > maxValue) {
maxValue = value;
if (maxValue >= beta)
break;
}
}
}
return maxValue;
}
int min(int depth, int alpha, int beta) {
if (depth == 0 || field.isFinished()) {
int moveCount = 0;
for (int[] turn : turns) {
int pos[] = field.findCat();
if(field.read(pos[0]+turn[0], pos[1]+turn[1]) == Field.EMPTY)
moveCount++;
}
return -depth - moveCount;
}
int[][] f = field.field;
int minValue = beta;
List<int[]> moves = generateBucketMoves();
for (int[] move : moves) {
f[move[0]][move[1]] = Field.BUCKET;
int value = max(depth-1, alpha, minValue);
f[move[0]][move[1]] = Field.EMPTY;
if (value < minValue) {
minValue = value;
if (minValue <= alpha)
break;
}
}
return minValue;
}
private List<int[]> generateBucketMoves() {
int[][] f = field.field;
List<int[]> list = new ArrayList<>();
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[i].length; j++) {
if (f[i][j] == Field.EMPTY) {
list.add(new int[]{i,j});
}
}
}
return list;
}
}
}
답변
스파이럴 캣
나선형으로 움직입니다. 그것
- 왼쪽 상단 원으로 이동하려고합니다.
- 가능하지 않은 경우 오른쪽 상단으로 이동하십시오.
- 가능하지 않으면 오른쪽 원으로 이동하십시오
- 가능하지 않으면 오른쪽 하단으로 이동하십시오.
- 가능하지 않은 경우 왼쪽 하단 원으로 이동하십시오.
스파이럴 캣 vs 아가멤논 :
package players;
/**
* @author Cool Guy
*/
import main.Field;
public class SpiralCat implements Cat{
public String getName(){
return "SpiralCat";
}
public int[] takeTurn(Field f){
int[][] turns = {{-1,1},{0,1},{1,0},{1,-1},{0,-1},{-1,0}};//all valid moves
int[] move;
int i = -1;
do {
i++;
move = turns[i];
} while(f.isValidMove(move) == false);
return move;
}
}
답변
RabidCat
RabidCat에는 소수성이 있으므로 물통이 무섭습니다. 그는 가장 가까운 것을 찾아 반대 방향으로 달린다.
RabidCat 및 ForwordCatcher :
package players;
import java.util.Random;
import main.Field;
/**
* Run away from water buckets
* @author cain
*
*/
public class RabidCat implements Cat {
public RabidCat() {
}
@Override
public String getName() {
return "RabidCat";
}
@Override
public int[] takeTurn(Field f) {
int[][] directions = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};
//where am I?
int[] position = {0,0};
for(int i = 0; i < 12; i++){
for(int j = 0; j < 12; j++){
if(f.read(i,j) == -1){
position[0] = i;
position[1] = j;
}
}
}
//Find the closest water
int direction = 0;
for(int d = 0; d < 10; d++){
if(f.read(position[0] + d, position[1] - d) == 1 && f.isValidMove(directions[0])){
direction = 1;
break;
}
if(f.read(position[0], position[1] - d) == 1 && f.isValidMove(directions[1])){
direction = 2;
break;
}
if(f.read(position[0] + d, position[1]) == 1 && f.isValidMove(directions[2])){
direction = 3;
break;
}
if(f.read(position[0] - d, position[1]) == 1 && f.isValidMove(directions[3])){
direction = 4;
break;
}
if(f.read(position[0], position[1] + d) == 1 && f.isValidMove(directions[4])){
direction = 5;
break;
}
if(f.read(position[0] - d, position[1] + d) == 1 && f.isValidMove(directions[5])){
direction = 6;
break;
}
}
//If there is no water near, wander
while(direction == 0){
Random rand = new Random();
direction = rand.nextInt(6) + 1;
if(!f.isValidMove(directions[direction - 1])){
direction = 0;
}
}
return directions[direction - 1];
}
}
답변
초이스 캣
가능한 모든 새로운 고양이 위치에 대해 우리는 그 장점을 확인하고 가장 좋은 것을 선택합니다. 양호는 점수를 계산하는 위치보다 고양이 위치에서 더 떨어진 두 개의 가장 좋은 이웃 셀의 기능입니다. 하나는 막을 수 있고 고양이는 도망 가기 위해 하나만 필요하기 때문에 우리는 두 개의 세포만을 사용합니다. 우리의 기능은 하나의 위대하고 다른 하나보다 두 개의 상당히 좋은 세포를 선호합니다. 버킷이있는 위치의 점수는 0이며 가장 빈 셀의 점수는 1입니다.
ChoiceCat은 현재 고양이보다 점수가 더 좋은 것 같습니다.
ChoiceCat 및 ChoiceCatcher :
package players;
/**
* @author randomra
*/
import java.util.Arrays;
import main.Field;
public class ChoiceCat implements Cat {
private class Values {
public final int size;
private double[][] f;
Values(int size) {
this.size = size;
f = new double[size][size];
}
public double read(int[] p) {
int i = p[0];
int j = p[1];
i = (i % size + size) % size;
j = (j % size + size) % size;
return f[i][j];
}
private double write(int[] p, double v) {
int i = p[0];
int j = p[1];
i = (i % size + size) % size;
j = (j % size + size) % size;
return f[i][j] = v;
}
}
final int[][] turns = { { -1, 1 }, { 0, 1 }, { 1, 0 }, { 1, -1 },
{ 0, -1 }, { -1, 0 } };// all valid moves CW order
final int stepCheck = 5;
public String getName() {
return "ChoiceCat";
}
public int[] takeTurn(Field f) {
int[] pos = f.findCat();
int[] bestMove = { 0, 1 };
double bestMoveValue = -1;
for (int[] t : turns) {
int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
double moveValue = movePosValue(currPos, f);
if (moveValue > bestMoveValue) {
bestMoveValue = moveValue;
bestMove = t;
}
}
return bestMove;
}
private double movePosValue(int[] pos, Field f) {
Values v = new Values(f.SIZE);
for (int ring = stepCheck; ring >= 0; ring--) {
for (int phase = 0; phase < 2; phase++) {
for (int sidepos = 0; sidepos < Math.max(1, ring); sidepos++) {
for (int side = 0; side < 6; side++) {
int[] evalPos = new int[2];
for (int coord = 0; coord < 2; coord++) {
evalPos[coord] = pos[coord] + turns[side][coord]
* sidepos + turns[(side + 1) % 6][coord]
* (ring - sidepos);
}
if (phase == 0) {
if (ring == stepCheck) {
// on outmost ring, init value
v.write(evalPos, -1);
} else {
v.write(evalPos, posValue(evalPos, v, f));
}
} else {
// finalize position value for next turn
v.write(evalPos, -v.read(evalPos));
}
}
}
}
}
return -v.read(pos);
}
private double posValue(int[] pos, Values v, Field f) {
if (f.read(pos[0], pos[1]) == Field.BUCKET) {
return 0;
}
int count = 0;
double[] product = new double[6];
for (int[] t : turns) {
int[] tPos = new int[] { pos[0] + t[0], pos[1] + t[1] };
if (v.read(tPos) > 0) {
product[count] = 1 - 1 / (v.read(tPos) + 1);
count++;
}
}
Arrays.sort(product);
double fp = 1;
for (int i = 0; i < Math.min(count,2); i++) {
fp *= product[5-i];
}
double retValue = Math.min(count,2) + fp;
return -retValue;
}
}
답변
바보 고양이
이것은 컨트롤러 테스트를 위해서만 만들어졌습니다. 고양이는 가능할 때마다 오른쪽으로 움직이고, 그렇지 않으면 임의의 방향으로 움직입니다.
package players;
import main.Field;
public class StupidRightCat implements Cat{
public String getName(){
return "StupidRightCat";
}
public int[] takeTurn(Field f){
int[][] turns = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};//all valid moves
int[] move;
if(f.isValidMove(turns[3])){
return turns[3];
} else {
do {
move = turns[(int) (turns.length * Math.random())];
} while(f.isValidMove(move)==false);
return move;//chose one at random
}
}
}