TeamMatch 프로젝트 문제해결 1[ 밸런스 알고리즘 ]

밸런스 알고리즘 구현해보기 

해당 프로젝트는 리그 오브 레전드 에서 팀 밸런스를 맞추기 위한 알고리즘을 구현한 것입니다. 이 게임에서는 각 팀에 특정 포지션(탑, 정글, 미드, 원딜, 서폿)이 존재하며 플레이어의 랭크 점수(RankScore) 를 기준으로 두 팀을 최대한 균등하게 나누는 것이 중요합니다.

밸런스를 맞추기 위해 다음 요소들을 고려했습니다:

1. 포지션 균형: 각 팀에 모든 포지션이 골고루 배치되도록 함.
2. 점수 차 최소화: 두 팀 간의 총 점수 차이를 최소화하여 게임 밸런스를 유지.
3. 랜덤성과 공정성: 플레이어를 랜덤으로 섞어 배정 과정에서의 편향성을 줄임

랭크?

•  해당 게임에는 총 10단계의 랭크 시스템이 존재한다.
• 각 랭크는 단계별로 구성되며 4단계 부터 1단계 까지 존재한다. 예를들어 아이언1단계에서 특정 LP 조건을 만족하면 다음 단계인 브론즈 4단계 티어로 승급하는 시스템을 갖추고 있다.
• 팀프로젝트 때 얘기가 나온건 각 랭크별로 우리만의 알고리즘을 통해 랭크별로 점수를 부여하였다.

 

밸런스 알고리즘을 구현하기 위해 엑셀로 각 티어단계별 점수를 임의적으로 적용

   

---

라인?

•  탑/정글/미드/원딜/서폿 총 5개의 라인이 존재하며 포지션별로 각자의 역할과 수행목표가 존재함
• 게임에서의 포지션 중요성은 티어가 높은 유저일수록 정글의 실력이 크면 게임이 초반에 무너질 가능성이 존재
• 해당 포지션별 중요도를 정하고 각 특정 포지션의 경우 가중치 점수를 적용하였습니다.
• 다이아티어 4단계 유저가 탑일경우 34 + 3 이라는 점수를 부여받아서 총 해당 유저의 점수는 37점이 되게 된다.

 

---

데이터 전달

• 프론트는 포지션과 팀원을 10명을 배치하여 서버쪽으로 다음과 같이 데이터를 넘겨주도록 하였다.

{
  "mode": "blance",
  "players": [
    { "id": 1, "gameName": "test1", "RankScore": 10, "position": "top" },
    { "id": 2, "gameName": "test2", "RankScore": 15, "position": "top" },
    { "id": 3, "gameName": "test3", "RankScore": 20, "position": "jug" },
    { "id": 4, "gameName": "test4", "RankScore": 18, "position": "jug" },
    { "id": 5, "gameName": "test5", "RankScore": 12, "position": "mid" },
    { "id": 6, "gameName": "test6", "RankScore": 22, "position": "mid" },
    { "id": 7, "gameName": "test7", "RankScore": 14, "position": "ad" },
    { "id": 8, "gameName": "test8", "RankScore": 17, "position": "ad" },
    { "id": 9, "gameName": "test9", "RankScore": 13, "position": "sup" },
    { "id": 10, "gameName": "test10", "RankScore": 19, "position": "sup" }
  ]
}

 

 

 

• 문제: 플레이어 데이터를 기반으로 팀을 구성하려 할 때, 각 팀에 동일한 포지션이 2개 이상 들어가면 안 된다.
• 조건:
  • 10명의 플레이어 데이터를 기준으로 팀을 5명씩 나눈다.
  • 각 팀에는 탑, 정글, 미드, 원딜, 서폿 포지션이 1개씩만 존재해야 한다.
• 제약 사항: 포지션이 중복될 경우, 팀의 밸런스가 깨질 수 있다.

 해결 방법에 대한 고민

• 첫 번째 고민: 무작위로 나누는 방식은 포지션 중복을 방지하기 어려움.
• 두 번째 고민: 데이터를 포지션별로 그룹화하여, 각 팀에 1명씩 배치하면 어떨까?

• filter 를 사용해서 해당 포지션값에 해당하는 플레이어들만 묶어서 출력을 해보았다.
• 이렇게 하면 포지션이 순서대로 넘어오지 않더라도 포지션별로 그룹화를 진행할 수 있어서 좋았던거 같다.

  // 포지션별로 데이터를 그룹화
const groupedPlayers = {
  top: players.filter(player => player.position === "top"),
  jug: players.filter(player => player.position === "jug"),
  mid: players.filter(player => player.position === "mid"),
  ad: players.filter(player => player.position === "ad"),
  sup: players.filter(player => player.position === "sup")
};

console.log(groupedPlayers);

 

 

 

• 해당 그룹에서 포지션별로 각 팀에서 한명씩 가져가면 해당 배열에서 제거되고 각 팀별로 5명씩 구성이 된다.
• read팀에서 먼저 해당 포지션에 있는 유저 한명을 가져가면 그룹에서 두명에서 한명으로 바뀌게 되는 것이다. 
• 블루쪽은 자연스럽게 남은 한명을 가져가게 된다.

