[kotlin] 돌려돌려 돌림판~ 룰렛 게임 구현하기

📌 서론

 룰렛 게임을 한 번쯤 해본 적이 있을 것이다. 빙글빙글 돌아가는 원판에는 구역별로 상품이 걸려있고 돌아가는 원판이 속도를 잃을 때쯤 멈추는 곳의 당첨 막대가 가리키는 상품을 얻게 된다.

이런 룰렛 게임을 코드로 구현하려면 어떻게 해야할까? 필자는 백엔드 개발자이기에 UI를 그리는 것보단 어떤 원리에 의해 상품이 당첨되는지 초점을 두게 됐다. 만약 원판이 여섯 개의 구역으로 나뉘어 있다면 각각 1/6의 당첨확률을 가진다고 생각할 수 있다. 하지만 세상일이 원래 생각대로 되던가요? 좋은 상품은 항상 빗나가고 상대적으로 값어치가 떨어지는 상품만 자주 걸리는 게 차가운 자본주의의 현실이다 like 윤루카스. 프로그램으로 구현된 룰렛 게임은 각 구역의 당첨확률을 세팅할 수 있기에 값어치가 높은 상품보단 그렇지 않은 상품이 더 빈번히 당첨될 수 있다.

출처 : 플랫티콘

 

이번 포스팅에서는 각각의 구역(상품)이 서로 다른 당첨확률을 가지는 룰렛을 코드로 구현하는데 의의를 둔다. 추가적으로 각각의 구역은 서로 다른 수량을 지닌다. 앞으로는 이 수량을 `재고`라 칭하겠다. 예를들어 룰렛이 여섯 개의 구역으로 구성된다면 여섯 개의 구역은 각기 다른 재고와 당첨확률을 보유한 셈이다. 때문에 당첨확률이 높은 구역의 아이템이 먼저 소진되고, 당첨확률이 낮은 구역의 아이템은 비교적 늦게 재고가 소진 될 것이다.

 

 

📌 요구사항 및 고려사항

아이템(score)	확률	재고
10	0.5	40
50	0.3	30
100	0.1	16
500	0.05	8
800	0.03	4
1000	0.02	2

 

룰렛 게임의 요구사항은 아래와 같다

• 당첨될 수 있는 아이템의 수량은 총 100개로 한정한다.
• 각 아이템의 당첨 확률은 위의 표(table)와 같다.
• 즉 룰렛의 실행 횟수 역시 100번으로 제한되며 100번의 플레이 이후에는 룰렛에 남은 아이템 재고가 없어야한다.
• 각각의 재고는 동시성 이슈로부터 자유로워야 한다.
• 전체 아이템의 당첨 확률을 합산하면 1이 된다.
• 특정 아이템의 수량이 모두 소진되면 해당 아이템의 당첨확률을 재고가 소진되지 않은 나머지 아이템에 분배한다.

ex) 10점 아이템 재고 모두 수량 -> 0.5 / 5(남은 아이템 개수) = 0.1 ➡️ 남은 아이템의 확률에 각각 합산 (아래 도표 참조)

 

점수(score)	확률	재고
10	0.5	40
50	0.3 + 0.1 = 0.4	30
100	0.1 + 0.1 = 0.2	16
500	0.05 + 0.1 = 0.15	8
800	0.03 + 0.1 = 0.13	4
1000	0.02 + 0.1 = 0.12	2

 

📌 구현하기

 

기술 스펙
- Kotlin 1.8
- Junit 5.10
- 이번 포스팅에선 별도의 외부 DB 연결없이 메모리 상에서만 룰렛 클래스를 관리한다.

 

우선 룰렛 돌림판을 구성하는 각각의 구역을 코드로 구현해야 한다.

위 요구사항에 따르면 룰렛의 각 구역은 1) 점수(score) 2) 당첨 확률(probability) 3) 재고(stocks) 총 3가지 요소를 갖는다. 이를 코틀린 코드로 표현하면 아래와 같다.

 

