jeu poster le plus tard possible - Page 1372

podcast ?

very> lol pour avant

thx

Every country has its own Canada. For example:

Sweden is the Canada of Norway
Korea is the Canada of China
Austria is the Canada of Germany
Belgium is the Canada of France
England is the Canada of Scotland
New Zealand is the Canada of Australia
Canada is the Canada of America


Help me compile a big list of Canadas.

http://www.hugeurl.com/?NDYzMWY1ZmU0YmZjNTNkMzIzOWZjNzZmNTIxYjVmOTYmMTImVm0wd2QyUXlVWGxXYTJoV1YwZG9WVll3Wkc5alJsWjBUVlpPV0Zac2JETlhhMUpUVmpGYWMySkVUbGhoTWsweFZqQmFTMk15U2tWVWJHaG9UVmhDVVZadGVGWmxSbGw1Vkd0c2FsSnRhRzlVVjNOM1pVWmFkR05GZEZSTlZUVkpWbTEwYTFkSFNrZGpTRUpYVFVad1NGUlVSbUZqVmtaMFVteFNUbUY2UlRGV1ZFb3dWakZhV0ZOcmJGSmlSMmhZV1d4b2IwMHhXbGRYYlVaclVsUkdXbGt3WkRSVk1rcElaSHBHVjJFeVVYZFpWRVpyVTBaT2NscEhjRlJTVlhCWlZrWldhMVV5VW5OalJtUllZbFZhY1ZscldtRmxWbVJ5VjI1a1YwMUVSa1pWYkZKRFZqQXhkVlZ1V2xaaGExcFlXa1ZhVDJOdFNrZFRiV3hYVWpOb1dGWnRNSGRsUjBsNFUydGthVk5GV2xSWmJHaFRWMVpXY1ZKcmRGUldiRm93V2xWb2ExWXdNVVZTYTFwWFlrZG9jbFpxU2tabFZsWlpXa1prYUdFeGNGaFhiRnBoVkRKT2RGSnJhR2hTYXpWeldXeG9iMWRHV25STlNHaFBVbTE0VjFSVmFHOVhSMHBJVld4c1dtSkhhRlJXTUZwVFZqRmtkRkp0ZUZkaWEwcElWbXBKZUUxR1dsaFRhMlJxVWtWYVYxWnFUbTlsYkZweFUydGthbUpWYnpKVlYzaHJZVWRGZUdOR2FGaGlSbkJvVmtSS1QyUkdTbkpoUjJoVFlYcFdkMVp0Y0V0aU1rbDRWMWhvWVZKRlNtOVVWbHBYVGxaYVdFNVZPVmhTTUZZMVZsZDRjMWR0U2toaFJsSmFUVlp3ZWxreWVIZFNWa1p5VDFkc1UwMHlhRmxXYlhCTFRrWlJlRmRzYUZSaVJuQnhWV3hrVTFsV1VsWlhiVVpzWWtad2VGVXlkR3RoYlVwV1ZtcGFXbFpXY0doWlZXUkdaVWRPUjJKR2FHaE5WbkJ2Vmxod1MxUXhXWGhqUld4VllrWmFjRlpxVG05a2JGcEhWbTA1VWsxWFVucFdNV2h2V1ZaS1JsTnRSbGRpV0U0MFZHdGFXbVZIUmtoUFYyaHBVbGhCZDFac1pEUmpNV1IwVTJ0b2FGSnNTbGhVVmxwM1YwWnJlRmRyZEd0U2EzQjZWa2R6TVZZeVNsbFpNMmhYVFc1b1dGWnFSbEpsUm1SWldrVTFXRkpZUWxsWFZtUjZUVlpzVjFWc1dsaGliVkpZVlcxNGQyVkdWblJOVldSWFRVUkdlVlJzVm05V01VbzJVbXRvVjFaRldreFdha3BQVW14YWMxcEhiRk5OVlZZelZteGFVMUl4YkZkWGJrcE9WbXh3V0ZsWWNGZFdSbFp5Vm10YVQxVlVNRGs9

