最近一直在学习 Rust。想起以前每次学习新语言,都会实现一个俄罗斯方块来验证对语言的掌握,但是从来没有尝试去实现其AI。正好这次碰到这个挑战,所以没有多想就使用 Rust 来做此题了。
题目之前的大佬已经分析得很完善了,这里不再赘述。
我采用的方法也是常规深度搜索(DFS)。即,在当前局面下,计算出下一个方块的所有可能放置方式,然后根据消行和计分规则得到当前局面的子局面,以及子局面的分数。以此类推,可以得到游戏的完整状态树。最后,只需要找到通往最高分的子局面的路径即可。
但是由于方块共有10000块,简单计算就知道,没有足够的空间和时间完成完整的状态遍历。所以后面使用了一系列方法来优化这个过程:
sum = sum - (height - 10)^2
.2 * tree_height
. 做到这一步时,第一次提交了成绩 66w. 此时深度为7。到上面为止,算法的整体框架就完成了,后面做的努力基本就是在调整评估函数和并行优化.
最后选择的评函数为:
self.evaluated =
min_occupied.iter().enumerate().fold(0i64, |a, (_col, b)| {
//const LVL: i64 = 5;
let b = *b as i64;
//if _col < 8 {
let b = b - avg_occupied;
a - b * b
// if b < LVL {
// let b = (LVL - b) as i64;
// a - b * b
// } else {
// // a + b
// a
// }
// } else {
// if avg_occupied > 6 {
// let b = 20 - b;
// a - b * b
// } else {
// let b = b - avg_occupied;
// a - b * b
// }
// }
//}) + space_count.iter().fold(0i64, |a, b| a - std::cmp::min(6, *b) * 15)
}) + space_count.iter().fold(0i64, |a, b| a - b * 20)
+ occupied_grid as i64 * 4
+ match full_rows.len() {
1 => occupied_grid,
2 => occupied_grid * 3,
3 => occupied_grid * 6,
4 => occupied_grid * 10,
_ => 0,
} as i64;
故意保留了注释,说明了当时尝试过的一些思路:
这一部分其实是我在这个游戏中消耗时间最多的。为了 make rust compiler happy. 几乎重写了搜索的数据结构。最后使用 crossbeam
的 deque
和 scope
完成了搜索树的 BFS 处理。关键代码如下:
fn find_task<T>(
local: &Worker<T>,
global: &Injector<T>,
stealers: &[Stealer<T>],
) -> Option<T> {
// Pop a task from the local queue, if not empty.
local.pop().or_else(|| {
// Otherwise, we need to look for a task elsewhere.
iter::repeat_with(|| {
// Try stealing a batch of tasks from the global queue.
global
.steal()
//.steal_batch_and_pop(local)
// Or try stealing a task from one of the other threads.
.or_else(|| stealers.iter().map(|s| s.steal()).collect())
})
// Loop while no task was stolen and any steal operation needs to be retried.
.find(|s| !s.is_retry())
// Extract the stolen task, if there is one.
.and_then(|s| s.success())
})
}
由于,子树不是完全相同的,有些子树快,有些慢,所以必须要支持一个工程线程可以取得(steal)其它工程线程的任务,才能保证并行加速的最大化。最开始只是根据第一层子节点,每个节点一个线程进行搜索。CPU占有率无法超过500%,大部分时间200%左右。
pub fn search(
mut init: AIState,
depth: usize,
min_row: usize,
) -> Option<AIState> {
let end_level = init.level + depth;
let injector: Injector<AIState> = Injector::new();
let mut workers = Vec::new();
let mut stealers = Vec::new();
let (tx, rx) = channel::unbounded();
for _ in 0..THREADS {
let worker = Worker::new_fifo();
workers.push(worker);
}
for worker in workers.iter() {
stealers.push(worker.stealer());
}
let global = &injector;
let stealers = &stealers[0..];
let mut roots = init.search_next_step(min_row)?;
for (index, state) in roots.iter_mut().enumerate() {
state.root_index = index as i8;
injector.push(*state);
}
let rt = thread::scope(|s| {
for (_i, local) in workers.into_iter().enumerate() {
let tx = tx.clone();
s.spawn(move |_| {
while let Some(mut state) = BFS::find_task(&local, global, &stealers)
{
if state.level < end_level {
if let Some(states) = state.search_next_step(min_row) {
//let width = std::cmp::min(14, (end_level - state.level) * 2);
let width = std::cmp::max(3, end_level - state.level);
for mut sub_state in states.into_iter().take(width) {
//for mut sub_state in states.into_iter() {
sub_state.evaluated += state.evaluated;
local.push(sub_state);
}
} else {
tx.send(state).unwrap();
}
} else {
tx.send(state).unwrap();
}
}
drop(tx);
});
}
drop(tx);
let result_join = s.spawn(|_| {
let mut chosen: Option<AIState> = None;
for state in rx.iter() {
chosen = chosen
.and_then(|selected| {
if state.evaluated > selected.evaluated {
Some(state)
} else {
Some(selected)
}
})
.or_else(|| Some(state));
}
chosen
});
result_join.join().unwrap()
})
.unwrap()?;
Some(roots[rt.root_index as usize])
}
这里需要注意的一点,就是 crossbeam::thread::scope
的使用。如果没有它,injector
和 stealers
传入到线程闭包中都会让编译器UNHAPPY!!
在最后一天尝试取得高分时,会去尝试评估函数的各种参数,为了高分,参数选得比较大时,会碰到无法完成10000块的情况。回看录像,可以看到有更好的走法,但是由于深度不够,陷入局部最优解,然后把自己玩死。最后解决这个办法是,先使用低的搜索深度向后走,如果死了,就回退两倍深度的方块,再使用+1深度的搜索尝试。在走过难点后,再回退用低深度向后走。最终使用的参数是,默认8层,最多回退使用12层。最终这个方法做到104w
由于方块序列提前可以计算得出,所以可以提前判定I方块在何时出现。考虑到I方块是唯一可以完成四行同时消的方块。因此,我们可以对I方块前的若干方块提高深度进行搜索。这个优化是在比赛快结束时想到的。最开始选择的参数是提前10块用11层搜索。但跑了一个多小时后发现,预计要3个小时才能完成,预计得分109w左右。但已经过了最后提交时间了,所以不得不忍痛放弃。所以改成提前9块用10层搜索,最终半小时取得107w的结果, 剩下的时间已经不够其它尝试了,遂躺平,等待最后的结果。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。