각 구역을 코드로 나타내기 - Sector.kt

class Sector(val score: Int, val probability: BigDecimal, var stocks: AtomicInteger) {
    fun decreaseStock() {
        if (stocks.get() > 0) {
            stocks.set(stocks.get() - 1)
        }
    }
}

 

해당 클래스는 3개의 필드와 decreaseStock() 메서드를 갖는다. 룰렛을 한번 돌릴 때마다 최소 하나의 아이템은 당첨되기에 재고의 갯수는 하나씩 차감되야 한다. stocks 필드는 AtomicInteger 로 정의했다. 처음엔 Int 타입으로 선언했지만 동시성을 지켜야 하는 요구사항이 있다. 멀티스레드 환경에서 stocks 를 차감한다면 stocks 필드는 경쟁상태가 되어 데이터 정합성이 맞지 않는 이슈가 발생할 수 있다. 이를 방지하고자 stocks 의 타입은 AtomicInteger 로 변경했다.

 

각각의 Sector 를 Collection 으로 묶어 하나의 룰렛을 만들 수 있다. 필자는 List collection 을 사용하여 최초에 룰렛 게임을 실행하는 상태를 만들었다. (한글명 메서드는 이해를 돕기 위해.. ㅎㅎ)

internal class RouletteUnitTest {
    private fun 룰렛_초기화(): List<Sector> {
        return listOf(
            Sector(10, BigDecimal.valueOf(0.5), AtomicInteger(40)),
            Sector(50, BigDecimal.valueOf(0.3), AtomicInteger(30)),
            Sector(100, BigDecimal.valueOf(0.1), AtomicInteger(16)),
            Sector(500, BigDecimal.valueOf(0.05), AtomicInteger(8)),
            Sector(800, BigDecimal.valueOf(0.03), AtomicInteger(4)),
            Sector(1000, BigDecimal.valueOf(0.02), AtomicInteger(2))
        )
    }
}

 

📌 플레이 과정 구현하기

요구사항을 다시 살펴보자. 까다로운 부분이 하나 있다.

다시보는 요구사항

 

특정 아이템의 재고가 모두 소진되면 해당 아이템의 당첨 확률을 다른 곳으로 재분배 해야한다. 전체 룰렛의 당첨 확률을 1로 유지하기 위해서다.

위 케이스보다 더 간단한 예를 들어보자. 총 3개의 sector 가 있고 각각의 당첨 확률은 20%, 30%, 50% 로 가정한다. 이를 간단히 정수로 표현하면 아래의 이미지와 같다.

 

 

0 에서 9 까지(총 10개의 정수) 랜덤한 정수를 하나 뽑을 때, 당첨된 정수가 속한 범위의 아이템을 받게 되는 것이다. 이미지 상 당첨확률이 높은 아이템 순서대로 영역이 넓은 것을 확인할 수 있다. 이러한 영역이 range 로 간주되며 랜덤으로 뽑은 수가 어떤 range 에 속하는지에 따라 당첨 아이템이 달라진다.

 

 

 

이러한 원리를 룰렛 게임에 적용해보자. 룰렛은 총 6개의 아이템이 있으므로 총 6개의 범위(range)이 생기는 셈이다. 룰렛의 누적 확률 구간을 나타내면 다음과 같은 형태일 것이다.

 

💎 Item 10: 0 < x <= 0.5

💎 Item 50:  0.5 < x <= 0.8

💎 Item 100: 0.8 < x <= 0.9

💎 Item 500: 0.9 < x <= 0.95

💎 Item 800: 0.95 < x <= 0.98

💎 Item 1000: 0.98 < x <= 1

 

0 에서 1 사이의 랜덤한 수를 구하고, 해당 숫자(ex, 0.32)가 속하는 범위에 따라 아이템이 당첨되는 것이다. 이 경우에는 0 < x <= 0.5 에 속하므로 item 10 을 얻게 된다. 0 에서 1 사이의 랜덤한 숫자는 Random 메서드로 간단히 구할 수 있다.

 

 

