독창 마작 검사 표 판단 후 표 고 효율 저 메모리 알고리즘
76892 단어 마작
34 * 34 * 34（ 34 ） 번 을 하고 차례대로 승 부 를 판정 해 야 한다 고 생각 했다. 이것 은 좋 은 방법 이 아니 라 나중에 야 39304 번 의 순환 에 불과 하 다 는 것 을 깨 달 았 다. 이렇게 오래 걸 리 지 않 을 정도 로 문 제 는 그 가 마작 의 승 부 를 판정 하 는 효율 이 약간 낮 다 는 것 이다.세 개의 독창 의 순환 횟수 를 어떻게 최적화 하고 줄 이 는 지 에 대해 서도 내 생각 이 있다. 어쨌든 나 는 그 에 게 실현 을 시도 하 겠 다 고 약속 했다. 본 고 는 관련 내용 을 정리 하 는 것 이다.내 가 관련 자 료 를 찾 아 보지 않 았 을 때 처음에 나 는 두 가지 생각 이 있 었 다.모든 이 긴 패 를 조합 하여 맵 을 구성 하고 승 패 를 판정 하려 면 표를 검사 하면 됩 니 다. 키 값 은 정렬 하고 연 결 된 string 을 초보 적 으로 구상 합 니 다.
자 료 를 찾 아 보고 Thinkraft 가 대답 하 는 것 이 저 에 게 큰 영향 을 주 었 습 니 다. 왠 지 방법 에 탄복 하지만 효율 이 현저히 향상 되 지 않 았 습 니 다. (여기 서 향상 되 지 않 은 것 이 아니 라 뒤의 테스트 데 이 터 를 참고 할 수 있 습 니 다. 향상 되 는 효율 은 데이터 항목 의 감소 에서 비롯 되 어야 합 니 다) Golang map 에서 알고리즘 을 찾 는 것 이 상당히 효율 적 일 수 있 습 니 다.그럼 에 도 불구 하고 이런 방법 을 사용 하면 메모리 의 점용 을 효과적으로 낮 출 수 있 습 니 다. 제 가 제공 한 소스 코드 를 자세히 보 세 요.
마작 은 모두 34 가지 카드 로 위 키 - mahjong 위 키 - 마작 1 - 9 떡, 1 - 9 개, 1 - 9 만 개, 동, 남, 서, 북, 홍 중, 돈 벌 기, 화이트 보드 (나머지 유형 패 는 본 고의 알고리즘 과 무관 하 므 로 여기 서 토론 하지 않 습 니 다).
var tiles = []byte{
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, // Dots
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, // Bamboo
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, // Characters
0x31, 0x41, 0x51, 0x61, 0x71, 0x81, 0x91, // East South West North Red Green White
}마작 이 이 기 려 면 반드시 4 조 1 쌍 (본 고 는 다른 이 길 가능성 을 고려 하지 않 는 다. 예 를 들 어 7 쌍, 예 를 들 어 1 봉 / 터치 가 존재 하 는 전제 에서 3 조 1 쌍 이 이 길 수 있다). 이 긴 모든 카드 를 조합 하려 면 모든 쌍 과 모든 조 를 찾 아야 한다.네: 모두 34 쌍 입 니 다. 유형 별로 1 쌍 을 취 할 수 있 습 니 다.그룹: 총 34 + (9 - 2) * 3 조, 유형 당 1 조 를 취 할 수 있 습 니 다. 같은 패 조 는 34 조, 떡, 줄기, 만 유형 당 9 - 2 순서 패 조 는 21 조, 총 55 조 입 니 다.
func findPairs() [][]byte {
pairs := make([][]byte, 0, len(tiles))
for _, v := range tiles {
pair := []byte{v, v}
pairs = append(pairs, pair)
}
return pairs
}
func findGroups() [][]byte {
groups := make([][]byte, 0, len(tiles)+(9-2)*3)
// find three identical tiles
for _, v := range tiles {
group := []byte{v, v, v}
groups = append(groups, group)
}
// find three sequence tiles
for i := 2; i < len(tiles); i++ {
if tiles[i-2]+1 == tiles[i-1] && tiles[i-1] == tiles[i]-1 {
group := []byte{tiles[i-2], tiles[i-1], tiles[i]}
groups = append(groups, group)
}
}
return groups
}쉽게 찾 을 수 있 지만 어떻게 조합 하 느 냐 에 대해 저 는 정신 이 없 었 습 니 다. 문 제 는 55 조 에서 34 조 의 같은 패 팀 이 조합 할 때 같은 1 조 에 한 번 밖 에 나타 나 지 않 았 습 니 다. 그러나 다른 21 조 의 순서 패 팀 은 조합 할 때 같은 1 조 에 최대 4 번 (유 저 는 싸 우 고 싶 지 않 습 니 다!) 이 나 올 수 있 고 효율 이 최고 라 고 생각 했 습 니 다.그러나 같은 목록 에 있 는 팀 은 서로 다른 처 리 를 해 야 한다. 나 는 이 55 조 의 목록 을 두 개의 목록 으로 나 누 어 복잡 도가 급증 하고 싶다.마지막 으로 현 재 는 데이터 준비 단계 이 고 어떤 효율 을 고려 해 최종 적 으로 정확 한 결 과 를 얻 는 것 이 왕도 다.폭력 조합 이면 돼!!
이 함 수 를 통 해 손 패 를 검사 하 는 것 이 효과 적 이 고 직접 정렬 하여 쉽게 이해 할 수 있 습 니 다. 나중에 효과 적 인 손 패 는 조만간 정렬 해 야 한 다 는 것 을 알 게 될 것 입 니 다.
func checkValid(win []byte) bool {
sort.Sort(byteSlice(win))
for i := 4; i < len(win); i++ {
if win[i] == win[i-4] {
return false
}
}
return true
}여기 서 명확 한 효율 문제 에 부 딪 힌 것 은 내 가 Golang 표준 창고 의 by tes. Equal () 함 수 를 과대 평가 한 것 이다.composeWin 실행 시간 눈대중 을 1 시간 이상 실행 해 야 합 니 다.그러나 이 를 탓 할 수 없다. 사고 자체 에 문제 가 존재 한다. 조합 결과 가 점점 많아 지면 서 notExist 를 집행 하 는 대가 가 점점 커 질 것 이다.
func notExist(win []byte, wins [][]byte) bool {
for _, v := range wins {
if bytes.Equal(win, v) {
return false
}
}
return true
}
func composeWin(pairs, groups [][]byte) [][]byte {
wins := make([][]byte, 0, 11498658)
tmp := make([]byte, 14)
for _, pair := range pairs {
for _, group1 := range groups {
for _, group2 := range groups {
for _, group3 := range groups {
for _, group4 := range groups {
copy(tmp, pair)
copy(tmp[2:], group1)
copy(tmp[5:], group2)
copy(tmp[8:], group3)
copy(tmp[11:], group4)
if checkValid(tmp) && notExist(tmp, wins) {
win := make([]byte, 0, 14)
win = append(win, tmp...)
wins = append(wins, win)
}
}
}
}
}
}
return wins
}다음 과 같은 방법 을 통 해 같은 이 긴 카드 가 있 는 지 확인 하 는 일 을 골 랑 맵 에 맡 기 고 몇 분 이면 결 과 를 얻 을 수 있 습 니 다.저 는 string 형식 을 사용 하여 map 키 형식 을 만 들 지 않 았 습 니 다. 사실 이 방법 은 string 형식 보다 키 형식 을 만 드 는 것 이 효율 적 이지 않 습 니 다.오히려 코드 를 많이 써 서 복잡 도 를 높 였 고 뒷글 에 테스트 데이터 가 있 을 것 이다.
type twoUint64 struct {
H uint64 // High
L uint64 // Low
}
func composeWinEx(pairs, groups [][]byte) map[twoUint64][]byte {
wins := make(map[twoUint64][]byte)
var key twoUint64
tmp := make([]byte, 14)
for _, pair := range pairs {
for _, group1 := range groups {
for _, group2 := range groups {
for _, group3 := range groups {
for _, group4 := range groups {
copy(tmp, pair)
copy(tmp[2:], group1)
copy(tmp[5:], group2)
copy(tmp[8:], group3)
copy(tmp[11:], group4)
if checkValid(tmp) {
key.H = uint64(tmp[0])
key.L = uint64(tmp[6])
for _, v := range tmp[1:6] {
key.H = key.H<<8 + uint64(v)
}
for _, v := range tmp[7:] {
key.L = key.L<<8 + uint64(v)
}
if _, ok := wins[key]; !ok {
win := make([]byte, 0, 14)
win = append(win, tmp...)
wins[key] = win
}
}
}
}
}
}
}
return wins
}다음은 Thinkraft 가 제시 한 일본 인의 알고리즘 을 설명 합 니 다. 독자 들 은 Thinkraft 의 대답 과 일본 인 이 발표 한 글 을 최대한 읽 어 주 십시오. 저 는 이해 하기 어 려 운 부분 에 만 보충 합 니 다.
이 긴 패 를 판정 할 때 는 두 가 지 를 주의해 야 한다.
예 를 들 어 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 3, 4, 2, 3, 3, 3, 4, 4, 4, 5, 5 순 위 를 매 긴 두 조수 카드 가 모두 이 기 는 것 을 보 여 준다. 이들 은 매우 비슷 한 지, 이런 이 기 는 유형 을 어떻게 요약 하 는 지, Thinkraft 는 이 를 패 형 이 라 고 부른다.
같은 패 의 수 를 계산 하고 연속 하면 같은 패 의 수 를 계속 계산 하 며, 연속 되 지 않 으 면 중간 에 숫자 0 으로 나 누 기 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 - > 3 4 4 (2 3 연속) 1 1 1 1 1 2 2 2 2 2 2 2 3 3 4 4 4 4 4 - > 3 4 4 3 4 4 4 4 3 (3 4 연속) 동 리 를 얻 을 수 있다.
1 1 1 2 3 4 6 7 8 동서 서 1 1 1 1 1 1 - > 3 1 1 1 2 - > 3 1 (1 2 연속) 1 1 2 3 - > 3 1 1 1 (2 3 연속) 1 1 1 2 3 4 - > 3 1 1 1 2 3 4 6 - > 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 6 7 - > 31, 1, 2, 3, 4, 6, 7, 8 동 동 동 동 - > 3, 1, 1, 0, 1, 1, 1, 2, 3, 3, 4, 6, 7, 8 동 동 동서 서 - > 3, 1, 1, 1, 1, 1, 1, 1, 0, 3, 3, 3, 1, 1, 0, 3, 3, 1, 1, 1, 0, 3
동 리 는 1, 2, 3, 5, 6, 7, 1, 2, 3, 5, 6, 7, 서 - > 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 2.
다음은 이 진 화 를 다음 과 같은 규칙 으로 1 - > 0 2 - > 1, 1, 0, 3 - > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10 - > 1, 1, 1, 0, 30 - > 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1숫자 1, 2, 3, 4 는 각각 같은 패 의 수량 을 나타 낸다. 예 를 들 어 규칙 에서 4 또는 40 은 같은 패 4 장 (이 같은 패 와 뒤의 연속 만 구별 되 는 지) 을 나타 내 고 인 코딩 후의 길 이 는 각각 7 비트 (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7 / 4 = 1.75, 8 / 4 = 2 이기 때문에 카드 당 1 ~ 2 비트 의 바 이 너 리 공간 만 차지한다.
Thinkraft 의 대답 댓 글 에서 개 선 된 호 프 만 인 코딩 이 라 고 생각 하 는 사람 이 있 습 니 다. 호 프 만 인 코딩 을 배 워 보 겠 습 니 다.위 키 - Huffman 위 키 호 프 만 이 호 프 만 인 코딩 에 따라 인 코딩 을 한다 면 오히려 14 장의 카드 데 이 터 를 int 32 에 저장 하 는 것 을 보장 할 수 없습니다. 여기 서 추론 합 니 다.
비로소 같은 패 의 수량 을 계산 하고 연속적으로 0 으로 분할 하지 않 으 면 모두 0, 1, 2, 3, 4 다섯 가지 문자 가 나타난다. 대략적인 통계 출현 횟수 는 다음 과 같다 [4: 2755728 2: 14386266 3: 26038905 0: 34871796 1: 43069053].호 프 만 인 코딩 4 - > 0 0 0 2 - > 0 0 1 3 - > 0 1 0 - > 1 0 1 - > 1 1 을 받 게 됩 니 다.
그 다음 에 이 부분 은 원작 자의 알고리즘 에서 약간 벗 어 났 습 니 다. 주로 저 는 일본 어 를 읽 지 못 하고 원작 자의 처리 에 대해 잘 이해 하지 못 했 습 니 다. 마침 Thinkraft 는 여기 서 자세히 말 하지 않 았 습 니 다. 저 는 Thinkraft 대답 에 댓 글 을 추가 하여 제 의문 을 설 명 했 습 니 다. 관심 이 있 는 친 구 는 가서 볼 수 있 습 니 다. 제 아 이 디: 장성 초, 제3 0 조 댓 글 입 니 다.
사실 이론 은 이미 명확 하 게 밝 혀 졌 다. 원작 자가 어떻게 생각 하 든내 가 이렇게 바 이 너 리 로 돌 리 는 건 항상 틀 리 지 않 아. 2, 2, 3, 3, 4, 5, 5. - > 3, 4, 4, 3, 3, 3. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1 1 1 2 3 4 6 7 8 동 동서 서 - > 3 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 3 2 - > 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 2 - > 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1고위 보 1 은 더 나 아가 모든 효과 적 인 바 이 너 리 위 치 를 유지 합 니 다. 예 를 들 어 프로그램 이 이상 하면 [2, 3, 5, 6, 7 서쪽] 으로 int 32 함 수 를 호출 하면 얻 은 int 32 수 치 는 위의 것 과 일치 하여 프로그램 이 실 수 를 판정 할 것 입 니 다.
다음은 제 가 실현 한 위 에서 말 한 논 리 는 논 리 를 간소화 하기 위해 저 는 0 으로 분할 하지 않 았 습 니 다. 저 는 분할 할 곳 의 숫자 가 직접 + 10 입 니 다. 그러면 원작 자 는 저 와 다음 과 같 습 니 다. 1 - > 1 (0x 01) 2 - > 2 (0x 02) 3 - > 3 (0x 03) 4 - > 4 (0x04) 10 - > 11 (0x0B) 20 - > 12 (0x0C) 30 - > 13 (0x0D) 40 - > 14 (0x0E)이렇게 하면 뒤의 switch 논 리 를 편리 하 게 하고 선명 하 게 할 수 있 습 니 다.
func bytesToInt(win []byte) int {
tmp := make([]byte, 0, 17)
tmp = append(tmp, 1)
for i, pos := 1, 0; i < len(win); i++ {
if win[i-1] == win[i] {
tmp[pos]++
} else if win[i-1]+1 == win[i] {
tmp = append(tmp, 1)
pos++
} else {
tmp = append(tmp, 1)
tmp[pos] += 0x0A
pos++
}
}
res := 1
for _, v := range tmp {
switch v {
case 0x01:
res <<= 1
case 0x02:
res <<= 3
res |= 0x06
case 0x03:
res <<= 5
res |= 0x1E
case 0x04:
res <<= 7
res |= 0x7E
case 0x0B:
res <<= 2
res |= 0x02
case 0x0C:
res <<= 4
res |= 0x0E
case 0x0D:
res <<= 6
res |= 0x3E
case 0x0E:
res <<= 8
res |= 0xFE
}
}
return res
}다음은 스트레스 테스트 결 과 를 보 여 드 리 겠 습 니 다. 테스트 환경 을 걱정 하지 마 세 요. 기본 적 인 랜 덤 피 드 는 똑 같은 카드 기준 1000000 번 과 세 개의 독창 자 1000 번 의 승 패 를 거 쳤 습 니 다. 이 기 는 횟수 를 통계 하고 시간 int 알고리즘 을 통계 할 것 입 니 다.
Test total 10000000, Win 30, Time 59.662091651s
Test total 1000, Win 8, Time 20.836001166stwo uint 64 알고리즘
Test total 10000000, Win 30, Time 1m22.517894824s
Test total 1000, Win 8, Time 24.289389045sstring 알고리즘
Test total 10000000, Win 30, Time 1m26.392626271s
Test total 1000, Win 8, Time 24.320570688s이때 그것들의 효율 은 이미 차이 가 매우 적다. 네가 어떻게 사용 하 느 냐 에 달 려 있다. 여기 서 한 가 지 를 제시한다. 어쨌든 int 알고리즘 은 메모리 에서 가장 적은 알고리즘 을 차지한다. 알고리즘 을 사용 하지 않 고 int 로 전환 할 때 메모 리 를 약 64 * 2 * 11, 498, 658 = 1, 471, 828, 224 (175 M) 를 차지한다. 그러나 int 로 전환 할 때 메모 리 를 약 32 * 8185 = 261, 920 (32K) 을 차지한다. 차 이 는 바로 여기에 있다.
세 개의 독창 상황 에서 순환 횟수 를 어떻게 효과적으로 줄 일 수 있 는 지 저 는 이렇게 생각 합 니 다. 위 에서 언급 한 두 가 지 를 빌려 서 사용 합 니 다. 똑 같이 해 야 합 니 다. 이 연속 적 인 것 은 연속 적 으로 해 야 합 니 다. 독창 은 이미 존재 하 는 카드 나 이미 존재 하 는 카드 와 연속 적 인 카드 로 교체 하 는 것 이 가장 좋 습 니 다!세심 한 사람 이 이런 걱정 을 할 수 있 습 니 다. 세 개의 독창 자 는 원래 한 조로 바 꿀 수 있 습 니 다. 이미 존재 하 는 패 와 다 르 고 이미 존재 하 는 패 와 연속 되 지 않 습 니 다. 저 는 증명 할 수 없 지만 이것 은 걱정 이 많 을 것 입 니 다. 왜냐하면 당신 은 서로 다른 비 연속 으로 독창 자 를 처리 해도 이 길 수 있 기 때 문 입 니 다. 똑 같이 연속 으로 독창 자 를 처리 하면 이미 이 겼 습 니 다. 몇 가지 예 를 들 어 테스트 해 보 세 요.
func availableTiles(win []byte) map[byte]bool {
available := make(map[byte]bool)
for _, v := range win {
if v > 0x01 && v < 0x09 || v > 0x11 && v < 0x19 || v > 0x21 && v < 0x29 {
available[v-1], available[v+1] = true, true
}
available[v] = true
}
return available
}
func benchmarkWinEx3Ex(n int, wins map[string][]byte) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
EXIT:
for v1 := range availableTiles(hand[3:]) {
hand[2] = v1
for v2 := range availableTiles(hand[2:]) {
hand[1] = v2
for v3 := range availableTiles(hand[1:]) {
hand[0] = v3
tmp := make([]byte, 0, 14)
tmp = append(tmp, hand...)
if checkValid(tmp) {
if _, ok := wins[string(tmp)]; ok {
win++
break EXIT
}
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}사실 위의 논 리 는 여전히 최적화 할 수 있다. 나 비 를 교체 한 후에 효과 가 있 는 지 다시 검사 하지 않 아 도 된다. 그러나 효율 적 인 측면 에서 오 르 지 않 고 오히려 떨어진다. 왜냐하면 무 작위 로 나 온 손 패 는 매우 복잡 하기 때문에 교체 할 수 없 는 패 를 촉발 할 수 있 는 상황 이 매우 적다.
func appendAvailableTiles(origin map[byte]int, ap ...byte) map[byte]int {
available := make(map[byte]int)
for k, v := range origin {
available[k] = v
}
for _, v := range ap {
if v > 0x01 && v < 0x09 || v > 0x11 && v < 0x19 || v > 0x21 && v < 0x29 {
if _, ok := available[v-1]; !ok {
available[v-1] = 0
}
if _, ok := available[v+1]; !ok {
available[v+1] = 0
}
}
available[v]++
}
return available
}
func benchmarkWinEx3Ex2(n int, wins map[string][]byte) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
available1 := appendAvailableTiles(nil, hand[3:]...)
EXIT:
for v1 := range available1 {
if available1[v1] >= 4 {
continue
}
available2 := appendAvailableTiles(available1, v1)
for v2 := range available2 {
if available2[v2] >= 4 {
continue
}
available3 := appendAvailableTiles(available2, v2)
for v3 := range available3 {
if available3[v3] >= 4 {
continue
}
tmp := make([]byte, 0, 14)
tmp = append(tmp, v1, v2, v3)
tmp = append(tmp, hand[3:]...)
sort.Sort(byteSlice(tmp))
if _, ok := wins[string(tmp)]; ok {
win++
break EXIT
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}낡은 방법 과 효과 적 인 방법 을 검증 해 야 하 는 효율 을 비교 하여 4 배 올 렸 다.
Test total 10000, Win 56, Time 3m59.80354974s
Test total 10000, Win 56, Time 54.301180241s두 가지 새로운 방법 은 효율 을 대비 하여, 오 르 지 않 으 면 오히려 떨어진다.
Test total 50000, Win 277, Time 4m34.589149569s
Test total 50000, Win 277, Time 5m18.078941139s모든 원본 코드
package main
import (
"bytes"
"encoding/json"
"fmt"
"io"
"log"
"math/rand"
"os"
"sort"
"time"
)
var tiles = []byte{
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, // Dots
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, // Bamboo
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, // Characters
0x31, 0x41, 0x51, 0x61, 0x71, 0x81, 0x91, // East South West North Red Green White
}
var full = []byte{
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, // Dots
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, // Bamboo
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, // Characters
0x31, 0x41, 0x51, 0x61, 0x71, 0x81, 0x91, // East South West North Red Green White
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, // Dots
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, // Bamboo
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, // Characters
0x31, 0x41, 0x51, 0x61, 0x71, 0x81, 0x91, // East South West North Red Green White
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, // Dots
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, // Bamboo
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, // Characters
0x31, 0x41, 0x51, 0x61, 0x71, 0x81, 0x91, // East South West North Red Green White
0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, // Dots
0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, // Bamboo
0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, // Characters
0x31, 0x41, 0x51, 0x61, 0x71, 0x81, 0x91, // East South West North Red Green White
}
func findPairs() [][]byte {
pairs := make([][]byte, 0, len(tiles))
for _, v := range tiles {
pair := []byte{v, v}
pairs = append(pairs, pair)
}
return pairs
}
func findGroups() [][]byte {
groups := make([][]byte, 0, len(tiles)+(9-2)*3)
// find three identical tiles
for _, v := range tiles {
group := []byte{v, v, v}
groups = append(groups, group)
}
// find three sequence tiles
for i := 2; i < len(tiles); i++ {
if tiles[i-2]+1 == tiles[i-1] && tiles[i-1] == tiles[i]-1 {
group := []byte{tiles[i-2], tiles[i-1], tiles[i]}
groups = append(groups, group)
}
}
return groups
}
type byteSlice []byte
func (b byteSlice) Len() int {
return len(b)
}
func (b byteSlice) Less(i, j int) bool {
return b[i] < b[j]
}
func (b byteSlice) Swap(i, j int) {
b[i], b[j] = b[j], b[i]
}
func checkValid(win []byte) bool {
sort.Sort(byteSlice(win))
for i := 4; i < len(win); i++ {
if win[i] == win[i-4] {
return false
}
}
return true
}
func notExist(win []byte, wins [][]byte) bool {
for _, v := range wins {
if bytes.Equal(win, v) {
return false
}
}
return true
}
func composeWin(pairs, groups [][]byte) [][]byte {
wins := make([][]byte, 0, 11498658)
tmp := make([]byte, 14)
for _, pair := range pairs {
for _, group1 := range groups {
for _, group2 := range groups {
for _, group3 := range groups {
for _, group4 := range groups {
copy(tmp, pair)
copy(tmp[2:], group1)
copy(tmp[5:], group2)
copy(tmp[8:], group3)
copy(tmp[11:], group4)
if checkValid(tmp) && notExist(tmp, wins) {
win := make([]byte, 0, 14)
win = append(win, tmp...)
wins = append(wins, win)
}
}
}
}
}
}
return wins
}
type twoUint64 struct {
H uint64 // High
L uint64 // Low
}
func composeWinEx(pairs, groups [][]byte) map[twoUint64][]byte {
wins := make(map[twoUint64][]byte)
var key twoUint64
tmp := make([]byte, 14)
for _, pair := range pairs {
for _, group1 := range groups {
for _, group2 := range groups {
for _, group3 := range groups {
for _, group4 := range groups {
copy(tmp, pair)
copy(tmp[2:], group1)
copy(tmp[5:], group2)
copy(tmp[8:], group3)
copy(tmp[11:], group4)
if checkValid(tmp) {
key.H = uint64(tmp[0])
key.L = uint64(tmp[6])
for _, v := range tmp[1:6] {
key.H = key.H<<8 + uint64(v)
}
for _, v := range tmp[7:] {
key.L = key.L<<8 + uint64(v)
}
if _, ok := wins[key]; !ok {
win := make([]byte, 0, 14)
win = append(win, tmp...)
wins[key] = win
}
}
}
}
}
}
}
return wins
}
type jsonData struct {
H uint64 // High
L uint64 // Low
V []byte // Value
}
func toJSON() {
pairs := findPairs()
groups := findGroups()
wins := composeWinEx(pairs, groups)
f, err := os.Create("json.data")
defer f.Close()
if err != nil {
log.Fatal("Create", err)
}
var jd jsonData
enc := json.NewEncoder(f)
for k, v := range wins {
jd.H = k.H
jd.L = k.L
jd.V = v
if err := enc.Encode(jd); err != nil {
log.Fatal("Encode", err)
}
}
}
func benchmarkWin(n int, wins map[twoUint64][]byte) {
var win int
var key twoUint64
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
sort.Sort(byteSlice(hand))
key.H = uint64(hand[0])
key.L = uint64(hand[6])
for _, v := range hand[1:6] {
key.H = key.H<<8 + uint64(v)
}
for _, v := range hand[7:] {
key.L = key.L<<8 + uint64(v)
}
if _, ok := wins[key]; ok {
win++
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
func benchmarkWinEx(n int, wins map[twoUint64][]byte) {
var win int
var key twoUint64
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
EXIT:
for _, v1 := range tiles {
for _, v2 := range tiles {
for _, v3 := range tiles {
tmp := make([]byte, 0, 14)
tmp = append(tmp, v1, v2, v3)
tmp = append(tmp, hand[3:]...)
if checkValid(tmp) {
key.H = uint64(tmp[0])
key.L = uint64(tmp[6])
for _, v := range tmp[1:6] {
key.H = key.H<<8 + uint64(v)
}
for _, v := range tmp[7:] {
key.L = key.L<<8 + uint64(v)
}
if _, ok := wins[key]; ok {
win++
break EXIT
}
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
type simpleData struct {
K int // Key
V []byte // Value
}
func bytesToInt(win []byte) int {
tmp := make([]byte, 0, 17)
tmp = append(tmp, 1)
for i, pos := 1, 0; i < len(win); i++ {
if win[i-1] == win[i] {
tmp[pos]++
} else if win[i-1]+1 == win[i] {
tmp = append(tmp, 1)
pos++
} else {
tmp = append(tmp, 1)
tmp[pos] += 0x0A
pos++
}
}
res := 1
for _, v := range tmp {
switch v {
case 0x01:
res <<= 1
case 0x02:
res <<= 3
res |= 0x06
case 0x03:
res <<= 5
res |= 0x1E
case 0x04:
res <<= 7
res |= 0x7E
case 0x0B:
res <<= 2
res |= 0x02
case 0x0C:
res <<= 4
res |= 0x0E
case 0x0D:
res <<= 6
res |= 0x3E
case 0x0E:
res <<= 8
res |= 0xFE
}
}
return res
}
func toSimple(wins map[twoUint64][]byte) {
f, err := os.Create("simple.data")
defer f.Close()
if err != nil {
log.Fatal("Create", err)
}
var sd simpleData
enc := json.NewEncoder(f)
for _, win := range wins {
sd.K = bytesToInt(win)
sd.V = win
if err := enc.Encode(sd); err != nil {
log.Fatal("Encode", err)
}
}
}
func fromSimple() {
f, err := os.Open("simple.data")
defer f.Close()
if err != nil {
log.Fatal("Open", err)
}
var sd simpleData
dec := json.NewDecoder(f)
wins := make(map[int]bool)
for {
if err := dec.Decode(&sd); err == io.EOF {
break
} else if err != nil {
log.Fatal("Decode", err)
}
wins[sd.K] = true
}
benchmarkWin2(10000000, wins)
benchmarkWinEx2(1000, wins)
}
func benchmarkWin2(n int, wins map[int]bool) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
sort.Sort(byteSlice(hand))
if _, ok := wins[bytesToInt(hand)]; ok {
win++
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
func benchmarkWinEx2(n int, wins map[int]bool) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
EXIT:
for _, v1 := range tiles {
for _, v2 := range tiles {
for _, v3 := range tiles {
tmp := make([]byte, 0, 14)
tmp = append(tmp, v1, v2, v3)
tmp = append(tmp, hand[3:]...)
if checkValid(tmp) {
if _, ok := wins[bytesToInt(tmp)]; ok {
win++
break EXIT
}
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
func benchmarkWin3(n int, wins map[twoUint64][]byte) {
winsCopy := make(map[string][]byte)
for _, v := range wins {
winsCopy[string(v)] = v
}
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
sort.Sort(byteSlice(hand))
if _, ok := winsCopy[string(hand)]; ok {
win++
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
benchmarkWinEx3(1000, winsCopy)
}
func benchmarkWinEx3(n int, wins map[string][]byte) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
EXIT:
for _, v1 := range tiles {
for _, v2 := range tiles {
for _, v3 := range tiles {
tmp := make([]byte, 0, 14)
tmp = append(tmp, v1, v2, v3)
tmp = append(tmp, hand[3:]...)
if checkValid(tmp) {
if _, ok := wins[string(tmp)]; ok {
win++
break EXIT
}
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
func availableTiles(win []byte) map[byte]bool {
available := make(map[byte]bool)
for _, v := range win {
if v > 0x01 && v < 0x09 || v > 0x11 && v < 0x19 || v > 0x21 && v < 0x29 {
available[v-1], available[v+1] = true, true
}
available[v] = true
}
return available
}
func benchmarkWinEx3Ex(n int, wins map[string][]byte) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
EXIT:
for v1 := range availableTiles(hand[3:]) {
hand[2] = v1
for v2 := range availableTiles(hand[2:]) {
hand[1] = v2
for v3 := range availableTiles(hand[1:]) {
hand[0] = v3
tmp := make([]byte, 0, 14)
tmp = append(tmp, hand...)
if checkValid(tmp) {
if _, ok := wins[string(tmp)]; ok {
win++
break EXIT
}
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
func appendAvailableTiles(origin map[byte]int, ap ...byte) map[byte]int {
available := make(map[byte]int)
for k, v := range origin {
available[k] = v
}
for _, v := range ap {
if v > 0x01 && v < 0x09 || v > 0x11 && v < 0x19 || v > 0x21 && v < 0x29 {
if _, ok := available[v-1]; !ok {
available[v-1] = 0
}
if _, ok := available[v+1]; !ok {
available[v+1] = 0
}
}
available[v]++
}
return available
}
func benchmarkWinEx3Ex2(n int, wins map[string][]byte) {
var win int
now := time.Now()
for i := 0; i < n; i++ {
perm := rand.Perm(136)
hand := make([]byte, 14)
for j := 0; j < 14; j++ {
hand[j] = full[perm[j]]
}
available1 := appendAvailableTiles(nil, hand[3:]...)
EXIT:
for v1 := range available1 {
if available1[v1] >= 4 {
continue
}
available2 := appendAvailableTiles(available1, v1)
for v2 := range available2 {
if available2[v2] >= 4 {
continue
}
available3 := appendAvailableTiles(available2, v2)
for v3 := range available3 {
if available3[v3] >= 4 {
continue
}
tmp := make([]byte, 0, 14)
tmp = append(tmp, v1, v2, v3)
tmp = append(tmp, hand[3:]...)
sort.Sort(byteSlice(tmp))
if _, ok := wins[string(tmp)]; ok {
win++
break EXIT
}
}
}
}
}
fmt.Printf("Test total %d, Win %d, Time %v
", n, win, time.Since(now))
}
func main() {
// fromSimple()
// return
f, err := os.Open("json.data")
defer f.Close()
if err != nil {
log.Fatal("Open", err)
}
var jd jsonData
dec := json.NewDecoder(f)
wins := make(map[twoUint64][]byte)
for {
if err := dec.Decode(&jd); err == io.EOF {
break
} else if err != nil {
log.Fatal("Decode", err)
}
wins[twoUint64{
H: jd.H,
L: jd.L,
}] = jd.V
}
benchmarkWin(10000000, wins)
benchmarkWinEx(1000, wins)
//benchmarkWin3(10000000, wins)
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
파이토존에서 마작을 했어요.나는 파이톤에서 마작을 할 수 있는 종목을 자제하고 있다. 이번에는 혼자서 마작을 하면서 카드를 우두둑우두둑 잘라내는 종목이다 점차 기능을 늘려 마작 AI를 만드는 것이 최종 목표다. 1~9이라는 숫자가 적힌 만자,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
