2

ビットボードの表現は、64ポジション未満の唖然としたチェスのような戦略ゲームでも同じくらい効果的でしょうか、それとも、より単純な配列ベースのメールボックスの実装がより実用的でしょうか？

私たちの学校のAIクラスでは、教授がボードゲームを作成するコンテストが毎年開催されており、ゲームをプレイするAIを作成するために4週間の猶予があります。通常、駒は同様のルールを持つチェスの駒のサブセットであり、小さいボードで再生されます。つまり、8x5、7x7などです。チェスの一般的な64ビットと比較して、40ビットのみを使用する方法はまったくわかりません。

私の唯一の問題は、私がCまたはC ++にあまり精通しておらず、Javaでプログラムを実装する方が快適だということです。ビットボード表現を実装できるビット操作に対するJavaでの十分なサポートはありますか？これにより効率が向上する場合は、複雑さを追加する価値がありますか？学習曲線は急すぎますか？

私の計画は、時間に応じて、ABプルーニング、クイエッセンス検索、転置テーブル、キラームーブなどでNegamax検索を使用することです。このような短時間で競争力のあるAIを作成するための他のヒントはありますか？

4

4 に答える 4

2

A bitboard would work, but in my opinion, the added effort and complexity just to get it working properly isn't worth any possible gains in computing efficiency later on.

In the overall scale of things, any efficiencies from bitwise masking (& or |) over fetching an element of an array (or even a List or Map) would be largely overshadowed by whatever AI or search algorithm you intend to use.

That is, an algorithm of exponential or polynomial complexity will still take O(e^n) or O(n^d) and what few CPU cycles you save with binary arithmetic over pointer dereferencing will be insignificant.

Just go with the easiest data structure you can use at this point (probably an array, or whatever Collection) and focus on getting your algorithms to work.

Later, if you have time, you can profile your program and if you find that array lookups are taking up, say, 20% of your run-time then maybe, just maybe, consider refactoring everything to bitwise ops.

Personally, I'd look at possible ways to conduct the searches of the solution space in parallel, to maximize multiple CPU cores, or better yet, in a way that can be distributed across multiple compute nodes. Yes, that'd probably qualify you for at least Master's degree if you discover something really clever. :)

于 2013-02-06T05:07:32.553 に答える
1

In university I had game AI writing competitions similar to yours, and I achieved the biggest speedups not when I worried about some little minutae like 'is coding things statically faster' or 'will sanity checks slow my program down?' but 'If I write my AI to be smarter/more efficient, it will perform a level of magnitude better, so I'm going to implement this cool new trick I found'.

Usual examples of staggering speedups are alpha-beta pruning, killer heuristic and choosing a good algorithm for calculating the strength of a game state (note that good != more accurate - it could also mean faster and still accurate. After all, if your score calculation is simpler it lets you look more moves ahead, which means you make up for it in spades).

于 2013-02-06T05:23:29.847 に答える
1

You might as well use bitboards. It's not really that complex, and you get a significant speedup in move-generation and static exchange evaluation. Your AI algorithm, no matter how clever, will still need to do a ton of those.

There's a very good website on the subject: chessprogramming.wikispaces.com/Bitboards

Since your boards are a different size some tricks may not apply, depending on how you assign bits to squares. On the other hand, since it's only a subset of the pieces, some problems that were traditionally problematic to solve with bitboards may not exist.

于 2013-02-06T08:39:22.460 に答える
0

Setting individual bit in bit scale is usually slower than settings element in boolean array, because the former requires read + bitwise AND/OR + write, while the latter requires just write.

Reading individual bit in bit scale is also slower: read + bitwise AND/OR + shift versus just read.

So if your AI will need lots of reading/writing states of individual board cells, than boolean array will be more effective. At the same time, operation of making a clone of the whole board is faster when board uses less memory, i.e. when cells are packed into bits. If your AI will clone bards often and do only few get/set operations between cloning operations, than bit scale is better regardless of the board size.

于 2013-02-06T05:07:49.097 に答える