랜덤 값이 어느 범위에 속하는지에 따라 당첨 아이템이 달라진다.

위 이미지처럼 각 아이템별 누적 당첨확률을 저장하기 위해 1) 아이템의 당첨확률을 차례로 누적하고 2) 누적된 당첨확률을 key로 하여 각 아이템을 할당해야 한다. 필자는 TreeMap 자료구조를 이용해 아이템의 당첨확률을 차례로 누적했다. (TreeMap 을 선택한 이유는 아래에서 다루겠습니다.)

class RouletteGame(val sectorList: List<Sector>) {

    private fun getRouletteProbability(): TreeMap<BigDecimal, Sector> {
        var cumulativeProbability = BigDecimal.ZERO // (a)
        val probabilityMap = TreeMap<BigDecimal, Sector>() // (b)

        this.sectorList
            .forEach { sector ->
                cumulativeProbability = cumulativeProbability.add(sector.probability) // (c)
                probabilityMap[cumulativeProbability] = sector // (d)
            }
        return probabilityMap
    }
}

 

 

(a) 최초의 누적 확률 값은 0 이어야 한다. 각 아이템의 당첨 확률을 이 값에 차례로 누적하게 된다.

(b) 각 누적 확률을 저장할 자료구조를 TreeMap 타입으로 선언하여 key 는  누적확률을, value 는 Sector 인스턴스를 저장한다.

 

(c) sectorList 를 순회하면서 각 Sector 의 당첨확률을 cumlativeProbability 에 차례로 누적한다.

(d) 누적된 당첨확률을 probabilityMap 의 key 로 저장하며 value 엔 Sector 객체를 저장한다.

 

결과적으로 해당 메서드는 probabilityMap 를 반환하여 아이템의 당첨확률을 차례로 누적하고 이를 key로 가지는 객체를 생성했다.

 

 

📌 TreeMap 사용 이유와 구현

 

저장하는 Key에 특별한 순서가 없는 HashMap과 달리 TreeMap은 어떤 규칙에 따라 키를 정렬하여 저장할 수 있다. TreeMap 은 이진 탐색 트리 형태를 활용하기 때문에 정렬된 key 순서로 데이터를 저장할 수 있다. TreeMap 은 키 값에 따라 오름차순으로 자동 정렬되기 때문에 (예를 들어) 0.1, 0.36, 0.05, 0.52 를 key로 저장하면  0.05, 0.1, 0.36, 0.52 순서로 자동 정렬 저장된다. TreeMap 의 이러한 특징을 활용하여 각 Sector 의 당첨확률을 저장하면 정렬된 상태를 유지할 수 있다.

또한 TreeMap 의 내부 코드를 살펴보면 NavigableMap 인터페이스를 상속한 구현체임을 알 수 있는데, NavigableMap 의 higherEntry() 메서드를 이용하여 요구사항을 구현할 수 있다.

 

TreeMap

 

higherEntry() method

 

higherEntry() : 인자로 받은 key 보다 큰 key 중에서 가장 작은 key 를 반환한다.

 

higherEntry()는 NavigableMap 인터페이스에 선언된 추상 메서드로 TreeMap에서 오버라이딩 돼 있다.  

higherEntry() 메서드는 주어진 key 보다 큰 다음(next) key 의 value 를 반환한다. 이 메서드는 특정 key 의 다음 항목을 찾는 데 사용되며 만약 주어진 key 보다 큰 다음 key 를 가진 항목이 없으면 null을 반환한다. 예를 들어 TreeMap 에 저장된 key 중 가장 큰 값이 1일 때 higherEntry(2) 를 호출하면 2 보다 큰 key 를 가진 항목이 없기 때문에 null 을 반환한다. 

 

class RouletteGame(val sectorList: List<Sector>) {