./41136> WIN

ce serait pas un peu biaisé comme comparatif ?

bon maintenant, trouver des chaines A et B telles que hugeurl/A => tinyurl/B => hugeurl/A

ouais j'y ai pensé aussi mais en fait ça va pas diviser par zéro malheureusement

damnvoid (./41139) :
ce serait pas un peu biaisé comme comparatif ?

en effet, à peine orienté le truc...

Hey les informaticiens..

J'ai un ensemble E de quelques centaines d'éléments.

J'ai besoin de représenter les parties de E.

Plus précisément, je veux pouvoir calculer la réunion de deux parties, et tester l'inclusion de l'une dans l'autre. Rapidement, et en utilisant peu de mémoire (ha ha, sérieusement?)

J'ai le droit d'utiliser des hash ou quelque chose comme ça, plutôt qu'une représentation exhaustive de la partie (C'est pas grave s'il n'y a qu'un nombre faible d'erreurs/collisions).


Est ce qu'il y a une structure de donnée et des algorithmes pour faire ça bien?

Je ne suis pas informaticien, désolé.

ben il faudrait réfléchir aux classes d'équivalences que tu veux : avec un hash classique tu auras des classes toutes moisies qui mettent ensemble des parties radicalement différentes, ça n'aurait pas de sens de parler d'inclusion d'une classe dans une autre* ; peut-être que ton problème peut être résolu avec certaines classes d'équivalence bien choisies (genre je sais pas, tu agglomères des paires d'éléments en un seul élément), mais sinon je pense pas que tu pourras couper au bon vieux champ de bits...

ou en d'autres termes : le hash favorise l'égalité au détriment de l'ordre, donc ce que tu veux n'est pas un hash mais une forme de "compression".