// 랜덤으로 팀 구성 함수
function getRandomPlayer(positionGroup) {
  const randomIndex = Math.floor(Math.random() * positionGroup.length);
  return positionGroup.splice(randomIndex, 1)[0]; // 선택된 플레이어 반환 후 배열에서 제거
}

// 팀 구성
const redTeam = [
  getRandomPlayer(groupedPlayers.top),
  getRandomPlayer(groupedPlayers.jug),
  getRandomPlayer(groupedPlayers.mid),
  getRandomPlayer(groupedPlayers.ad),
  getRandomPlayer(groupedPlayers.sup)
];

const blueTeam = [
  getRandomPlayer(groupedPlayers.top),
  getRandomPlayer(groupedPlayers.jug),
  getRandomPlayer(groupedPlayers.mid),
  getRandomPlayer(groupedPlayers.ad),
  getRandomPlayer(groupedPlayers.sup)
];

---

어려웠던 점

• 데이터의 랜덤성을 유지하는 것이 어렵다
  • 초기엔 포지션을 랜덤으로 배치하려고 했지만, 동일한 포지션이 겹치지 않게 하는 제약 때문에 생각보다 복잡해졌다.

 

---

최종 밸런스 매칭 코드

// 밸런스 섞기
const balanceTeams = (players) => {
  // 포지션별 점수 -> 정글-미드-원딜-탑-서폿
  const positionPoints = { jug: 5, mid: 4, ad: 3, top: 2, sup: 1 };

  // 포지션별 그룹화
  const positionPlayers = {
    jug: [],
    mid: [],
    ad: [],
    top: [],
    sup: [],
  };

  // 선수 데이터 새로 복사하고 랜덤 섞기
  const shuffledPlayers = [...players]; // 원본을 변경하지 않기 위해 복사
  shufflePlayers(shuffledPlayers);

  // 복사된 선수들을 포지션별로 분류
  shuffledPlayers.forEach((player) => {
    positionPlayers[player.position].push(player);
  });

  // 각 포지션별로 점수 추가
  for (const position of Object.keys(positionPoints)) {
    const playersInPosition = positionPlayers[position];

    // rankScore가 20 이상인 선수만 점수 추가
    playersInPosition.forEach((player) => {
      if (player.RankScore >= 20) {
        player.RankScore += positionPoints[position];
      }
    });
  }

  // 점수 기준으로 내림차순 정렬
  shuffledPlayers.sort((a, b) => b.RankScore - a.RankScore);

  // 두 팀으로 균등 분배 (각 팀에 5명씩)
  const teams = [
    { players: [], totalRankScore: 0 },
    { players: [], totalRankScore: 0 },
  ];

  // 포지션 순서대로 팀에 분배
  const positionOrder = ["top", "jug", "mid", "ad", "sup"];

  // 각 포지션에서 한 명씩 배정
  positionOrder.forEach((position) => {
    const team1Player = positionPlayers[position].shift();
    const team2Player = positionPlayers[position].shift();

    // 점수가 적은 팀에 배정
    if (team1Player) {
      teams[0].players.push(team1Player);
      teams[0].totalRankScore += team1Player.RankScore;
    }
    if (team2Player) {
      teams[1].players.push(team2Player);
      teams[1].totalRankScore += team2Player.RankScore;
    }
  });

  // 나머지 선수들 균등 배정
  let remainingPlayers = [].concat(...Object.values(positionPlayers));
  remainingPlayers = shufflePlayers(remainingPlayers);

  // 남은 선수들을 순차적으로 팀에 추가
  remainingPlayers.forEach((player) => {
    if (teams[0].players.length < 5) {
      teams[0].players.push(player);
      teams[0].totalRankScore += player.RankScore;
    } else if (teams[1].players.length < 5) {
      teams[1].players.push(player);
      teams[1].totalRankScore += player.RankScore;
    }
  });

  // 클라이언트로 전달할 때 탑 -> 정글 -> 미드 -> 원딜 -> 서폿 순으로 정렬
  const sortPositionClient = (team) => {
    const positionOrder = ["top", "jug", "mid", "ad", "sup"];
    return positionOrder
      .map((position) => {
        return team.players.filter((player) => player.position === position);
      })
      .flat();
  };

  // 각 팀의 포지션 순서대로 정렬 후 전달
  const blueTeam = sortPositionClient(teams[0]);
  const redTeam = sortPositionClient(teams[1]);

  return {
    blueTeam: {
      players: blueTeam,
      totalRankScore: teams[0].totalRankScore,
    },
    redTeam: {
      players: redTeam,
      totalRankScore: teams[1].totalRankScore,
    },
  };
};
// 선수 랜덤 섞기
const shufflePlayers = (arr) => {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]]; // 요소를 교환
  }
  return arr;
};

 

응답데이터