    private fun getResult(sectorMap: TreeMap<BigDecimal, Sector>): Sector {
        val random = Random()
        val randomValue = BigDecimal.valueOf(random.nextDouble())
        return sectorMap.higherEntry(randomValue).value
    }

    private fun getRouletteProbability(): TreeMap<BigDecimal, Sector> {
        var cumulativeProbability = BigDecimal.ZERO
        val probabilityMap = TreeMap<BigDecimal, Sector>()

        this.sectorList
            .forEach { sector ->
                cumulativeProbability = cumulativeProbability.add(sector.probability)
                probabilityMap[cumulativeProbability] = sector
            }
        return probabilityMap
    }
}

 

당첨 결과를 얻기 위해 getResult() 메서드를 선언했다.

해당 메서드는 getRouletteProbability() 를 통해 생성된 TreeMap 을 인자로 받고, 내부에서 Random 숫자를 만들어 higherEntry()  메서드의 인자로 사용한다. higherEntry(randomValue)는 TreeMap의 key 중 randomValue보다 크면서 동시에 가장 근접한 key 를 선택해 반환한다. 예를들어 randomValue 값이 0.55 일 때 0.55 보다 크면서 가장 근접한 값인 0.8을 key 로 갖는 value 를 반환한다. 랜덤 값은 Random 클래스의 nextDouble 메서드를 사용했다. 코틀린 공식 문서에 의하면 nextDouble() 메서드는 0 <= x < 1 범위의 Double 형 값을 반환한다.

 

TreeMap 의 key 가 오름차순으로 저장되는 특징을 활용해 확률map 을 구현할 수 있었다.

 

 

📌 재고 차감을 고려한 확률 연산

요구사항에서 재고 부분을 다시 확인해보자. 총 재고는 100개로 각 아이템의 재고가 모두 소진되면 해당 아이템의 당첨 확률을 다른 아이템에 분배해야 한다. 만약 당첨확률이 0.5인 아이템10 이 모두 소진되면 남은 아이템(5가지 종류)에 확률을 각각 분배해야한다. 이 경우에는 남은 아이템의 갯수가 5개이므로 분배해야 할 확률 값은 0.5 / 5 = 0.1 이 된다. 이를 고려하여 확률 map 을 다시 구현해보자.

class RouletteGame(val sectorList: List<Sector>) {

    private val soldOuts = ConcurrentHashMap<Int, Roulette>()

    private fun getCurrentProbability(): BigDecimal? {
        val sumSoldOutProbability = soldOuts.values
            .stream()
            .map { obj: Roulette -> obj.probability }
            .reduce(BigDecimal.ZERO)
            { obj: BigDecimal, agent: BigDecimal? -> obj.add(agent) }
        val availableSize = rouletteList.size - soldOuts.size
        return sumSoldOutProbability.divide(BigDecimal.valueOf(availableSize.toLong()), 3, RoundingMode.HALF_UP)
    }

    ...
    
}

 

getCurrentProbability() 는 재고가 소진된 아이템의 확률을 다른 아이템에게 재분배 하는 메서드다.

이 때 soldOuts 라는 인스턴스 변수를 활용하여 현재 룰렛 게임에서 재고가 소진된 아이템을 저장한다. 해당 변수는 ConcurrentHashMap<Int, Roulette> 타입으로 솔드 아웃된 아이템을 저장한다.

 

이제 위에서 살펴본 getRouletteProbability() 메서드에 getCurrentProbability() 메서드를 녹여보자. remainProbabiliy 는 아직 재고가 남아있는 아이템에게 분배해줄 확률 값이다. 아직 재고가 남아있는 아이템을 구하기 위해 filter() 를 추가(a)하고, 필터링 된 재고의 아이템에 remainProbability 를 더해준다(b).

class RouletteGame(val rouletteList: List<Roulette>) {

    private val soldOuts = ConcurrentHashMap<Int, Roulette>()
    private val random = Random()
    
    ...
    