(* : à moins que la majorité de tes parties soient dans un petit sous-ensemble des parties, dans ce cas-là s'il y a une unique telle partie dans ta classe ça marche)

R 10:29 wided: bonjour

En fait ça a à voir avec le go, ce problème.

Mon ensemble E, c'est l'ensemble des intersections du goban, et la partie de E, c'est une chaîne de pierres.

J'aimerais décider si une chaîne, dans une position tardive de la partie, a été obtenue par concaténation de pierres avec une chaîne du début de la partie. Le but étant de calculer des corrélations, faire de l'inférence bayésienne, ou ce genre de choses, pour qu'une IA puisse dire "telle chaîne doit vivre pour espérer gagner" ou "telle chaîne doit être connectée pour espérer vivre", etc..

Au go on utilise classiquement le hash de Zobrist : On se fixe au début du programme une fonction aléatoire f : E -> { les entiers de 64 bits } (par exemple), sous la forme d'un tableau rempli de nombres aléatoires. Le hash d'une chaîne, c'est juste le XOR des f(i) pour tout élément i de la chaîne.
C'est simple et ça a plein de qualités, notamment la réunion de deux chaînes est très rapide (un XOR). Par contre ça ne permet de savoir si une chaîne est un sous ensemble d'une chaîne plus grosse.

Bon mais en fait je crois que j'ai trouvé ce que je cherchais :
http://en.wikipedia.org/wiki/Bloom_filter

Pas sûr que ça ait des performances radicalement meilleures qu'un champ de bits, par contre, faut voir...

oui c'est à ce genre de choses que je pensais en parlant d'"agglomérer des paires d'éléments en un seul élément" ^^

Donc en fait ça voudrait dire fabriquer une fonction g aléatoire de E dans l'ensemble des entiers à m bits, telle que g(i) a toujours k bits à 1.
Alors le hash d'une chaîne est le OR des g(i) pour tout élément i de la chaîne.
Réunir deux chaînes se résume à faire un OR, et tester l'inclusion est facile aussi.

Ah, c'est splendide. Clair, élégant et rapide.
Ne reste qu'à trouver m et k pour qu'il n'y ait pas trop de collisions et pas trop de faux positifs.
Comme le go ajoute plein de contraintes pratiques (les éléments d'une chaîne sont assez "localisés" puisqu'adjacents, une chaîne a dans la plupart des cas moins de 10-15 éléments, et dans le pire des cas moins de 50), ça doit être possible d'avoir une solution bien.

Joie.

Donc l'idée est très proche de l'algorithme de Zobrist, on remplace juste XOR par OR et on met pas trop de bits pour que ça puisse marcher.

Bon par contre une différence c'est que Zobrist permet de hacher non seulement les chaînes, mais aussi la position globale du plateau.
Il suffit d'avoir deux fonctions f_noir et f_blanc et de faire le XOR des f_noir(i) pour toute pierre noire i et f_blanc(j) pour toute pierre blanche j.

On pourrait faire ça aussi avec Bloom, mais ça parait moins crédible, j'ai l'intuition qu'il faut vraiment augmenter m pour éviter les collisions/faux positifs. Ca vaut quand même le coup de lire l'étude théorique de wikipedo, ça serait grassouille de n'avoir à calculer qu'un hash au lieu de deux.

Un truc emmerdant, quand même, c'est de ne pas pouvoir simplement enlever d'élément. Ca interdit la mise à jour incrémentale du hash lors d'une capture de pierres (évènement rare, mais tout de même...)

en fait j'ai pas bien compris à quoi te servira l'inclusion ? ni ce que tu entends exactement par chaîne ? c'est pas ordonné j'imagine, donc quelle est la différence avec le plateau à part pour les captures ?

(et 368 bits c'est vraiment prohibitif ?)

et pour le recalcul du filtre c'est pas forcément compliqué, rien qu'un truc du style filter = bitfield | bitfield>>42 | bitfield>>123 | ... pourrait suffire même si c'est moins robuste théoriquement qu'un vrai filtre de Bloom ^^

Une chaîne c'est un ensemble maximal de pierres d'une même couleur, connectées verticalement et horizontalement.

L'inclusion j'en aurai besoin dans mon analyseur (du moins tel que je me représente mon moteur actuellement) pour comparer des positions proches de la racine et proches des feuilles dans l'arbre de recherche. (C'est à dire savoir si telle chaîne de fin de partie a été obtenue à partir d'une chaîne de début de partie en rajoutant des pierres)

Avoir un hash court et rapide (et qui, idéalement, soit un entier) c'est vraiment sympa, parce qu'il y a vraiment du gros stockage de positions et du gros travail de comparaisons de hashs. 64 bits (voire 32?), ça parait un vœu raisonnable pour du go 9*9, avec 81 intersections. Ça serait bien que 64 ou 128 bits marchent aussi pour du 19*19.

D'ailleurs, maintenant que j'y pense, ça serait amusant et encore plus grassouille de ne pas représenter du tout le plateau, de se contenter de hashs de bloom. En plus ça doit (presque) être faisable, il faut surtout s'assurer d'un taux vraiment faible de collisions.
Rôh ça serait puissant, ça, un moteur d'intelligence artificielle qui ne retient même pas la position des pierres

Pour ça va falloir voir comment bloom et zobrist se comportent vis à vis du pattern matching et du décompte des libertés, etc..

Pollux (./41152) :
et pour le recalcul du filtre c'est pas forcément compliqué, rien qu'un truc du style filter = bitfield | bitfield>>42 | bitfield>>123 | ... pourrait suffire même si c'est moins robuste théoriquement qu'un vrai filtre de Bloom ^^

Pff ça sera programmé en caml mon cher
(bon yaura un peu de C pour gérer les manips de bits de bas niveau, ok ^^)

je serai curieux de voir les résultats de tes algos

Rôh il me vient en tête une structure de donnée de la mort qui tue, pour représenter une position sans mémoriser les pierres, et incrémenter rapidement

Cherche quand même si une lib pour faire des opérations bitwise sur plus de 64 bits n'existe pas déjà avant de la coder ^^

c'est chiant ces gens qui cassent le layout des pages

²

à qui la faute ?