본문으로 건너뛰기

23.05.16.

Today I learned

컴공실

컴공실

tetris project third week

먼저 전체탐색(브루트포스)방식으로 구현해본다.
현재블록을 트리의 root로 설정하여 level2는 다음블록, level3은 다다음 블록이 오게 한다.
다음 블록에서 회전, 위치를 고려하여 가능한 모든 경우의 수를 탐색하고, 이를 재귀호출해 다다음블록에 대해서도 똑같이 수행하게 한다.
level3에 다다르면 해당경우의 점수를 최대점수와 비교하고 갱신한다.
최대점수를 갖는 노드를 추천한다.

문제점

더 먼 미래까지 볼 수있다면 더 좋은 추천알고리즘을 만들 수 있다. 하지만 이는 많은 시공간 복잡도를 요구한다.
예를들어 회전, 위치를 고려한 최대 경우의 수는 36가지, 다다다음블록까지 예측해본다고하면, 이는 36^3의 시간복잡도를 요구한다.
이를 개선할 방법엔 뭐가 있을까?

해결방안

가지자르기
낮은 점수대의 가지들을 자른다. 하지만 이는 최대점수를 가진 가지를 자를 수있는 단점을 가진다.
단순화
트리의 높이만을 기억하게 하여 공간복잡도를 줄인다. 하지만 이는 빈 구멍등의 데이터손실을 야기한다.
유전 알고리즘
내가 생각한 최선책은, 구현 가능한지는 모르겠지만 가중치를 활용한 유전 알고리즘이다.
트리를 만들지 않고 다음블록에 대해, 위치했을때 발생하는 변수들에 가중치를 부여하여 최대점수를 기대할 수있는 상황을 찾는다.
빈 구멍, 높이들의 표준편차, 최대높이, 가장 높은 높이에서의 빈칸의 갯수들에 +-가중치를 부여하여 가장 높은 가중치를 갖는 상황을 선택한다. 여러번의 실행을 통해 최적의 가중치가 무엇인지를 찾는다.

//recommend를 그린다
void DrawRecommend() {
    int i;
    for (i = 0; i < HEIGHT - 1; i++) {
        if (!CheckToMove(field, nextblock[0], blockRotate, i, blockX)) {//drawshadow와 똑같이 구현
            DrawBlock(i - 1, blockX, nextblock[0], blockRotate, 'R');
            break;
        }
    }
}

int recommend(RecNode* root) {
    int i,j,k,l=0;
    constructTree(root);
    DrawRecommend();
}

void constructTree(root) {
    RecNode* node = (RecNode*)malloc(sizeof(RecNode));
    for (i = 0; i < blockAbleRotate[nextblock[0]]; i++) {//중복되는 경우 제외 모든 회전
        for (j = 0; j < WIDTH - 1; j++) {//모든 위치
            for (k = 0; k < HEIGHT - 1; k++) {
                if (!CheckToMove(field, nextBlock[0], i, k, j)) {//위치시키기
                    if (lv == 2) {//lv 2에 도달하면 최댓값과 비교 후 갱신
                        if (best->score < root->score) best = root;
                    }
                    else {//lv 2가 아니라면 lv2로,이동
                        node->score = root->score + AddBlockToField(field,i,k-1,j);
                        node->lv = root->lv + 1;
                        root->c[l++] = node;
                        constructTree(node);
                        removeBlockTofield(field, i, k - 1, j);
                    }
                }
            }
        }
    }
}

//AddBlockToField로 채워진 필드 초기화
void removeBlockToField(char f[HEIGHT][WIDTH], int currentBlock, int blockRotate, int blockY, int blockX) {
    // user code
    int i, j;
    for (i = 0; i < 4; i++) {
        for (j = 0; j < 4; j++) {
            if (block[currentBlock][blockRotate][i][j]) {
                if (0 <= i + blockY && i + blockY < HEIGHT && 0 <= j + blockX && j + blockX < WIDTH) {
                    f[i + blockY][j + blockX] = 0;
                }
            }
        }
    }
}

어림도 없지 segmentation fault.
내일 수정하는걸로..

컴공실
전체탐색 recommend 구현해보기