    private fun getRouletteProbability(): TreeMap<BigDecimal, Roulette> {
        val remainProbability = getCurrentProbability()
        var cumulativeProbability = BigDecimal.ZERO
        val probabilityMap = TreeMap<BigDecimal, Roulette>()

        this.rouletteList
            .filter { r -> r.stocks.get() != 0 } // (a)
            .forEach { r ->
                val add = r.probability.add(remainProbability) // (b)
                cumulativeProbability = cumulativeProbability.add(add)
                probabilityMap[cumulativeProbability] = r
            }
        return probabilityMap
    }
    
    private fun getCurrentProbability(): BigDecimal? {
        val sumSoldOutProbability = soldOuts.values
            .stream()
            .map { obj: Roulette -> obj.probability }
            .reduce(BigDecimal.ZERO)
            { obj: BigDecimal, agent: BigDecimal? -> obj.add(agent) }
        val availableSize = rouletteList.size - soldOuts.size
        return sumSoldOutProbability.divide(BigDecimal.valueOf(availableSize.toLong()), 3, RoundingMode.HALF_UP)
    }
    
    ...
    
}

 

 

📌 play() 메서드

위에서 언급한 모든 내용을 실행하는 것이 play() 메서드로, 클라이언트가 룰렛을 한번 돌릴 때 호출된다.

getResult() 메서드의 결과로 나온 roulette 값은 당첨된 아이템에 해당되며, 이를 decreaseStock() 메서드의 인자로 호출하여 해당 아이템의 재고를 차감한다. 이 때 해당 아이템(roulette) 의 stocks 가 0이면 soldOut 으로 판단하여  soldOuts concurrentHashMap 에 추가한다.

 

class RouletteGame(val rouletteList: List<Roulette>) {

    private val soldOuts = ConcurrentHashMap<Int, Roulette>()
    private val random = Random()
    
    fun play(): Roulette {
        checkPlayAvailable()
        val rouletteProbability = getRouletteProbability()
        val roulette = getResult(rouletteProbability)
        decreaseStock(roulette)
        return roulette
    }
    
    private fun checkPlayAvailable() {
        if (this.rouletteList.size == this.soldOuts.size) {
            throw IllegalStateException()
        }
    }
    
    private fun getResult(rouletteMap: TreeMap<BigDecimal, Roulette>): Roulette {
        val randomValue = BigDecimal.valueOf(random.nextDouble())
        return rouletteMap.higherEntry(randomValue).value
    }
    
    private fun decreaseStock(roulette: Roulette) {
        roulette.decreaseStock()
        if (roulette.stocks.get() == 0) {
            soldOuts[roulette.score] = roulette
        }
    }
    
    ...
    
}

 

 

📌 결론

 

이렇게 돌려돌려 돌림판을 코드로 구현했다. 소진된 아이템의 확률을 다른 아이템으로 분배하는 요구사항이 까다롭긴 했지만 TreeMap 자료형을 사용하여 해결할 수 있었다. 멀티스레드가 동시에 접근할 수 있는 soldOuts 변수를 concurrentHashMap 타입으로 선언한 덕분에 동시성 관련 문제도 해결할 수 있었다. 동시성 문제에 관한 코드는 테스트 코드로 대체한다.

테스트코드는 아래에서 확인할 수 있다.

 

 

 

📌 테스트 코드

internal class RouletteUnitTest {
    private val initialStock = 100
    private fun 룰렛_초기화(): List<Roulette> {
        return listOf(
            Roulette(10, BigDecimal.valueOf(0.5), AtomicInteger(40)),
            Roulette(50, BigDecimal.valueOf(0.3), AtomicInteger(30)),
            Roulette(100, BigDecimal.valueOf(0.1), AtomicInteger(16)),
            Roulette(500, BigDecimal.valueOf(0.05), AtomicInteger(8)),
            Roulette(800, BigDecimal.valueOf(0.03), AtomicInteger(4)),
            Roulette(1000, BigDecimal.valueOf(0.02), AtomicInteger(2))
        )
    }