{
    "message": "밸런스 팀 생성 완료",
    "redTeam": {
        "players": [
            {
                "id": 2,
                "gameName": "test2",
                "RankScore": 15,
                "position": "탑"
            },
            {
                "id": 4,
                "gameName": "test4",
                "RankScore": 18,
                "position": "정글"
            },
            {
                "id": 6,
                "gameName": "test6",
                "RankScore": 26,
                "position": "미드"
            },
            {
                "id": 8,
                "gameName": "test8",
                "RankScore": 17,
                "position": "원딜"
            },
            {
                "id": 10,
                "gameName": "test10",
                "RankScore": 19,
                "position": "서폿"
            }
        ],
        "totalRankScore": 95
    },
    "blueTeam": {
        "players": [
            {
                "id": 1,
                "gameName": "test1",
                "RankScore": 10,
                "position": "탑"
            },
            {
                "id": 3,
                "gameName": "test3",
                "RankScore": 25,
                "position": "정글"
            },
            {
                "id": 5,
                "gameName": "test5",
                "RankScore": 12,
                "position": "미드"
            },
            {
                "id": 7,
                "gameName": "test7",
                "RankScore": 14,
                "position": "원딜"
            },
            {
                "id": 9,
                "gameName": "test9",
                "RankScore": 13,
                "position": "서폿"
            }
        ],
        "totalRankScore": 74
    }
}

---

단계별 코드 분석

 

1. 포지션별 점수 가중치 부여

•  -  이 가중치는 팀 밸런스를 맞추기 위해 RankScore에 추가할 점수

const positionPoints = { jug: 5, mid: 4, ad: 3, top: 2, sup: 1 };

 

2. 플레이어 섞기 (shufflePlayers)

•    -  처음엔 팀을 무작위로 섞어주기 순서대로 나누거나 정렬할 경우 한팀에만 잘하는 유저들이 분포될 수 있음

const shuffledPlayers = [...players];
shufflePlayers(shuffledPlayers);

 

3. 포지션별 그룹화

•  - 포지션이 겹치지 않게 그룹화하기

shuffledPlayers.forEach((player) => {
  positionPlayers[player.position].push(player);
});

 

4. 포지션 순서대로 팀 배정

•  - 점수가 적은 팀에 우선적으로 배정하면서 두팀의 점수 차이를 최소화 하기

positionOrder.forEach((position) => {
  const team1Player = positionPlayers[position].shift();
  const team2Player = positionPlayers[position].shift();

  if (team1Player) {
    teams[0].players.push(team1Player);
    teams[0].totalRankScore += team1Player.RankScore;
  }
  if (team2Player) {
    teams[1].players.push(team2Player);
    teams[1].totalRankScore += team2Player.RankScore;
  }
});

 

5. 남은 선수 팀 배정

remainingPlayers.forEach((player) => {
  if (teams[0].players.length < 5) {
    teams[0].players.push(player);
    teams[0].totalRankScore += player.RankScore;
  } else if (teams[1].players.length < 5) {
    teams[1].players.push(player);
    teams[1].totalRankScore += player.RankScore;
  }
});

 

---

코드의 강점

• 점수 차이를 최소화: 플레이어 점수를 기준으로 균등 분배를 진행하여, 두 팀 간 점수 차이가 최대한 적도록 설계했습니다.
• 포지션 겹침 방지: 각 포지션에서 한 명씩 배정하여, 게임 밸런스를 해치지 않도록 했습니다.
• 확장 가능성: 가중치나 팀 배정 방식을 쉽게 변경할 수 있어, 다른 요구 사항에 맞게 조정하기 용이합니다.
• 랜덤성과 공정성 보장: 플레이어를 무작위로 섞고, 점수 및 포지션 기준으로 배정하여 편향성을 방지했습니다.

개선 방향 및 목표

1. 사용자 피드백 기반 데이터 수집
   • 이 프로그램을 사용하는 유저들에게 추가적인 데이터와 피드백을 받아 현재 점수 시스템의 한계를 보완하고 개선 방향을 찾습니다.
   • 다양한 유저의 플레이 스타일과 의견을 반영해 밸런스를 보다 정교하게 조정합니다.
2. 다양한 플레이 스타일 반영
   • 현재는 단순히 티어별 점수를 기준으로 밸런스를 평가하고 있지만 유저들의 플레이 스타일에 따라 점수를 조정할 필요가 있습니다.
   • 예를 들어:
     • 특정 챔피언 하나만 잘 다루는 유저: 해당 챔피언에 대한 높은 숙련도로 티어를 유지하는 경우
     • 다양한 챔피언을 다루며 지능적으로 플레이하는 유저: 특정 챔피언에 의존하지 않고 전반적으로 실력을 발휘해 티어를 올리는 경우.
3. 지속적인 업데이트
   • 수집한 데이터와 유저 피드백을 바탕으로 점수 시스템과 밸런스 알고리즘을 주기적으로 업데이트합니다.
   • 이를 통해 유저들이 프로그램을 사용할수록 점점 더 공정하고 만족스러운 결과를 얻을 수 있도록 개선합니다.

---

기대 효과

• 다양한 유저의 플레이 스타일을 반영한 맞춤형 밸런스 제공
• 유저 피드백을 바탕으로 점진적으로 발전하는 시스템 구축
• 단순한 티어별 점수 배정 방식을 넘어 실제 실력을 보다 정확히 반영