    @Test
    @DisplayName("룰렛 게임 플레이 테스트")
    fun playTest() {
        val initialRoulette = 룰렛_초기화()
        val rouletteGame = RouletteGame(initialRoulette)
        for (i in 0 until initialStock) {
            val play = rouletteGame.play()
            if (play.stocks.get() == 0) {
                println(i.toString() + "번째 play: " + play.score + "점 아이템 소진")
            }
        }
        val rouletteList = rouletteGame.rouletteList
        for (roulette in rouletteList) {
            Assertions.assertThat(roulette.stocks.get()).isEqualTo(0)
        }
    }

    @Test
    @DisplayName("플레이 마다 재고는 1씩 차감된다")
    fun stockCountTest() {
        val initialRoulette = 룰렛_초기화()
        val rouletteGame = RouletteGame(initialRoulette)
        val totalStock = rouletteGame.currentTotalStock()
        Assertions.assertThat(totalStock).isEqualTo(initialStock)
        for (i in 1..initialStock) {
            rouletteGame.play()
            val currentStock = rouletteGame.currentTotalStock()
            Assertions.assertThat(currentStock).isEqualTo(initialStock - i)
        }
    }

    @Test
    @DisplayName("재고 없을때 예외를 던진다")
    fun overPlayTest() {
        val initialRoulette = 룰렛_초기화()
        val rouletteGame = RouletteGame(initialRoulette)
        for (i in 1..100) {
            rouletteGame.play()
        }
        Assertions.assertThatThrownBy { rouletteGame.play() }
    }

    @Test
    @DisplayName("스레드 30개 동시성 테스트 - Future")
    @Throws(
        InterruptedException::class,
        ExecutionException::class
    )
    fun multiThreadTest() {
        val initialRoulette = 룰렛_초기화()
        val initialStock = initialRoulette.stream()
            .mapToInt { r -> r.stocks.get() }
            .sum()
        val rouletteGame = RouletteGame(initialRoulette)
        val numThreads = 30
        val executorService = Executors.newFixedThreadPool(numThreads)
        for (i in 0 until numThreads) {
            val future = executorService.submit<Roulette> { rouletteGame.play() }
            future.get()
        }
        executorService.shutdown()
        Assertions.assertThat(initialStock - numThreads)
            .isEqualTo(rouletteGame.currentTotalStock())
    }

    @Test
    @DisplayName("스레드 30개 동시성 테스트 - Thread")
    @Throws(
        InterruptedException::class
    )
    fun multiThreadTestV2() {
        val initialRoulette = 룰렛_초기화()
        val rouletteGame = RouletteGame(initialRoulette)
        val numThreads = 30
        val threads: MutableList<Thread> = ArrayList()
        for (i in 0 until numThreads) {
            val thread = Thread { rouletteGame.play() }
            threads.add(thread)
            thread.start()
        }
        for (thread in threads) {
            thread.join()
        }
        Assertions.assertThat(100 - numThreads).isEqualTo(rouletteGame.currentTotalStock())
    }
}

 

 

📌 그 다음은?

이제 해야 할 일은 크게 2가지로 추려볼 수 있다.

1. 외부 저장소를 연동해서 룰렛을 관리

2. 웹 통신을 이용해 실제 사용자가 룰렛 게임을 할 수 있도록 만드는 것.

 

언제 다음 시리즈를 쓸지는 몰루겠지만 2편에선 외부 저장소를 연동해서 룰렛 정보를 관리하는 법을 다뤄보겠다.

 

---

 

 

github

https://github.com/hugehoo/spring-principle/tree/main/src/main/java/com/spring/principle/examples/roulette

 

 

ref.

https://docs.oracle.com/javase/9/docs/api/java/util/NavigableMap.html

https://tech.socarcorp.kr/dev/2021/10/19/sub-interfaces-navigablemap.html

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.random/-random/